Обсуждение @ 2072. Садовод Кирилл 3 @ Timus Online Judge

👑TIMOFEY👑 easy bfs // Задача 2072. Садовод Кирилл 3 24 авг 2022 15:20

Abid_Jawad wa 11 [1] // Задача 2072. Садовод Кирилл 3 12 апр 2020 20:07

zhuangqf W11 [5] // Задача 2072. Садовод Кирилл 3 4 ноя 2015 17:51

Mahilewets Nikita [BSUIR] It was hard to solve // Задача 2072. Садовод Кирилл 3 3 сен 2017 17:01

zlo WA 12 // Задача 2072. Садовод Кирилл 3 29 июн 2017 01:31

esbybb what is the answer on ..? 15757 or 16364? thanks! [3] // Задача 2072. Садовод Кирилл 3 25 ноя 2015 07:48

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

rip&pvs Re: what is the answer on ..? 15757 or 16364? thanks! [2] // Задача 2072. Садовод Кирилл 3 26 ноя 2015 13:03

16364

esbybb Re: what is the answer on ..? 15757 or 16364? thanks! [1] // Задача 2072. Садовод Кирилл 3 27 ноя 2015 02:15

thanks

Combatcook Re: what is the answer on ..? 15757 or 16364? thanks! // Задача 2072. Садовод Кирилл 3 12 мар 2017 14:58

This test is incorrect, because all a[i]>0.

vnikulin O(N^2) [7] // Задача 2072. Садовод Кирилл 3 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.

Axenick Re: O(N^2) [1] // Задача 2072. Садовод Кирилл 3 22 окт 2015 15:37

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

vnikulin Re: O(N^2) // Задача 2072. Садовод Кирилл 3 23 окт 2015 18:14

Yes. I thought it is 10^4. I was neglectful.

Jane Soboleva (SumNU) Re: O(N^2) [4] // Задача 2072. Садовод Кирилл 3 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...

Felix_Mate Re: O(N^2) [2] // Задача 2072. Садовод Кирилл 3 22 окт 2015 18:47

Hello! I solved this problem O(N*logN). Idea=Sort+Dp[i,x],where x=the most Right and the most Left

algo13354165 Re: O(N^2) // Задача 2072. Садовод Кирилл 3 5 ноя 2015 18:26

.

Edited by author 05.11.2015 18:28

luoxl9 Re: O(N^2) // Задача 2072. Садовод Кирилл 3 7 ноя 2015 13:31

...

Edited by author 07.11.2015 13:32

esbybb Re: O(N^2) // Задача 2072. Садовод Кирилл 3 27 ноя 2015 04:50

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)

Обсуждение задачи 2072. Садовод Кирилл 3