|
|
| Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения | | For those who have WA#6 | zhangweilst | 1606. Слалом | 29 ноя 2015 11:15 | 1 | This is when there's only one pole.
1
1 2
The answer should be:
1
1 | | If you have WA 3 | Alexey Dergunov [Samara SAU] | 1606. Слалом | 13 июл 2012 14:41 | 1 | Try this test:
4
4 4
1 3
2 2
3 1 | | What answer on this test? | r1d1 | 1606. Слалом | 5 июл 2011 11:06 | 2 | 3
2 1
2 3
2 4
This sample correct?
Edited by author 14.07.2010 13:02 yes, it is correct. for both of samples below answer is 1 (anyone of poles)
3
1 2
3 2
4 2
3
2 1
2 3
2 4 | | Problem 1606 "Slalom". TL is decreased to 1 sec. (-) | Sandro (USU) | 1606. Слалом | 4 янв 2011 16:07 | 1 | | | WA #6 | Dimitar Dimitrov | 1606. Слалом | 20 июл 2009 00:21 | 1 | WA #6 Dimitar Dimitrov 20 июл 2009 00:21 Any idea what is that test case ? | | Some of u, AC'rs, had WA12, don't u? (-) | AlMag(VNTU) | 1606. Слалом | 24 апр 2009 13:32 | 2 | | | are there inaccuracy conditions?.. | kavolorn | 1606. Слалом | 14 июл 2008 13:52 | 3 | I think there is inaccuracy in conditions. I answer the first example 2 5 1 3. Why is not it correct?
Edited by author 02.03.2008 12:04 2 5 1 3 - is it correct.
Edited by author 14.07.2008 22:50 | | How many test cases are there? | obtuseSword | 1606. Слалом | 19 апр 2008 00:28 | 9 | I've got TLE at Test#10,so I want to know how many test cases there are.
If there are only near 10 cases,I'll improve on my program,or else,I'll give it up.
Who can help me? I suppose there are much more than 10 testcases. My solution works about 0.1 sec on any test, so timelimit is quite enough. Try to create quicker algo... Thank you.
I've found that greedy algorithm can solve this problem,thus no longer need dynamic progrmming.
And I've got AC. Can you tell me your greedy algorithm? Greedy? Please tell us your idea. I think that "greedy" here is terminologic mismatch.
Right termin is "simple constructive" algo.
Candidat to optimum easy to find simply tracing
trajectory of all points sorted by y- coordinate. Not mismatch at all. The simplest way to solve the problem is to find a greedy algo. I solved it with DP+date structure like "the stars" task.
0.578 sec, 44 896 КB...
How to solve it with greedy algo? Data structure i used is Binary Index Tree |
|
|
|
