Invitation to Alkhwarizm 2018 (Rated)

First of all, I think your solution should give TLE as it is O((nnn*n )/16) for the case when k = n/2. You got WA because even in small test case your code isn’t giving a correct answer. I think it is because of the collision in hashing as your mod value is small and your hash is not strong enough.

Read more about Hashing here : https://threads-iiith.quora.com/String-Hashing-for-competitive-programming

It is not giving TLE, just WA.Can you suggest changes in my code ? What mod value should I use. My hashing function is based on this post Link:https://discuss.codechef.com/questions/101218/how-to-solve-clonemejune17-for-30-and-100-pts

Your solution is not giving TLE because you are getting WA on the 1st test case. Test cases with larger constraints are not being judged. But when it will be judged it will eventually give TLE.

The hashing technique mentioned in that post is good for that question because we are trying to find only 1 mismatch. But for a strong hash function you have to use a good prime value and good MOD value, maybe 2 sometimes. But with unsigned long long int data type in C++ we can allow a large range of value to be assigned as hash and less chance of collision. Go through the above post I suggested.

1 Like

laddus are credited for rated contests only ??

Thanks. :slight_smile:

No. It is mentioned on the contest page whether laddus are kept as prize for a given contest or not.

1 Like

please help me in harrywnd , applied dp using the above given expression , see my code and help:
solution , getting tle

please explain the small to large trick of merging two maps in “hedwig” problem.

You can read about it here :
http://codeforces.com/blog/entry/44351

1 Like

Two state dp with a memory complexity of O(n * k) won’t pass. Try reducing it to one state.

Look at this solution for help : https://www.codechef.com/viewsolution/18005629

Can u explain in HARRYPSS,how is the second part fib(n)? Any mathematical proof would be useful.

For the same problem(HEDWIG) can you provide a clear solution, will be greatly helpful.