### maroonrk's blog

By maroonrk, history, 11 months ago,

We will hold AtCoder Grand Contest 048. This contest counts for GP30 scores.

The point values will be 300-700-700-900-1500-2200.

We are looking forward to your participation!

• +261

 » 11 months ago, # |   0 Isn't it at the same time as KickStart? Or are all the time zones confusing me?
•  » » 11 months ago, # ^ |   +29 Yea timezones suck, life would have been much easier if earth had just been flat
•  » » » 11 months ago, # ^ |   +30 Life would be much easier if only I existed, all those things and other people just make my life complicated.
•  » » » » 11 months ago, # ^ | ← Rev. 2 →   +19 Then who will set problems ?Btw if you are serious, you need help dude
•  » » » » » 11 months ago, # ^ |   +11 He will set the problems and then solve them. I don't see a problem.
•  » » » » » » 11 months ago, # ^ |   +5 you won't see a problem because he only exists.
 » 11 months ago, # |   0 Can you give me some hints for problem D. Thank you very much!
 » 11 months ago, # |   +60 Amazing contest, congratulations to the authors.
 » 11 months ago, # |   +18 Thanks for the participation!Since the editorial of F has not been translated yet, I'll leave some hints here. SpoilerConsider the maximum value in the original numbers. SpoilerConsider the maximum sum of the largest K numbers among the original numbers. SpoilerConsider the maximum number of '0's and '1's coming from the largest K numbers. SpoilerWell, sometimes, a necessary condition turns out to be sufficient.
 » 11 months ago, # |   0 Anyone's got any proof for why in D it's optimal to only take one rock or the whole pile at a time?
•  » » 11 months ago, # ^ |   0 We only need to know "how many turns player take leftmost/rightmost pill before it disappear"
•  » » 11 months ago, # ^ |   +61 Well, it's kind of obvious. If you take more than 1 but not all stones from your current pile then in next move set of positions you can end up with after it is strict subset of positions you could end up with if you had taken only 1 stone.
•  » » » 11 months ago, # ^ |   0 How exactly can $left[i][j]$ and $right[i][j]$ be computed from $left[i][j-1]$ and $right[i+1][j]$, as it is said in editorial? I think, these transitions consider only those cases when current player takes the whole pile, not just one rock.
•  » » » » 11 months ago, # ^ |   +8 Let $right[i+1][j]$ denote minimum value of $a[j]$ such that second player wins. The for interval $[i,j]$ the first player can take the whole number $a[i]$ only after $a[j]$ drops to below $right[i+1][j]$. So for $d_1 = a[j]-right[i+1][j]$ turns the first player must do a[i]-- and only then he can take the whole value $a[i]$. Similarly, the second player must do a[j]-- for $d_2 = a[i]-left[i][j+1]$ turns. You can get the winning player by comparing $d_1$ and $d_2$ because this way you see which one first stops doing -- operation because he sees the opportunity to win now. If you want to watch a lengthy explanation and code, see my stream https://youtu.be/uNCnvPVsZv4 around 2:05:00
 » 11 months ago, # |   0 For problem C, does everyone use the same algorithm in the editorial? I'm wondering why you guys can come up the idea of using SPACES in between? I use a different algorithm from the editorial, which is simulating the operations with some optimization.For problem B, is it just guessing what necessary condition is sufficient condition? I feel I'm not good at this.
•  » » 11 months ago, # ^ |   0 For problem B I've started with brute force solution to see what happens for small lengths. Sometimes it can help to make useful observations, or at least to check your guess.
•  » » » 11 months ago, # ^ |   0 Same here, the observation was enough to get it done. I didn't go for brute force though, constraints indicated like a kind of sort may be necessary.
•  » » 11 months ago, # ^ |   +18 In C, it seemed inconvenient to me that penguins on consecutive positions create a block. I applied a[i] -= i for every penguin so that a block would be just penguins with the same position. This is equivalent to changing penguin width to 0.
•  » » » 11 months ago, # ^ |   -21 Big brain :o