sahilrathore03's blog

Getting TLE on O(nlogn) solution with n <= 2e5
By sahilrathore03, 12 hours ago, In English

I was trying to solve this problem during contest.
Problem: 2061B - Kevin and Geometry

I wrote this solution for it which is an O(nlogn) solution but it is giving tle on the last pretest(10). I am unable to figure out the reason for this.
Submission: 302117530

Approach:
- Check the frequency of every element using map.
- If all elements are distinct, no valid solution is possible.
- If there is an element with frequency >=4 we can simply print that element 4 times since we found a square.
- If more than 1 elements have frequency greater than 1 we can print those 2 elements twice since we found a rectangle.
- Now only 1 case remains. We have a single element with freq>1 and we fix the isosceles side as this element. Now for the base and roof we can select any two elements such that | base — roof | < 2*side. For this we sort the array in O(nlogn) time and check adjacent elements.

TC: O(nlogn).
SC: O(n)

Can anyone help me out. Where is the problem with this solution?

  • Vote: I like it
  • +4
  • Vote: I do not like it

»
11 hours ago, # |
  Vote: I like it +21 Vote: I do not like it

Do not use unordered_map in any contest.

→ Reply
  • »
    »
    11 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It worked. Thanks a lot

    → Reply
  • »
    »
    10 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    why unordered_map gave tle and map worked totally fine ?

    → Reply
»
11 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Use map instead of unordered map. And it will pass.

→ Reply
»
11 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Unordered map may be the issue try with ordered map .

→ Reply
»
11 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

read this https://codeforces.net/blog/entry/62393

→ Reply
»
11 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

about the problem , you dont need frequency .. just sort the array , get the biggest pair of elements that the are equal , erase them from the array , and iterate on it .. if you find an element a[i] such that : |A[i] — A[i + 1]| < 2 * C (here C is the value of the pair of equal elements) print a[i] , a[i + 1] , c , c

→ Reply