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

Обсуждение задачи 1790. В поисках Истины

Easy solution
Послано Alexander Georgiev 18 окт 2010 22:34
Interestingly enough the problem can be solved with simple simulation. Just simulate the process, choosing random directions and random initial positions while you are within the time limit and you will get accepted.
I really doubt this is the correct solution, so I was wondering what is the real one?
Re: Easy solution
Послано Vedernikoff Sergey (HSE: АОП) 19 окт 2010 05:22
There is very simple O(m) solution - just use your algorithm for solution of previous problem.
Re: Easy solution
Послано KALO 20 окт 2010 04:37
I've got WA#9.
My algo is:
first I generate the possible answers in both directions (strating from 1 and n) with algorithm from the previous problem, and with KMP I'm searching the input array for match, also I added special cases for 2 (1 1 and 2 2) and for 3 (2 2).

Edited by author 20.10.2010 04:44
Re: Easy solution
Послано [Ural SU] GetTester 20 окт 2010 16:37
To Alexander Georgiev:
now your solution gets wa51. do you happy? :)

Edited by author 20.10.2010 16:37
Re: Easy solution
Послано [Ural SU] GetTester 20 окт 2010 16:58
To KALO:
Try this test
5 10
1 2 3 4 5 1 2 3 4 5
Re: Easy solution
Послано Oleg Strekalovsky [Vologda SPU] 20 окт 2010 17:00
Yep.
It is interesting - how many brute force solutions fail after new tests :)
Re: Easy solution
Послано Alexander Georgiev 20 окт 2010 17:00
Sort of =) NOW I have to write a real solution :)
Re: Easy solution
Послано Oleg Strekalovsky [Vologda SPU] 20 окт 2010 17:02
[Ural SU] GetTester писал(a) 20 октября 2010 16:58
To KALO:
Try this test
5 10
1 2 3 4 5 1 2 3 4 5
If N is odd = then sequence are
1..N 1..N
2..N-1 N-1
else the sequence is 2..N-1 N-1.. 2
I'm right?

Edited by author 20.10.2010 17:04
Re: Easy solution
Послано [Ural SU] GetTester 20 окт 2010 17:21
I don't understand you. As I know, jury's solution don't use misterious knowledges about any sequences. =)
Re: Easy solution
Послано Vedernikoff Sergey (HSE: АОП) 20 окт 2010 19:31
O(m) solution doesn't use them as well =)
No, I was talking about general logic of my algorithm. Of course, it is incorrect to search for some predefined sequence in the answer. For example, for m=5 general algorithm gives
sequence like 1 2 3 4 5 1 2 3 4 (or something like that), but possible answer is 2 2 4 4 4 4 3 2.
Re: Easy solution
Послано Ibragim Atadjanov (Tashkent U of IT) 20 окт 2010 22:35
if m = 5, 2 2 4 4 4 4 3 2 can't be the answer
imagine original is on 4th pedestal

you touch 2 orig move 4 -> 3
you touch 2 orig move 3 -> 2
you touch 4 orig move 2 -> 3
you touch 4 orig move 3 -> 2
you touch 4 orig move 2 -> 3
you touch 4 orig move 3 -> 2
you touch 3 orig move 2 -> 3
you touch 2 orig move 3 -> 4

you didn't catch the orig!

if the sequence has 2 * k numbers suquencially you can
take only 2 if 2 * k - 1 you can take 1 (I think)

example  2 2 2 2 3 3 3 5 6 --> 2 2 3 5 6

Edited by author 20.10.2010 22:39
Re: Easy solution
Послано svr 25 окт 2010 14:06
Idea:
Game of two person
and bacward analysis from the end
Example:
3 3
1 2 3
3: 1,2-win; 3- fail
2:1,3-win(1->2,3->2) 2- fail
1:2-win(2->1)1,3-fail
so win:2->1->2


Edited by author 25.10.2010 14:41
Re: Easy solution
Послано Ibragim Atadjanov (Tashkent U of IT) 27 окт 2010 02:05
I understand ur algo but I think it's O(n*m). Isn't It? Won't it get TL
Re: Easy solution
Послано svr 27 окт 2010 09:50
Yes. But pattern of failed states exits and it's maitaining costts O(1) on eaxh of n steps.
Re: Easy solution
Послано Ibragim Atadjanov (Tashkent U of IT) 27 окт 2010 17:07
what if n = 10^5 and m = 10^5
sequence is like this 4 6 4 6 4 6 4 6 4 6 . . .
I think at this test the length of failed pattern is 1 all the time and time is O(n, m) again. Or I didn't understand your previous massage rightly?