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.
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?
They had warned us friends : https://atcoder.jp/posts/975
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: