I did hashing by modifying value of matrix i.e. a[i][j] was changed to :
[a[i][j] | its row in kk matrix | its column in kk matrix] then after getting this value I calculated hash and used the same map method, it passes time limit but gives WA. Is it because of collision in hashing ?
Solution : CodeChef: Practical coding for everyone
I strongly agree with @aryan403 , this type of copy paste is not allowed and should be strongly discouraged. BTW, I messed this problem completely. But the point here is that solution should not be available on net, actions need to be taken.Can someone provide a solution to this?
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. 
No. It is mentioned on the contest page whether laddus are kept as prize for a given contest or not.
1 Like
You can read about it here :
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 : CodeChef: Practical coding for everyone
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.