We will hold Toyota Programming Contest 2023 Spring Qual A（AtCoder Beginner Contest 288）.

- Contest URL: https://atcoder.jp/contests/abc288
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20230204T2100&p1=248
- Duration: 100 minutes
- Number of Tasks: 8
- Writer: leaf1415, cn449, chokudai, nok0, PCTprobability, m_99
- Tester: kyopro_friends, math957963
- Rated range: ~ 1999

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!

How to do problem D?

IMO problem D is of higher difficulty than usual one.

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

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.

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

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.

Could you please explain the burnside lemma solution?

Japan has a different definition for "beginner"

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

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

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!

can you provide your submission link

Sir Do you solved E by now ?? If you do Please share the solution sir.

Yes, I get AC after contest, and here is my submission, and I have added detailed explanation as much as I can, https://atcoder.jp/contests/abc288/submissions/38635406

But, my definition of j is different from above, and mine denotes the number of unsold items.

Missed D by 5 mins, rip ratings...

Tip: Never start a contest late, and that too by 5 mins.

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

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

It's exactly 2000

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?

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).

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

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.

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: