maroonrk's blog

AtCoder Grand Contest 048 Announcement
By maroonrk, history, 4 years 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
  • +261
  • Vote: I do not like it

Comments Comments (18)
| Write comment?
»
4 years 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?

→ Reply
  • »
    »
    4 years 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

    → Reply
    • »
      »
      »
      4 years 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.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
        ← Rev. 2   Vote: I like it +19 Vote: I do not like it

        Then who will set problems ?

        Btw if you are serious, you need help dude

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it +11 Vote: I do not like it

          He will set the problems and then solve them. I don't see a problem.

          → Reply
          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
              Vote: I like it +5 Vote: I do not like it

            you won't see a problem because he only exists.

            → Reply
»
4 years 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!

→ Reply
»
4 years ago, # |
  Vote: I like it +60 Vote: I do not like it

Amazing contest, congratulations to the authors.

→ Reply
»
4 years 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
→ Reply
»
4 years 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?

→ Reply
  • »
    »
    4 years 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"

    → Reply
  • »
    »
    4 years 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.

    → Reply
    • »
      »
      »
      4 years 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.

      → Reply
      • »
        »
        »
        »
        4 years 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

        → Reply
»
4 years 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.

→ Reply
  • »
    »
    4 years 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.

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +18 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.

    → Reply