chokudai's blog

Toyota Programming Contest 2023 Spring Qual A（AtCoder Beginner Contest 288） Announcement
By chokudai, history, 2 months 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

»
2 months 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.

→ Reply
  • »
    »
    2 months 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

    → Reply
  • »
    »
    2 months 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.

    → Reply
»
2 months 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 ?

→ Reply
»
2 months 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.

→ Reply
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Could you please explain the burnside lemma solution?

    → Reply
»
2 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Japan has a different definition for "beginner"

→ Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it 
First I didn't see r-l+1>=k. I thought it was yet another irritating array corner problem.
Then I thought it is kind of modulo sum, then all remainders in range should should be multiple of K except 
zero
After so much time, thought to see in lens of math,
Then I thought it might be of diff array technique. No luck I couldn't get any ideas.
→ Reply
»
2 months 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?

→ Reply
  • »
    »
    2 months 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

    → Reply
    • »
      »
      »
      2 months 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!

      → Reply
»
2 months 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
→ Reply
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Same. My laptop hanged and I couldn't submit for starting 5 mins (had to force reboot). Only had read problem A by then. 😢

    → Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    2 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    It's exactly 2000

    → Reply
    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How is it calculated?

      Does it mean 2000 rated person can solve with 50% chance A to E in 100 minutes? Or is it that they can solve E in 100 minutes?

      → Reply
      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I don't know the exact calculation. It's something along the lines of 2000 rated person can solve it with 50% chance (for a problem rated 2000). The timing doesn't matter. If you check on kenkoooo though, they show solve time when you hover on problem circle. My guess is that they take average of time taken to solve E by all those who solved that problem in contest (don't know if those people are considered for whom the contest is unrated (either by choice or due to rating >=2000), after the previous AC on some other problem (or just first AC time for E, if E is solved first in contest).

        → Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Damn, I missed this and was wondering why some people in my standings(that usually do rated register) has registered in unrated mode. Will keep an eye out for this thing in the second qualification round (B) of Toyota ABC later this month.

    → Reply
»
2 months 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:

→ Reply