CF div-3 problem C

general
, ,
1

Problem link-link text

Solution link-link text

Im getting TLE for input size 120000

Can Anyone please suggest a algorithm for this to solve in 3 sec.

Also why im getting TLE even if the time constraint (is high compared to 1 sec ) = 3 sec

2

Maintain a map to store the frequencies of elements . Then for all the power of 2 traverse the array for every element check if its second part is present in array or not. For more Refer to my SOLUTION

3

Let me explain how I solved this question. Now note that all are positive numbers.

Note: we can use binary search to find if an element exists in an array

We have to find arr[j] for every arr[i] such that arr[i] + arr[j] = 2^n for some n

Now,

There are limited n because of the limit of integers in C++/C.

So,

This becomes pseudocode:

For every arr[i] in arr

run a loop to find smallest l which satisfies (1 << l) >= arr[i] (In other words arr[i] <= 2^l)

Run l till 30 and check if (1 << l) - arr[i] exist in array

If (1 << l) exist for any l then, it must be included.

Edge Case: arr[i] == (1 << l) and no l other that (1 << l) == arr[i] exist in array

Solution: Check if arr[i] is present more than once else it won’t be included.

I did something similar but not exactly the same due to the pressure of the contest. Check my solution here. Though in C++, I think you might understand if you try.

Comment on your solution: After giving a glance to your solution O(n^2 . log(n)), I stopped reading it. This makes a worst-case run to be nearly 1.2 \times10^5 \times 1.2 \times10^5 \times 16.87 = 2.4 \times 10^{11} operations (nearly). Never gonna work.

Tip: In contest, just think of an approach and put maximum values of variables in complexity of approach. If worst-case operations <= 10^7 (nearly), then its good to implement.

Solution Link

4

I don’t know map bcoz I use c, sorry can u please elaborate solution.

5

@ay2306 I have used same logic as u mentioned.

Solution link I have updated. Now getting TLE for size= 119999

But passes for size=120000.

Also I don’t understand why im getting TLE this time bcoz in worst case my code produces = n * 30 *log(n) iterations(n=120000)

Which turns out to be 60732000 operations in worst case.

Will this not work under time constraint 3 sec?

6

I posted a link to my solution. Compare it with your solution. Tell me if you still have a problem

7

Thanks a lot , My qsort() function (inbuilt) was leading to TLE, I guess it would be O(n^2). I changed to merge sort, and got AC. Now before using
qsort() , ill think 10 times :slight_smile: