We will hold AtCoder Regular Contest 204 (Div. 1).
- Contest URL: https://atcoder.jp/contests/arc204
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20250817T2100&p1=248
- Duration: 150 minutes
- Number of Tasks: 4
- Writer: potato167
- Tester: Nyaan, maspy
- Rated range: 1600 ~ 2999
The point values will be 700-800-900-1000.
We are looking forward to your participation!
A more detailed explanation of Problem A:
First, split the answer as $$$f(0,R) - f(0,L-1)$$$.
Currently, we are processing the answer for $$$f(0,x)$$$. Let’s think in reverse, working backwards:
define $$$f_{i,j}$$$ as the number of valid schemes when $$$A$$$ considers $$$i \sim n$$$ and $$$B$$$ considers $$$j \sim n$$$.
Initially, at $$$(n+1, n+1)$$$, the acceptable range of values is $$$[0, x]$$$.
After performing a $$$-a_i$$$ operation, this is equivalent to accepting an initial range of $$$[0, x + a_i]$$$.
After performing a $$$+b_j$$$ operation, this is equivalent to accepting an initial range of $$$[0, x - b_j]$$$. If $$$x \lt b_j$$$, then no valid initial state exists.
For a fixed $$$(i, j)$$$, the accepted range $$$[0, ?]$$$ is a fixed interval, i.e., $$$?$$$ is a constant number.
This makes it convenient in our DP, since we don’t need to store the current value explicitly.
Essentially, we want to compute a valid suffix scheme such that during the process no value drops below $$$0$$$ (which would correspond to an invalid initial state).
As long as all intermediate ranges are valid, the final result is guaranteed to be valid because the left endpoint of every accepted range is $$$0$$$.
This can be solved with a straightforward $$$O(n^2)$$$ DP, or optimized to $$$O(n \log n)$$$.
Thank you so much for sharing your idea. Would you like to share your submission as well, since I still don't know how to implement the dp process.
Hello, my submission is here.
The design of the DP process is as follows. We first define $$$A$$$ to consider the range $$$i \sim n$$$, and $$$B$$$ to consider the range $$$j \sim n$$$, with the acceptable value range being $$$[0, v_{i,j}]$$$. In fact, you will notice that this allows for very natural transitions. Specifically, we set the initial value $$$v_{n+1,n+1}=0$$$, and each $$$v_{i,j}$$$ can be derived either from $$$v_{i+1,j}+a_i$$$ or from $$$v_{i,j+1}-b_j$$$. This can also be implemented easily using suffix sums.
Let $$$f_{i,j}$$$ denote the number of valid configurations where $$$A$$$ considers $$$i \sim n$$$, $$$B$$$ considers $$$j \sim n$$$, and the acceptable initial value range is $$$[0, v_{i,j}]$$$. We initialize with $$$f_{n+1,n+1}=x$$$ (where $$$x$$$ represents that the current problem we are solving is $$$f(0,x)$$$). Each time, we transition from either $$$f_{i+1,j}$$$ or $$$f_{i,j+1}$$$. If $$$(i+1,j)$$$ is a valid state (i.e., $$$v_{i+1,j}\ge0$$$), then we can transition; similarly, if $$$(i,j+1)$$$ is valid (i.e., $$$v_{i,j+1}\ge0$$$), then we can transition as well.
Finally, we return $$$f_{1,1}$$$.
Thank you again for your kind and detailed reply. There is still one thing that I feel confused.
As v[i,j] can be derived from either v[i+1,j]+a[i] or v[i,j+1]-b[j], then which one should we give to v[i,j]? If I understand your codes correctly, it seems that v[i,j+1]-b[j] is always set to v[i,j] as long as this is a valid transition? But why? Can we set v[i,j] = max(v[i+1,j]+a[i], v[i,j+1]-b[j]) or min(v[i+1,j]+a[i], v[i,j+1]-b[j])?
If $$$i\le n,j\le n$$$, $$$v_{i+1,j}+a_i=v_{i,j+1}-b_j$$$. They are same.
You really have helped me (maybe other ones who get stuck in this problem) a lot! Thank you!
I think the limits in problem B were too tight, is it just my skill issue or did anyone else have the same problem?
I passed it with 1900ms after the contest, but I use 2x states compared to tutorial ($$$(L, R]$$$ for all $$$1 \leq l, r \leq NK$$$, but tutorial only use $$$1 \leq l \leq r \leq NK$$$), and if we just consider subarrays with $$$l \leq r$$$ like editorial did, we can calculate DP in decreasing order of $$$l$$$, then increasing order of $$$r$$$, which would have much better constant than other ways.
So it's probably my fault in my case.
I did a range DP for each cycle with 10 transitions per state. It ran pretty fast (279 ms) but it was submitted 15sec after the contest ended :skull:
https://atcoder.jp/contests/arc204/submissions/68602610
I also got TLE in the first submission and did some optimization to squeeze it in. I think it is much faster to write the dp in a linear way rather than a recursive way. But maybe for the purpose of this problem, the constraints should be a bit smaller, since the way to write the dp isn't an important point.
Can someone explain to me what the updates for dp in B means?