saiteja_0712's blog

Vlad and Division -> Help with this
By saiteja_0712, history, 9 months ago, In English

Problem link : https://codeforces.me/contest/1926/problem/D Submission : 247469924

My Approach Here I tried to make the groups of 2 integers whose xor will be 0. If we consider number of bits=3 then max possible number in binary = 111(7) and after flipping the bits it will be 000(0). lets take a number 101(5) after flipping bits it will be 010(2) (as we are considering only 3 bits) then i concluded to get the number after flipping the bits we should do (maxPossibleNumber — currNumber) -> this gives the number after flip. In the same way I formed the groups for 11 bits maxnum=2147483647 for the given problem. But im getting TLE for this code. But unable to figure out why im getting TLE.Even though it is an O(N) approach. Please help me out in this.

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

»
9 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Used a map and it got accepted 247485674. Maps are faster than unordered maps. Worst case of insertion in an unordered map is $$$O(N)$$$

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

    unordered_maps are usually faster than maps, but they have some drawbacks:

    • In contests with hacks, avoid unordered_map. Hackers can exploit hash collisions to make your code run in O(n) time. (The hacked test cases will be used to evaluate all submissions after the hacking phase ends)
    • In contests without hacks, be careful with unordered_map. The problem setters may have prepared some tricky test cases to slow down your code. It’s safer to use map instead.

    However, unordered_maps are still useful in some scenarios where speed matters and hash collisions are unlikely or impossible. For example, on LeetCode or when dealing with permutation arrays, you can use unordered_map without worries.

    → Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Your approach is very right the only thing is that u have used an unordered_map which is very slow in searching just use map instead of unordered_map it will get accepted.

Here is the submission id for modified version of your code : 247486165

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Same I also got TLE because of unordered_map as ai can range upto 2^31 which is more than 1e5 and in worst case scenario due to collisions unordered_map can take O(n). So use map in larger range as it guarantees log(n) in worst case.

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Got it. Thank you guys !!

→ Reply