|
|
| Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения | | easy bfs | 👑TIMOFEY👑 | 2072. Садовод Кирилл 3 | 24 авг 2022 15:20 | 1 | | | wa 11 | Abid_Jawad | 2072. Садовод Кирилл 3 | 20 апр 2020 17:13 | 2 | wa 11 Abid_Jawad 12 апр 2020 20:07 a silly mistake got me wa. A simple testcase helped me. here it is-
3
3 2 1
Edited by author 12.04.2020 20:09 | | W11 | zhuangqf | 2072. Садовод Кирилл 3 | 20 апр 2020 17:08 | 6 | W11 zhuangqf 4 ноя 2015 17:51 answer will be long or long long. Thank you!!!
That is very helpful! Appreciate your suggestions!Nearly died with laughing!!!!Fage JJ boom the sky!!! thank you very much for your suggestion!!!! | | It was hard to solve | Mahilewets Nikita [BSUIR] | 2072. Садовод Кирилл 3 | 3 сен 2017 17:01 | 1 | I have solved it only after reading Felix Mate's comment about dynamic programming approach | | WA 12 | zlo | 2072. Садовод Кирилл 3 | 29 июн 2017 01:31 | 1 | WA 12 zlo 29 июн 2017 01:31 long long at least, otherwise WA12. doesn't fit even in unsigned long | | what is the answer on ..? 15757 or 16364? thanks! | esbybb | 2072. Садовод Кирилл 3 | 12 мар 2017 14:58 | 4 | 1000
13 0 10 14 12 14 9 12 1 0 9 9 16 14 14 10 9 0 9 14 14 14 14 13 13 15 10 14 14 13 14 0 14 9 13 0 7 15 13 9 1 1 0 14 9 10 10 10 14 0 14 12 10 14 0 14 1 13 11 6 10 0 9 0 12 4 9 9 4 6 10 14 4 7 7 14 15 13 13 14 14 12 1 14 6 14 14 16 4 14 16 0 0 16 7 10 12 10 12 14 7 10 14 14 7 10 14 14 13 9 9 0 13 14 15 9 9 9 14 10 1 9 0 14 9 9 10 16 10 9 14 13 13 12 0 14 4 14 9 7 13 13 13 10 9 14 0 13 12 11 4 14 1 4 0 1 9 14 14 14 10 10 0 10 14 0 12 10 0 16 16 15 9 6 0 16 14 1 14 0 9 16 7 14 10 10 16 8 10 13 14 10 14 7 13 7 14 16 4 12 9 14 14 14 1 9 14 15 10 0 13 13 14 7 14 14 16 9 10 12 12 13 9 16 7 16 9 13 7 13 0 14 9 14 12 0 10 0 9 7 9 12 0 14 9 14 16 16 16 10 13 1 0 13 13 16 14 0 14 10 10 13 0 14 14 10 7 14 0 5 13 16 14 12 10 1 1 14 14 13 14 0 13 14 16 0 9 10 10 14 10 13 14 7 0 9 14 7 16 7 6 1 9 7 14 14 1 15 11 9 16 0 14 12 14 9 9 7 14 12 0 7 10 0 14 12 14 1 9 14 10 14 14 9 13 0 14 1 0 9 12 14 14 14 0 13 13 16 15 9 0 14 7 7 0 13 14 14 9 8 14 14 10 14 10 10 13 10 4 4 12 16 12 14 14 11 4 7 12 14 4 0 14 10 16 14 7 7 8 13 16 7 9 1 1 13 8 13 9 0 16 10 1 10 7 15 13 14 14 14 10 1 9 14 14 4 14 16 1 14 8 16 9 14 13 14 0 14 7 14 9 15 10 10 13 14 9 9 0 16 13 13 1 16 7 1 14 7 14 10 0 14 13 15 9 13 10 12 14 10 16 13 14 14 13 10 16 16 14 14 14 14 10 0 13 10 4 14 7 13 9 16 11 13 0 4 10 15 14 14 0 0 13 0 14 14 14 13 16 0 1 13 14 0 9 16 0 16 10 16 9 0 0 13 0 7 16 14 8 13 16 14 13 0 14 9 16 9 13 14 14 14 14 0 9 7 10 0 12 13 16 9 9 14 13 14 1 14 13 14 12 0 13 7 15 15 9 14 12 0 10 13 14 4 16 14 14 12 14 0 9 12 9 14 7 10 1 1 13 10 0 14 9 15 16 15 16 14 12 14 0 12 14 1 12 12 14 0 5 14 14 12 14 16 16 1 6 14 13 8 10 10 13 16 10 14 16 13 1 12 10 14 13 16 10 13 15 7 13 12 0 4 14 1 0 0 16 14 7 9 9 10 16 13 3 4 9 12 7 13 9 12 4 14 15 10 14 7 14 1 14 14 16 12 13 0 0 14 16 14 14 10 8 14 13 14 13 14 0 7 10 0 10 14 10 12 16 16 13 7 12 10 14 14 14 9 7 10 7 13 13 12 14 9 14 12 16 6 7 14 9 14 13 10 0 16 0 14 14 10 15 6 9 14 10 9 10 10 1 14 15 10 14 14 14 1 14 14 14 14 16 15 16 14 6 9 14 13 10 10 12 9 14 16 10 12 16 0 10 14 16 10 14 0 0 7 8 0 13 16 10 14 14 7 0 0 11 15 15 14 13 10 16 12 16 15 16 14 13 4 13 14 14 5 7 0 11 0 13 16 1 13 16 14 14 16 16 16 0 14 10 14 6 14 16 14 13 14 14 16 13 9 14 14 1 9 16 14 12 14 13 14 15 7 14 8 14 13 9 14 7 0 13 1 15 16 0 10 13 14 12 14 14 0 10 7 13 13 13 8 14 9 10 16 7 8 14 14 16 13 7 16 7 9 13 16 14 14 12 0 13 13 9 9 8 15 14 14 14 13 14 13 13 16 14 0 14 16 13 14 8 1 1 1 9 14 9 16 10 14 14 8 0 0 9 6 13 9 0 7 15 8 9 0 14 0 14 14 9 14 12 13 16 14 3 10 14 10 14 11 1 14 14 9 9 9 0 16 0 7 0 16 14 9 14 9 13 14 16 0 0 9 16 14 14 14 10 9 14 1 9 9 14 8 11 15 0 14 11 14 14 0 7 0 14 1 9 14 14 14 14 14 8 16 0 10 0 7 8 14 This test is incorrect, because all a[i]>0. | | O(N^2) | vnikulin | 2072. Садовод Кирилл 3 | 27 ноя 2015 04:50 | 8 | O(N^2) vnikulin 22 окт 2015 06:31 Hi.
Is O(N^2) solution good for this problem? I got TL on 8th test. Should I reduce constant in O() or should I find N*logN solution? It's strange that 25M operations take over 2 seconds. Ofc no; the max N is 10^5, so N^2 would be 10^10; thats about 50 seconds to do such number of operations on a normal PC Yes. I thought it is 10^4. I was neglectful. Re: O(N^2) Jane Soboleva (SumNU) 22 окт 2015 16:18 N^2 is almost never acceptable if N exceeds ~4000-5000.
I attempted to think a bit at this task... as far as i understood, for flowers with a certain dryness X, let us assume that the leftmost flower with such dryness is X1, the rightmost is X2, Kirill's position is Y. Cases like Y...X1...X2 and X1...X2...Y are easy, Kirill needs to go to the rightmost and to the leftmost flower respectively, but in case of X1...Y...X2 it gets a bit harder. At first, i assumed that we should just go first to the side that we're closer to, but then, i found out a counter test for that:
19
2 9 9 9 9 9 9 9 1 9 9 9 9 9 9 2 3 4 5
Initial path to the right 2, through 6 nines, is shorter than to the left 2, through 7 nines, but eventually this turns out to be a bad decision, since we have to go all the way to the right again. So probably, we should somehow take a group of flowers with next closest dryness into consideration. I'll try to think of it some more when i'm not lazy... Hello! I solved this problem O(N*logN). Idea=Sort+Dp[i,x],where x=the most Right and the most Left .
Edited by author 05.11.2015 18:28 ...
Edited by author 07.11.2015 13:32 19
2 9 9 9 9 9 9 9 1 9 9 9 9 9 9 2 3 4 5
70, btw for java AC long for path[] is enough (BigInteger works slower few milliseconds) |
|
|
|
