[Official] Contest 4 Hints

@rishup_nitdgp My code with Time complexity O(n*(n+logn)) is still accepted in 1sec.

As I replied to @harshraj22. Test cases are weak for the problem.

@rishup_nitdgp Why is my solution for EURON giving TLE, even when its time complexity is O(nlogn), pls check it here

Worst case time complexity for std::distance function is O(N). For more information, visit here.

then how is @harshraj22 answer in python, having the same complexity as mine, gets accepted even in 1.22 sec of runtime ??

I would like to say a few things:

  1. Rishup already pointed out, test cases are weak. Given the constraints, a O(n2) solution should not pass.
  2. The Python3 Solution is not mine.
  3. Python has different time multiplier (which might have given edge over cpp solution)
  4. Finally, the constants, they are ignored while calculating time complexity, but still play a major role. Read here

I know, it is strange for the same complexity to be accepted in one language and rejected in another, but maybe you should focus on improving the complexity from O(n2)

1 Like

Your solution complexity is roughly O(N^2 + N*Log N), that’s why you are getting TLE.

P.S: Log N factor due to std::multiset.

Did you mean O(n * (n + logn)) ?

1 Like

Thanks.

1 Like

Problem EURON
I have used pbds data structure for the problem.
My code is working fine on sample test cases.
Can anyone tell me where I am going wrong.
Here is link to my code.

the test cases also consist of duplicate elements, so pbds ordered set will not work , you have to change one template of tree from less to less_equal , by this it will work as multiset. You can check my solution, I have also used pbds…
Here is my soln my code

1 Like

@supandeep Thanks .

I followed the same approach of question 4 as given in hint but still getting TLE. please tell me where it went wrong. CodeChef: Practical coding for everyone

Iam getting wrong answer on problem EURON . Its working correctly on sample test case. Could anyone help me regarding this. Where iam doing wrong?
See my solution here

replace int with ll (long long)

@rishup_nitdgp can you please look at my code …(Giving WA)
https://www.codechef.com/viewsolution/33603451

My logic is since in the given constraints qi ranges form 1 to 10000 that is we are not going to ask the minimum element 100001 or more…so we can just sort the given input array and take the sum of just 100 values from first array with the 100 element of second array and store it in vector effectively I am just caluclating the 10000 sums and then answering the queries in o(1) time.

I am implementing the same approach as given in hints but it’s still giving TLE in problem LOWSUM
Here is my code.
How can I make it more efficient

Can anyone help me in Problem ASHIGIFT . My solution got accepted when i used binary search range [1,sum+5] where sum=sum of y[i] . But i got WA in one test when i used binary search range [1,10^18+5].
Accepted Solution
Wrong solution
Help me in overflow understanding

Can anyone explain why my logic is not working for problem EURON? My solution: CodeChef: Practical coding for everyone

What i am trying to do here is, for every index i am calculating the no. of elements greater than a[i] (which are present at left of a[i]) and adding to the answer and keep inserting a[i] in sorted vector at desired index so that vector remains sorted.

y i am still getting the time limit exceeded in the question LOWSUM although i have implemeented the strategy of the hints The link of my solution is in this link…pls tell me where Iam doing wrong