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?
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://codeforces.net/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