Обсуждение @ 1532. Трудности перевода @ Timus Online Judge

Smog Judges, does solution exist for JAVA? [5] // Задача 1532. Трудности перевода 5 апр 2007 22:04

I've got TLE on 7st test.

I use Ukkonen algorithm for comparing pairs of strings (it does O(2*m) time) and O(n*(n+1)/2) for excess all pairs.
So, it must be O((5000+1)*2500*15*2) time.

Isn't it enough?

[SPbSU ITMO] WiNGeR Re: Judges, does solution exist for JAVA? [1] // Задача 1532. Трудности перевода 7 апр 2007 23:58

There is a much simplier solution with the same complexity, and with less constant

Igor Dex Re: Judges, does solution exist for JAVA? // Задача 1532. Трудности перевода 3 июл 2007 02:50

To [SPbSU ITMO] WiNGeR :
Do you use any input filters before an algorithm of O(n^2)?
(For example
The difference in the length of compared words mustn't be more than 2.
Sets of symbols of two words cann't consist of more than 4 different symbols.
Or anything else?
)

Bohdan Istrashkin Re: Judges, does solution exist for JAVA? [2] // Задача 1532. Трудности перевода 23 ноя 2007 23:49

Mine solution is almost same... get's TLE on 6th test.
I've tried that "dirty" tricks (as length checking) before difference calcultion beetwen words.
It seems that it's unsolvable on JAVA (noone has got AC in JAVA, i watched :) )
Mb will write same on CPP...

Lomir Re: Judges, does solution exist for JAVA? [1] // Задача 1532. Трудности перевода 24 ноя 2007 23:51

There is much faster O(n) check.
Just one for and some if.
However i write in CPP :)

[SPbSU ITMO] Kazakov Sergey (CK.) Re: Judges, does solution exist for JAVA? // Задача 1532. Трудности перевода 22 ноя 2008 00:24

YES!!!

Обсуждение задачи 1532. Трудности перевода