chokudai's blog

By chokudai, history, 21 month(s) ago, In English

We will hold Toyota Programming Contest 2023 Spring Qual A(AtCoder Beginner Contest 288).

The point values will be 100-200-300-400-500-500-600-600. Since this contest is used as a qualification round for a local event, the style of problems is modified a bit.

  • Up to task C is usual.
  • (the style of tasks D-Ex in this contest) is between (the style of tasks D-Ex in usual ABC) and (the style of earlier tasks in usual ARC).
  • Tasks in the middle of this contest are slightly harder than usual. Later tasks are not too difficult.

We are looking forward to your participation!

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

| Write comment?
»
21 month(s) ago, # |
Rev. 2   Vote: I like it +4 Vote: I do not like it

How to do problem D?
IMO problem D is of higher difficulty than usual one.

  • »
    »
    21 month(s) ago, # ^ |
    Rev. 2   Vote: I like it +11 Vote: I do not like it

    yep it was harder..

    I solved it with some maths intuition. After a lot of case work I found that

    For a sequence of $$${[L, R]}$$$ should be good if and only if.

    $$${A_i + A_{i - k} + A_{i - 2 * k} + .... A_p - A_{i - 1 - k} - A_{i - 1 - 2 * k} - .... A_{p-1} = 0}$$$

    where $$${p < L}$$$ and $$${L \le p + k}$$$.

    for all $$$i$$$, $$${R - k + 2 \le i \le R}$$$

    My Submission

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    According to Kenkoooo Atcoder Problems, ABC288D may be the second Problem D (in 8 problems rounds) that difficulty is above 1600. It is even harder than the first one ABC227D. But I think that ABC288 is easier than ABC227 on the whole.

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

It looks like E is dp but i don't know how to solve it. Where can i find problems like this ?

»
21 month(s) ago, # |
Rev. 2   Vote: I like it +52 Vote: I do not like it

screencast

For problem Ex, the solution in the editorial is a bit complicated. You can simply consider using the burnside lemma for all permutations on all $$$n$$$ numbers.

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Could you please explain the burnside lemma solution?

»
21 month(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

Japan has a different definition for "beginner"

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

I know E is Dp but can't figure out states. Someone please Explain?

  • »
    »
    21 month(s) ago, # ^ |
    Rev. 2   Vote: I like it +6 Vote: I do not like it

    The key observation in $$$E$$$ is that if we bought $$$2$$$ items $$$i$$$ and $$$j$$$ ($$$i<j$$$), then for $$$i$$$ it will not matter whether we buy it before or after $$$j$$$, but for $$$j$$$ it will matter because if we bought $$$j$$$ first, we would use $$$C[j]$$$, otherwise we would use $$$C[j-1]$$$.

    So let $$$dp[i][j]$$$ be the least amount of money we can spend if we start from item $$$i$$$ and we bought $$$j$$$ items with indexes less than $$$i$$$. If item $$$i$$$ is not in $$$X$$$ we can consider the option of not buying it. For the other option of buying it, we can buy it first before buying any of the $$$j$$$ items (will use $$$C[i]$$$), or we can buy it after buying $$$1$$$ of the $$$j$$$ items (will use $$$C[i-1]$$$), and so on.

    So, we can have an array $$$mins$$$ where $$$mins[i][j]$$$ is the smallest $$$C[k]$$$ for $$$j\le k\le i$$$. So when we want consider buying item $$$i$$$ if we bought $$$j$$$ items with indexes less than $$$i$$$, we can set $$$dp[i][j] = min(dp[i][j], a[i]+mins[i][i-j]+dp[i+1][j+1])$$$.

    Submission

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you so much for your detailed explanation of problem E. I have got the definition of states and transition formula, but missed that mins[i][i-j] part, while I used C[i-j] instead.

      Your words "we can buy it first before buying any of the j items, or we can buy it after buying 1 of the j items and so on" really helps me a lot. Thank you!

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Missed D by 5 mins, rip ratings...
Tip: Never start a contest late, and that too by 5 mins.

Spoiler
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

What??? The difficulty of E is above 2000?????????

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

They had warned us friends : https://atcoder.jp/posts/975

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Broo, I had some stupid bug in my code for E and couldn't fix it in time. After contest I realized that I could've easily got F had I tried :sad: