We will hold AtCoder Grand Contest 046. This contest counts for GP30 scores.
- Contest URL: https://atcoder.jp/contests/agc046
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20200620T2100&p1=248
- Duration: 150 minutes
- Number of Tasks: 6
- Writer: DEGwer
- Rated range: 1200 ~
The point values will be 200-600-800-1100-1500-2000.
We are looking forward to your participation!
How to solve D?
I decribed my solution below. It has a lot of steps.
How to solve C?
DP. State is (position in the string, how many times you can delete a 1 from the string, how many times you can add a 1 to the string, whether you are allowed to delete a 1, whether you are allowed to add a 1). The transition is picking whether the next character will be a 0 or a 1.
The two booleans in the state are to avoid double-counting. Once you decide not to delete a 1 in the current block you can't delete 1s any more (since that would give two paths to the same string). Once you delete a 1 in a block of ones you can't add a 1 anymore (since that would give two paths to the same string).
Brute force over how many moves (adds+deletes) you will ultimately make. Note that this is at most the number of 1s in the original string ($$$K<=10^9$$$ is misleading).
My code ("nadd" starts as the number of moves you will ultimately make):
Assume there n number 0,we get n+1 pit,use 1 throw in these pit.Set dp[i][j][k] represent the to i-th pit,use j number 1 total,move k step.We can get a O(n^4) Dp,but for 0 and 1 need balance,the number of pit expected is n/2,so time complex is O(n/2^4),and we also need meet j>=sum[i] anytime,sum[i] is the first i pit include 1's number.So with the condition,we actually time complex is expected O(n^3).
A — Either brute force, or use the formula lcm(360, x) / x.
B — Use dynamic programming. Let f[i][j] denote the number of different configurations starting from a rectangle of size a x b to a rectangle of size i x j. The transitions are the following:
(i, j) is filled: in this case, it is always possible to uniquely determine whether a row or a column was added last. Therefore, f[i][j] += f[i-1][j] + f[i][j-1].
(i, j) is not filled: We count the number of cases where we could have added a row last (that is, the top row contains exactly 1 black square), which is (j — 1) * f[i-1][j]. Similarly, we count the number of cases where we could have added a column last, which is (i — 1) * f[i][j-1]. Finally, we subtract the number of cases where both are possible, which is (i — 1) * (j — 1) * f[i-1][j-1].
C — Consider the zeros of the string as separators dividing the string up into blocks. Also consider the sequence, consisting of (NumOfZerosInString + 1) elements, which represent the number of 1's in each block. For example, the string 0111001 is represented by the sequence [0, 3, 0, 1] (Note that there is a size 0 block at the very beginning, before the first 0).
Whenever we perform an operation, we decrement an element of the sequence by 1 and increment an element to the left of it.
We find that a sequence can be achieved using some number of operations if and only if each element in the new sequence's prefix sum sequence is not less than the corresponding element in the original sequence's prefix sum sequence. In addition, if the new sequence can be formed, the minimum number of operations needed to change the original sequence, orig_i, to the new sequence, new_i, is the sum of all max(new_i — orig_i, 0).
Using these facts, we can do dynamic programming. Let f[i][j][k] be the number of ways to choose the first i elements of the sequence such that the current prefix sum is j and the current minimum number of operations needed is k. To make transitions, enumerate the next element of the sequence.
The time complexity is currently O(n^4). To speed it up to O(n^3) we use prefix sums (turns out two prefix sums are needed, with one of them being a diagonal prefix sum).
By the way, the forbidden configuration in problem F is identical to that of 1338E - JYPnation. Even the labeling used in the statement (A, B, C, and D) is unchanged.
What is the proof of A?
We keep rotating until the total angle we rotate by is a multiple of 360. Clearly, the first multiple of 360 that we will reach is lcm(x, 360). Dividing this number by x yields the number of rotations that we will perform.
but each time we are moving by one meter, why we will regain our first position after the first multiple of 360 ?
For the angles divisible by $$$360$$$, If we consider the angles as the exterior angles of a regular polygon of $$$1$$$m side. It is known that it's sum is equal to $$$360$$$. We can extend this for angles not divisible by $$$360$$$ by taking the lcm.
For a more detailed proof we can consider the equation in vector plane:
$$$\sum_{k = 1}^{n}1 \angle (k x) = 0$$$
$$$\sum_{k = 1}^{n}e ^{ik x} = 0$$$ where you can assume real part as x axis and imaginary as y axis.
The second answer from this link shows that this is equal to :
$$$\frac{sin\frac{nx}{2}}{\frac{x}{2}}e^{\frac{i(n+1)x}{2}}$$$
So, $$$nx$$$ = multiple of $$$360$$$ for the above term to be $$$0$$$.
It was a great DP contest
Solving A by guessing :)
Lucky for reading this problem :D
Same here.
I did upsolve the problem but my solution was different from the author's, so I had to read the editorial during the contest.
On the opposite, Radewoosh solved it in a different way than editorial and that insight he had during cf contest gave him a lot advantage here, while me and mnbvmar read editorial of this problem and got nothing. Could you describe how to solve it based on observations from editorial?
https://codeforces.me/blog/entry/75913?#comment-602145
Yep, I was thinking more about a Hamiltonian cycle of the graph instead of partitioning it into two parts while still I cut this cycle into two to calculate the result.
When I read that the vertices can be split into two parts (say, P and Q), I was almost sure that the table[i][j]=(there is an edge from P_i -> Q_j ?) has a nice structure, because otherwise, it's impossible to count them!.
I then wrote down some graphs, found a likely pattern, gave reasoning to satisfy myself, and got AC!
Well, I considered such tables for a long time, but got pretty lame results. One nice condition is that when I look at a vertex then its outneighbours on second path form an interval which says that 0s in each row form an interval and that 1s in each column form an interval and moreover that is equivalent condition for a table to have no forbidden structures. However such tables can be pretty wild and I had no idea how to count them (with even some more conditions on indegrees and caring that such partition is unique in some way). mnbvmar told me that if we still remember that terminal vertex of one part has maximum indegree then these tables look nicer, bit I didn't use that when analyzing them — is that something you used?
Well, I used that fact, but not explicitly. Rather, I just sorted the vertices of each part, then the table looked really simple.
I am author of that problem and I cannot solve in time.......
How to solve B?
dp[i][j]=number of ways to color a grid of size i*j. The given grid is always fully white. So, dp[a][b]=1.
Transitions are quite simple,
dp[i][j] = dp[i][j-1]*i + dp[i-1][j]*j-dp[i-1][j-1]*(i-1)*(j-1)
First term corresponds to adding a column where we can color any 1 of the i cells. Second term corresponds to adding a row where we can color any 1 of the j cells. We have counted some colorings twice, so we'll remove them. This part corresponds to the 3rd term.
Final answer is dp[c][d].
Soooo my solution to D, which was to me the most interesting problem out of ABCD because of this unusual approach:
My code to "F — Forbidden Tournament". Time complexity $$$\mathcal O (N^4)$$$.
mayaohua2003 had said CF1338E has a worth studying Graph structure. As expected, just modifying a little, creates a new problem.
Use the lemmas in CF1338E's official editorial, it turns out we need to calculate the number of sequences $$$a_{1 \ldots |P|}$$$ satisfying $$$a_1 = 0$$$, $$$a_{|P|} = |Q|$$$ and $$$a_{i - 1} \le a_i$$$, furthermore, because the editorial demands node $$$x$$$ has the maximum in-degree, condition $$$(i - (|P| - |Q|)) \le a_i \le (i - 1)$$$ must be satisfied. But in this way some graphs may be counted multiple times, this is because if more than one vertices have the maximum in-degree as $$$x$$$ does, each of them will be chosen as $$$x$$$ exactly once. So if the number of these vertices is $$$c$$$, this sequence contributes $$$\frac{N!}{c}$$$ to the answer.
For all values of $$$|P|$$$ and $$$|Q|$$$, use DP to calculate the contributions, naive approach gives $$$\mathcal O (N^6)$$$. Use prefix-sums to handel transitions, and process the $$$P, Q$$$ pairs together if they have the same $$$|P| - |Q|$$$ value. So the final complexity is $$$\mathcal O (N^4)$$$.
detailed explanations.
$$$a_i$$$ is actually $$$|\mathrm{in}Q(P_i)|$$$ in CF1338E's official editorial, the editorial didn't give out all the properties. let $$$b_i = |\mathrm{in}P(Q_i)|$$$, we have $$$b_i = \min ( \{ j \mid a_j \ge i \} ) - 1$$$. considering the in-degrees of vertices in $$$Q$$$ should be less than $$$|P|$$$ too, it's not hard to get $$$(i - (|P| - |Q|)) \le a_i$$$.
when counting those $$$c$$$ vertices, note that $$$\displaystyle c = \sum_{i = 1}^{|P|} [a_i = i - 1] + \sum_{j = 0}^{|Q| - 1} [a_{j + |P| - |Q|} = j]$$$. so add it to DP states, it's an 1 dimension stages($$$i$$$) 2 dimension states DP($$$a_i$$$ and $$$c$$$).
$$$O(n^3)$$$ solution of F: As in all other solutions, notice that in strongly connected graph we can arrange vertices on cycle in such a way that for every vertex $$$v$$$ all vertices $$$u$$$ such that there is an edge $$$v->u$$$ form a segment after $$$v$$$ (let's call its end $$$C(v)$$$). Ok, let's multiply all at $$$(n-1)!$$$, now just the lengths of segment matters. Lets fix also $$$a=C(1)$$$. Now let's go from 1 to $$$a$$$ and draw some sequence of $$$+$$$ and $$$-$$$ in the following way — in $$$i$$$-th step draw firstly $$$+$$$, then $$$C(i+1)-C(i)$$$ minuses. If we look at condition about degree, we can notice that correct sequences are the followings: if we start from $$$a-1$$$ and make steps $$$+1$$$ and $$$-1$$$ according the sequence, we will be in $$$[max(n-k-1,1), k+1]$$$ all the time, and it is equivalent. Now we can calculate number of such paths using reflection principle in $$$O(n)$$$ (and in total there is just formula with $$$O(n^3)$$$ summands).
In fact all summands are binomial coefficients, and there are only $$$O(n^2)$$$ different of them, so with some care we will obtain $$$O(n^2)$$$ solution, or maybe even faster.
When solving the problem D, I noticed the following.
Let
Xbe the number of different binary strings that can be obtained by inserting exactly $$$n$$$1sand $$$m$$$0sinto a binary stringS.The
Xonly depends on the number of1sand0sinS. In other words, if to shuffle digits inS,Xwon't change.How to prove it?
Consider the greedy algorithm deciding if string $$$t$$$ is a subsequence of another string $$$s$$$. In case of success this algorithm gives $$$|t|$$$ positions $$$a_1, a_2, \ldots, a_{|t|}$$$ such that $$$t_i = s_{a_i}$$$. Notice that for each $$$i < |t|$$$ letters $$$s_{a_i+1}, \ldots s_{a_{i+1}-1}$$$ must not be equal to $$$s_{a_{i+1}}$$$. The letters after $$$a_{|t|}$$$ don't matter.
So you just take string $$$t$$$ and before each letter $$$t_i$$$ you insert some non-negative number of letters not equal to $$$t_i$$$. After the last letter you can insert anything. In this way you can uniquely generate all possible strings $$$s$$$ which have $$$t$$$ as a subsequence. Simple binomial coefficients finish the argument.
That makes sense, thanks.
What was the reason for introducing a lower bound for participation in AGC? You can take a look at grass_strawberry, who took the 20'th place and gets nothing. This decision seems a bit unfortunate, especially that most of the stats show that the contests for everyone provide the best rating (the closest to the real skill).
Sometimes A is nontrivial and for very low rated people it's possible to get + by not getting any ACs.
Can someone give a bound for tourist's solution to C
It seems O(n^4) but it passes all the tests.
https://atcoder.jp/contests/agc046/submissions/14500508
I believe a lot of optimized $$$O(n^4)$$$ passes for $$$n \le 300$$$ especially when a lot of states aren't actually visited so the constant is small. I had a $$$O(n^4)$$$ in C and D during contest but tried to get them to $$$n^3$$$ and failed :(
UPD: It turns out I misread C >_<