Discussion @ 2072. Kirill the Gardener 3 @ Timus Online Judge

👑TIMOFEY👑 easy bfs // Problem 2072. Kirill the Gardener 3 24 Aug 2022 15:20

Abid_Jawad wa 11 [1] // Problem 2072. Kirill the Gardener 3 12 Apr 2020 20:07

zhuangqf W11 [5] // Problem 2072. Kirill the Gardener 3 4 Nov 2015 17:51

Mahilewets Nikita [BSUIR] It was hard to solve // Problem 2072. Kirill the Gardener 3 3 Sep 2017 17:01

zlo WA 12 // Problem 2072. Kirill the Gardener 3 29 Jun 2017 01:31

esbybb what is the answer on ..? 15757 or 16364? thanks! [3] // Problem 2072. Kirill the Gardener 3 25 Nov 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] // Problem 2072. Kirill the Gardener 3 26 Nov 2015 13:03

16364

esbybb Re: what is the answer on ..? 15757 or 16364? thanks! [1] // Problem 2072. Kirill the Gardener 3 27 Nov 2015 02:15

thanks

Combatcook Re: what is the answer on ..? 15757 or 16364? thanks! // Problem 2072. Kirill the Gardener 3 12 Mar 2017 14:58

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

vnikulin O(N^2) [7] // Problem 2072. Kirill the Gardener 3 22 Oct 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] // Problem 2072. Kirill the Gardener 3 22 Oct 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) // Problem 2072. Kirill the Gardener 3 23 Oct 2015 18:14

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

Jane Soboleva (SumNU) Re: O(N^2) [4] // Problem 2072. Kirill the Gardener 3 22 Oct 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] // Problem 2072. Kirill the Gardener 3 22 Oct 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) // Problem 2072. Kirill the Gardener 3 5 Nov 2015 18:26

.

Edited by author 05.11.2015 18:28

luoxl9 Re: O(N^2) // Problem 2072. Kirill the Gardener 3 7 Nov 2015 13:31

...

Edited by author 07.11.2015 13:32

esbybb Re: O(N^2) // Problem 2072. Kirill the Gardener 3 27 Nov 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)

Discussion of Problem 2072. Kirill the Gardener 3