Hello Everyone,
Topcoder SRM 806 is scheduled to start at 11:00 UTC-4 on May 26, 2021.
Registration is now open for the SRM in the Arena or Applet and closes at** 10:55 UTC-4. **The coding phase will start at **11**:**05 UTC-4**, so make sure that you are all ready to go. Click here to what time it starts in your area
Please take a look at our How to Compete guide to understand Topcoder Algorithm rounds better.
Problem Writer: misof
Learn more about problem writing and testing opportunities.
TCO21: This is the second SRM of Stage 4 of TCO21 Algorithm Tournament. Learn More
Some Important Links:: Match Results (match results, rating changes, challenges, individual test case results), Problem Archive, Problem Writing, Algorithm Rankings, Editorials and Older Editorials(SRM 710 and before),
Best of luck!
- the Topcoder Team
Since no one bumped this post after the contest. Here we go.
How to solve the easy and medium questions?
On a sidenote, although I couldn't solve it. This easy question was better than typical topcoder boring easy questions.
I thought medium is too standard so I Googled "educational dp kmp" and found a similar problem in an Educational round, 808G - Гимн Берляндии. You even solved it before!
The 300p and 1000p are quite interesting, I love them! The 500p is standard though.
Brief solution:
300p: we can construct a permutation that contains only one cycle, so the number of steps is minimized. The cycle should contain all pairs $$$(i,j)\pod{i\neq j}$$$ and be in the form of $$$(a,b),(b,c),(c,d),\ldots,(z,a)$$$. If you consider a pair as an edge, it becomes a Euler tour, thus can be constructed easily.
500p: use KMP Algorithm and DP. Complexity $$$O(L\cdot |S|\cdot |\Sigma|)$$$.
1000: Alice loses iff $$$a_0=a_1=a_2$$$, $$$a_4=a_5=a_6$$$ and $$$a_0\oplus a_3\oplus a_6=0$$$. Proof is simple.
500p also has a solution in $$$O(|S|^3 \log L)$$$ with matrix exponentiation-like combining of matrices "from KMP state $$$i$$$ to KMP state $$$j$$$ using $$$2^k$$$ characters, what's the max. number of occurrences we can gain and number of ways to do that?". I agree that it's standard stuff either way.
Does anyone have any ideas about solving the 1000 on a general graph? (This solution obviously extends to any number of parallel paths.)
There's an alternative solution to the 500 that doesn't directly involve the KMP automaton; it only relies on the set of borders of $$$S$$$ (a border is a shared prefix and suffix of $$$S$$$). Then, we can compute a DP of the number of ways of picking a prefix of length $$$l$$$ with the maximum number of matches and the last match ending at $$$l$$$. Then, we can just try each possible distance/overlapping border between the last occurrence and then next occurrence of $$$S$$$. There is a worry that we will "overcount" strings $$$T$$$ because we might jump over some matches in our jumping strategy; however, this is not a worry because we're trying to end up with the maximum possible number of matches anyways, so we'll never miss a match in a maximum-length sequence.
This runs in $$$O(L^2)$$$ or $$$O(L |S|)$$$ if you optimize the non-overlapping case a little.
You can actually improve this even further to $$$O(|S| \log |S|)$$$ (independent of $$$L$$$) using FFT to take powers of generating functions with $$$\exp$$$/$$$\log$$$, because there is at most $$$|S|$$$ total "slack" (extra characters/length) compared to the strategy of always taking the maximum overlap.
The naive $$$O(L^2)$$$ solution is probably to keep the end of current S as the DP state, and then loop for the end of next S for the next DP state. If they overlap then we can look up some 2d array or use z function to determine whether the overlap is valid.
The $$$O(L|S|)$$$ solution is probably to maintain 2 DPs. One same as above, where did current S ended. And the other DP is, solve for remaining length. So in case of non overlapping S, we will call the second dp for the state $$$i+|S|$$$. For overlapping case there are $$$|S|$$$ possibilities to call the first DP.
I wonder how to convert it to FFT solution. Specially I am confused how to do maximization and also deal with these two different DP to achieve the generating function.
The short answer is that we can compute an easy closed form for the maximization, so only counting ways is nontrivial.
Let the longest possible overlap have length $$$k$$$. Then, for a fixed length $$$L \ge |S|$$$, the maximum number of occurrences is exactly $$$Cmax = 1 + \left\lfloor \frac{L-|S|}{|S|-k} \right\rfloor$$$, and we have $$$(L-|S|) \% (|S| - k)$$$ extra space that we can fill. Then, we can compute the generating function for number of ways to use $$$l$$$ extra space between two instances of $$$S$$$ (this is 0 or 1 for $$$l \le k$$$ depending on whether the overlap is valid, and $$$26^{l-k}$$$ for $$$l \ge k$$$), and take the $$$Cmax$$$ th power. Exponentiating by squaring would take $$$|S| \log|S| \log Cmax$$$ time, but you can actually do $$$|S| \log|S|$$$ time with techniques like this.
For the 500p I never thought of KMP, went a completely different direction by separating 4 different cases: L < |S|, S all char the same, S can overlap with S, no overlap. And then I tried to solve it using combinatorials, but failed in the end for the last two system tests :(
Should learn KMP right away
I was really struggling with 300 before coming up with this inductive solution right before the contest ended:
(Hint: think of how you would solve for $$$n$$$ if you already has a solution for $$$n-1$$$)
what is a & b?
10 and 11?
Mine was no more than a guess :)
Start from (0, 1), then for every last pos (x, y) in the answer list, look for y at row y from right to left, and appened the position found to the answer list. Finally, put N * N in.
I really don't know how to prove this, but it works magically.
The rough idea is, each swap should be effective, so go for the row with the same color as the column of the empty slot indicates. But instead of going from left to right, we go from the other way around; otherwise, we may exhaust all the 1's in.
I think this should somehow echo with the euler cycle idea mentioned above.
My solution was exactly the same :)
Was editorial draft shared in arena?
No, I don't think so.
Editorial Draft: https://docs.google.com/document/d/e/2PACX-1vRp_TbiJ8UGMwaF2KhCkmj2KiEJ-XS4RFvMyvdvbwlcMwVLwjTeRHz7Ep1_sMDtwxoAFdj8NvzwY95H/pub
Ok, so for 1000 it seems this is the key observation for any graph with 2 vertices connected by multiple direct paths: if there's a path where all piles aren't equal, it's a winning state.
Let's use $$$m_1, m_2, \ldots, m_k$$$ to denote minima of $$$k$$$ paths. By contradiction: for a "smallest" (figure out by yourself what this means) losing state $$$s$$$ with at least 1 path that doesn't have equal piles, we can move to the state $$$(m_1, m_2, \ldots, m_k)$$$, and since we haven't taken from all the piles in any path, we can still decrease some $$$m_i$$$ by taking an equal number from all piles in path $$$i$$$.
Now we're solving the game on states with equal values on each path, which is just nim, since from a state $$$(m_1, m_2, \ldots, m_k)$$$, we can't make any moves other than decreasing exactly one value.