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

reply in this discussion

Shashwat ChandraIOITC 2018 · 51w

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

Read more… (15 words)

reply in this discussion

reply in this discussion

Shashwat ChandraIOITC 2018 · 1y

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 ChandraIOITC 2018 · 1y

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

reply in this discussion

Shashwat ChandraIOITC 2018 · 1y

#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 ChandraIOITC 2018 · 1y

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

Read more… (17 words)

reply in this discussion

Shashwat ChandraIOITC 2018 · 1y

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 ChandraIOITC 2018 · 1y

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)