Блог пользователя formidablechief27

Автор formidablechief27, история, 7 месяцев назад, По-английски

I was solving this question 1731C - Even Subarrays

I was getting TLE on test 2 until i decided to have a look a at the editorial Editorial suggested an n root n complexity answer => 186975655

which then i implemented the same in java and 237133047

i felt maybe hash map collisions could lead to this, so i tried with trie data structure as well that didnt even cross test 3

  • Проголосовать: нравится
  • -6
  • Проголосовать: не нравится

»
7 месяцев назад, # |
  Проголосовать: нравится +30 Проголосовать: не нравится

The C++ submission you linked does not use any hashmap. It just uses a couple of vectors.

»
7 месяцев назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

Instead of hashmaps you should use arrays. Note that $$$a_i \leq n$$$, now we can use the fact that xor of a set of elements $$$\leq n$$$ is $$$\leq 2^{\lfloor \log n \rfloor + 1} - 1$$$.

So if you use an array of size $$$2^{\lfloor \log n \rfloor + 1}$$$ you would be safe. (in the official solution they have used $$$2n$$$ which is $$$> 2^{\lfloor \log n \rfloor + 1} - 1$$$).

Hashmaps are usually quite slow and take a lot of constant time, in fact some people who tried to use unordered_map of c++ also got TLE (you can see the editorial comment section).