Yup, it is O(n log n).

Active In

International Olympiad in Informatics

Competitive Programming

Indian Computing Olympiad (ICO)

International Mathematics Olympiad

Deep Learning

U.S. College Admissions for International Students

Technology

Artificial Intelligence

Bitcoin and Blockchain

Game Development

Featured Contributions

reply in this discussion

Shashwat ChandraI have discovered a truly remarkable proof for P = NP but the margin is too small to contain it. · 12w

Yup, it is O(n log n).

Read more… (6 words)

reply in this discussion

Shashwat ChandraI have discovered a truly remarkable proof for P = NP but the margin is too small to contain it. · 17w

You only need to print the last four digits of the answer i.e mod 10000.

Read more… (15 words)

reply in this discussion

Shashwat ChandraI have discovered a truly remarkable proof for P = NP but the margin is too small to contain it. · 23w

I guess 15.

Read more… (3 words)

reply in this discussion

Shashwat ChandraI have discovered a truly remarkable proof for P = NP but the margin is too small to contain it. · 23w

No, I wasted 1/2 of the time trying to get 100 on the second one after I had got 75.

Read more… (20 words)

reply in this discussion

Shashwat ChandraI have discovered a truly remarkable proof for P = NP but the margin is too small to contain it. · 23w

I made one case like that manually and my code worked fine on that.So,I pretty sure my code works fine for those cases

Read more… (23 words)

reply in this discussion

I also did the same but got 75.

Read more… (8 words)

reply in this discussion

Shashwat ChandraI have discovered a truly remarkable proof for P = NP but the margin is too small to contain it. · 25w

#include <bits stdc++.h="">using namespace std;int main() {long long int n,k;cin >> n >> k;long long int a[n];for(int i = 0;i < n;i++)cin >> a[i];sort(a,a+n);long long int i = 0,j = n-1,ans = 0;while(i < j){if(a[i] + a[j] < k){ans += j-i;i++;}else j--;}cout << ans;return 0;}

Read more…

reply in this discussion

Shashwat ChandraI have discovered a truly remarkable proof for P = NP but the margin is too small to contain it. · 25w

Nope, It wont give TLE. Also, I recommend you to read this Binary Search – topcoder .

Read more… (17 words)

reply in this discussion

Shashwat ChandraI have discovered a truly remarkable proof for P = NP but the margin is too small to contain it. · 25w

Your code will fail on test cases like : 5 4 1 2 3 4 5.

The answer is 1 but your code will output 0.

You need to add an extra loop or binary search for each position i to find a position j such that a[i] - a[j] >= k and then add j+1 to the counter.

Read more… (59 words)

reply in this discussion

Shashwat ChandraI have discovered a truly remarkable proof for P = NP but the margin is too small to contain it. · 28w

Here's the official solution -

In this problem, the necklace size is small enough (350) that we might as well just try breaking the necklace at each point and see how many beads can be collected. This will take approximately O(n^2) time, but n is small enough that it won't matter.The code is slightly simple-minded in that we might count the same beads twice if they can be taken off either side of the break. This can only happen if all beads can be taken off the necklace, so we just check for that at the end.

#include <stdio.h>#include <string.h>#include <assert.h>#define MAXN 400char necklace[MAXN];int len;/** Return n mod m. The C % operator is not enough because* its behavior is undefined on negative numbers.

Read more… (97 words)