I make O(n^2*z) (z - time for updating hash table) algo to check if exist equal squares of some k-size. Then I make binary search by k. So complecity in worth case is O(n^3*log n) - so that is bad... But what to do - some ideas?.. Maybe goodhash function or doublize it, or there is much different approach?

Only thing you need is z = O(1).

Edited by author 15.02.2007 22:43

Hash-based solution can be applied easily in O(N^2*logN). Even not very good hash can get AC because of weak tests for this problem...

What 'not very good' hash you mean? Can you describe it?

Pasha, if you accept this ...
help me to do this too!
   Good Luck!

     Chobit'my jiji, chobit'my!!!

I have f..ed this problem!
I did this problem the same as you did.
my Modulo in hash table = 999983.