ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 2072. Kirill the Gardener 3

Vadim Nikulin 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
Vadim Nikulin 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...
__Andrewy__ 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
Михаил Аршинов 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)