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

Обсуждение задачи 1517. Свобода выбора

Страницы: 1 2 3 Следующая
Just curious
Послано Ivan Ivanov 16 дек 2006 18:14
Just curious did anyone managed to pass the time limit
using binary search + rolling hash or the test data are
specially designed to be solved in time only by an efficient suffix tree/array implementation?
Re: Just curious
Послано Bruce Merry 16 дек 2006 18:16
I tried an O(N.log N) suffix array (although finding the length of a match was O(N.log N.log N)) and it was too slow, although it ran in about 1.3s on my machine.
Re: Just curious
Послано Nick J 16 дек 2006 18:23
Test 10 was very hard for binary+hash solutions,but
double or triple hash would pass it.
Several hash-based solutions got AC (+)
Послано Dmitry 'Diman_YES' Kovalioff 16 дек 2006 18:36
These solutions are correct, because the test set was really hard. The solutions of the authors are based on suffix trees (Nikita Rybak, Pascal) and suffix arrays (Ilya Grebnov, Java) and pass the TL easily.
Re: Several hash-based solutions got AC (+)
Послано Ivan Ivanov 16 дек 2006 22:52
Thank you Dmitry!
It seems that pretty soon Ukkonen and/or efficient suffix array implementations
will become a must in real time contests.
I would like to congratulate the autors for the excellent problem set!
Re: Several hash-based solutions got AC (+)
Послано Deftone 17 дек 2006 07:40
Single hash-based solution got AC too
Re: The solutions of the authors are based on suffix trees and suffix arrays
Послано Burunduk1 17 дек 2006 16:22
Why not suffix automaton?
It is much easier to implement and, of course, gets AC =)
Re: Several hash-based solutions got AC (+)
Послано Nick J 18 дек 2006 13:39
I got AC with optimized single hash-based solution too. But if
I wrote double hash based solution I wouldn't have +9.
Re: Several hash-based solutions got AC (+)
Послано CHN_XT 22 дек 2006 11:45
I got TLE on #28, with single hash solution.
Re: I got TLE on #28, with single hash solution.
Послано Burunduk1 22 дек 2006 13:28
The simplest solution with single hash gets AC in 0.468
Re: I got TLE on #28, with single hash solution.
Послано Ilya Grebnov[Ivanovo SPU] 22 дек 2006 15:33
Some statistics:
  0. Suffix Automaton get AC in C++ 0.125 time and 22 320 KB Memory, author is [SPbSU ITMO] WiNGeR
  1. Suffix Automaton get AC in C++ 0.14c with 22220КБ Memory, author is Burunduk1
  3. Suffix Tree gets AC in 0.14 time and 23 888 KB Memory, author is [SPbSU ITMO] WiNGeR
  4. Suffix Array with O(N) implementation get AC in C++ 0.343c with 5756 КБ Memory, author is me
  5. Single Hash get AC in C++ 0.39c with 4024 КБ Memory, author is me
  6. Single Hash get AC in Pascal 0.5c with 6191 КБ Memory, author is me
  7. Suffix Tree get AC in Pascal 0.656c with 16416 КБ Memory, author is Kit(Vologda SPU)
  8. Suffix Array with O(NLogN) implementation get AC in C++ 0.765c with 2756КБ Memory, author is me
  9. Suffix Array with O(NLogN) implementation get AC in Java 1.406c with 5503КБ Memory, author is me

Edited by author 22.12.2006 15:35

Edited by author 25.12.2006 11:24

Edited by author 11.02.2007 13:44

Edited by author 11.02.2007 13:45

Edited by author 11.02.2007 13:45
Re: I got TLE on #28, with single hash solution.
Послано EfremovAleksei 22 дек 2006 16:05
I write Suffix Tree(Ukkonen Algorithm).
AC - 1 sec.
But I used 30mb memory.
Re: Several hash-based solutions got AC (+)
Послано Kit 22 дек 2006 16:15
Actually, not any hash is suitable here.
I got MLE, TLE on test #9, WA on test #8 :(
Послано Felix Halim 23 дек 2006 09:37
I tried to solve this problem using Suffix Tree (ukkonen95) and got MLE on test #9, what trick did you use to reduce the memory?

Then I saw this discussion about Suffix Array, I tried Larsson-Sadakane algorithm and got WA on test #8. Then I tried Karkkainen-Sanders algorithm and got TLE on test #9.

I haven't try to use Suffix Automaton yet.

This problem is really hard. Anyone can give hints about reducing memory for the Suffix Tree?
Re: I got MLE, TLE on test #9, WA on test #8 :(
Послано Kit 23 дек 2006 12:09
Felix Halim писал(a) 23 декабря 2006 09:37
I tried to solve this problem using Suffix Tree (ukkonen95) and got MLE on test #9, what trick did you use to reduce the memory?
No tricks, I have almost double reserve in memory. But I use hash working with edges, may be that's the matter.
Test #8 is extremally small, so you can find similiar manually.
#9 is just the first large test.
Good luck!
Re: I got MLE, TLE on test #9, WA on test #8 :(
Послано EfremovAleksei 23 дек 2006 17:18
>This problem is really hard. Anyone can give hints about >reducing memory for the Suffix Tree?

I also had MLE#9, after that I saved at node of suffix tree only used links to child And got AC.

It reduced memory, but I my prog eat 30mb.
Re: I got MLE, TLE on test #9, WA on test #8 :(
Послано Felix Halim 23 дек 2006 22:18
Those who solved it using Suffix Trees:

Did you built 2 Suffix Trees or just 1?

What I did is to create 1 Suffix Tree with string: s1 + "$" + s2 + "#"  where s1 and s2 is the first and second string in the input. After I built the Suffix Tree, I traversed it and find the deepest node which has child "$" and "#".

Or is it better to create 2 Suffix Trees and compare the two trees?

Or there is a way to build a Suffix Tree only for the first string and try to find the LCS with the second string using that Tree.

Did you get AC using the first algorithm? second? or the last? Thanks
First way (-)
Послано Kit 24 дек 2006 10:52
Re: First way (-)
Послано Ngô Minh Đức 25 дек 2006 17:48
I use hashing but my algorithm is O(n(logn)^2), is it a better way?
Here is my algorithm:
m = the result
l = length(m)
- Do a binary search on l
Check whether there is a common substring length l:
+ Calculate and sort hash values of string 1 (into array f)
+ For each value in string 2, search it in f, check whether
there is a match!
Re: First way (-)
Послано Vedernikoff Sergey 25 дек 2006 22:12
What is double hash???

My single hash O(N*logN) prog. got AC within 0.671 sec. and 6,... MB memory.
Страницы: 1 2 3 Следующая