maroonrk's blog

By maroonrk, history, 4 days ago, In English

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!

 
 
 
 
  • Vote: I like it
  • +250
  • Vote: I do not like it

»
4 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Isn't it at the same time as KickStart? Or are all the time zones confusing me?

  • »
    »
    4 days ago, # ^ |
      Vote: I like it +29 Vote: I do not like it

    Yea timezones suck, life would have been much easier if earth had just been flat

    • »
      »
      »
      4 days ago, # ^ |
        Vote: I like it +30 Vote: I do not like it

      Life would be much easier if only I existed, all those things and other people just make my life complicated.

»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you give me some hints for problem D. Thank you very much!

»
3 days ago, # |
  Vote: I like it +60 Vote: I do not like it

Amazing contest, congratulations to the authors.

»
3 days ago, # |
  Vote: I like it +18 Vote: I do not like it

Thanks for the participation!

Since the editorial of F has not been translated yet, I'll leave some hints here.

Spoiler
Spoiler
Spoiler
Spoiler
»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Anyone's got any proof for why in D it's optimal to only take one rock or the whole pile at a time?

  • »
    »
    3 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    We only need to know "how many turns player take leftmost/rightmost pill before it disappear"

  • »
    »
    3 days ago, # ^ |
      Vote: I like it +61 Vote: I do not like it

    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.

    • »
      »
      »
      7 hours ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      • »
        »
        »
        »
        6 hours ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        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

»
36 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    7 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

  • »
    »
    6 hours ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    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.