We will hold AtCoder Grand Contest 048. This contest counts for GP30 scores.
- Contest URL: https://atcoder.jp/contests/agc048
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20201018T2100&p1=248
- Duration: 150 minutes
- Number of Tasks: 6
- Writer: maroonrk, sugim48
- Tester: latte0119, reew2n
- Rated range: 1200 — inf
The point values will be 300-700-700-900-1500-2200.
We are looking forward to your participation!
Isn't it at the same time as KickStart? Or are all the time zones confusing me?
Yea timezones suck, life would have been much easier if earth had just been flat
Life would be much easier if only I existed, all those things and other people just make my life complicated.
Then who will set problems ?
Btw if you are serious, you need help dude
He will set the problems and then solve them. I don't see a problem.
you won't see a problem because he only exists.
Can you give me some hints for problem D. Thank you very much!
Amazing contest, congratulations to the authors.
Thanks for the participation!
Since the editorial of F has not been translated yet, I'll leave some hints here.
Consider the maximum value in the original numbers.
Consider the maximum sum of the largest K numbers among the original numbers.
Consider the maximum number of '0's and '1's coming from the largest K numbers.
Well, sometimes, a necessary condition turns out to be sufficient.
Anyone's got any proof for why in D it's optimal to only take one rock or the whole pile at a time?
We only need to know "how many turns player take leftmost/rightmost pill before it disappear"
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.
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.
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 doa[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:00For 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.
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.
In C, it seemed inconvenient to me that penguins on consecutive positions create a block. I applied
a[i] -= ifor every penguin so that a block would be just penguins with the same position. This is equivalent to changing penguin width to 0.Big brain :o