Обсуждение @ 1486. Одинаковые квадраты @ Timus Online Judge

PSV TLE10 [5] // Задача 1486. Одинаковые квадраты 26 дек 2006 06:00

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?

Kit Re: TLE10 [2] // Задача 1486. Одинаковые квадраты 15 фев 2007 22:40

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

Edited by author 15.02.2007 22:43

Vedernikoff Sergey Re: TLE10 [1] // Задача 1486. Одинаковые квадраты 19 фев 2007 15:21

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...

Kit Re: TLE10 // Задача 1486. Одинаковые квадраты 19 фев 2007 16:44

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

R13 Re: TLE10 // Задача 1486. Одинаковые квадраты 28 апр 2007 21:06

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

Chobit'my jiji, chobit'my!!!

R13 Re: TLE10 // Задача 1486. Одинаковые квадраты 28 апр 2007 22:14

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

Обсуждение задачи 1486. Одинаковые квадраты