ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

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

Judges, does solution exist for JAVA?
Послано Smog 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?
Re: Judges, does solution exist for JAVA?
Послано [SPbSU ITMO] WiNGeR 7 апр 2007 23:58
There is a much simplier solution with the same complexity, and with less constant
Re: Judges, does solution exist for JAVA?
Послано Igor Dex 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?
)
Re: Judges, does solution exist for JAVA?
Послано Bohdan Istrashkin 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...
Re: Judges, does solution exist for JAVA?
Послано Lomir 24 ноя 2007 23:51
There is much faster O(n) check.
Just one for and some if.
However i write in CPP :)
Re: Judges, does solution exist for JAVA?
Послано [SPbSU ITMO] Kazakov Sergey (CK.) 22 ноя 2008 00:24
YES!!!