Codforces Round 696 | Problem C | TLE

In problem C of yesterday’s round, i’ve tried to optimize the soln as much as i can, and still i’m getting a TLE in test case 8. Can you please help me in resolving this issue!?

My submission : https://codeforces.com/contest/1474/submission/104902419

Problem Link : Problem - C - Codeforces

My approach :
I use a TreeMap, and for every step, i use max = map.getFirst() to get the maximum element. then i search whether (sum - max) is present in the map or not, if it is present then we go further, otherwise we’ll return.

Similar solutions, in C++, are getting accepted. ( they use multiset) however, i’m having trouble with this. Please help!!!

I did C in C++ using a multimap and I got to say, I feel you. This sucks. I had similar issues with java before (I learned coding in java) and it is one of the reasons I switched to C++.
I didn’t look at your code in detail. In my experience, many of the build-in data structures in java suck hard. I think they are just super slow to build and in this task, you have to rebuild them often. - At least that is what I did. Try out all possible positions that pair up with the maximum value …
I bet you can be a lot faster if you just build the structure once and maintain a counter of how many copies of each number are available. In this way, you only have to change the counters and the tree does not require any changes.

I guess you should profile it to know for sure.

I used set as well as Map in C++ still AC.
C++ is faster than Java
Solution Link-Submission #104861963 - Codeforces

1 Like

i’ve done exactly that… i’ve used a map in order to store elements and their frequencies ( counters, like you said). However, in order to get the max element in O(1) time, i have to delete elements from the map when their frequency becomes 0.