vinayaka's blog

By vinayaka, history, 3 months ago, In English

Hello, I'm trying to solve the problem movie festival II on cses problemset.

This is my code

My code

It gives AC on 9 cases and WA on 4.

This is success code from USACO Guide forum.

Success code

What am I doing wrong? Isn't set.upper_bound comparison same and in mine? Can anyone help in writing success PQ code?

Full text and comments »

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

By vinayaka, history, 5 months ago, In English


My knowledge on String algorithms is poor so I am studying it now.

I solved 271D - Хорошие подстрочки using a Trie, but I am trying to solve it using hashing.

I am able to calculate a polynomial rolling hash and compare substrings based on the hash, but my solution is getting WA on test 8 (230797737). I am thinking this is because of collisions, since the expected answer is also pretty high.

I read a topic on double polynomial rolling hash to reduce probability of collisions. I understand that if we use two hashes of order 10^9 then probability will be less because it is equivalent to using a 10^18 modulo.

I am unable to understand how to implement it.

Can anyone help?

Please point me towards an article/blog/submission that has code on implementing it.

Thank you.

Full text and comments »

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