I was trying to solve this problem during contest.
Problem: 2061B - Кевин и Геометрия
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?
Do not use
unordered_mapin any contest.It worked. Thanks a lot
why unordered_map gave tle and map worked totally fine ?
Because
unordered_mapcan be hacked by hash collision and become O(n).got it.
Use map instead of unordered map. And it will pass.
Thanks for clarifying...
Unordered map may be the issue try with ordered map .
Yeah it worked with map.
read this https://mirror.codeforces.com/blog/entry/62393
Thanks for the blog post.
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