Topcoder SRM 789 is scheduled to start at 13:00 UTC -4, August 30, 2020.
Registration is now open for the SRM in the Arena or Applet and will closes at 12:55 UTC-4. The coding phase will start at 13:05 UTC-4, so make sure that you are all ready to go.
Thanks to square1001, lg5293 and misof for writing the problem set. Also thanks to misof for testing and coordinating the round.
Choose Your Competition Arena
There are two ways to compete in Algorithm Competitions or Single Round Matches (SRMs). Read here to find which works best for you.
Some Important Links
| Match Results | (To access match results, rating changes, challenges, failure test cases) |
| Problem Archive | (Top access previous problems with their categories and success rates) |
| Problem Writing | (To access everything related to problem writing at Topcoder) |
| Algorithm Rankings | (To access Algorithm Rankings) |
| Editorials | (To access recent Editorials) |
Good luck to everyone!
Gentle Reminder: Match begins in an hour
I found the Div1 1000-pointer very nice, thanks!
Get Downvotes !
dont make this great platform spoil
For those lazy to look it up, the 1000-pointer for this round was written by Lewin (lg5293 at Topcoder).
The editorial has not been posted right? I don't see it when I click "Editorial". Anyway, how to solve the second and third problem?
500: Assume $$$C \le 13$$$. A state will need information of two previous rows to transit to next state but the number of states is very small (about thousands) not $$$2^{26}$$$. Nothing else...
Yea it is also worth noting that the number of states is bounded by Fibonacci numbers due to the condition that no two bases can be adjacent, which is less than a thousand here I guess.
For one row the number of valid placements of bases into n columns satisfies the recurrence ways[n]=ways[n-1]+ways[n-3], which gives an upper bound of O(1.4656^n), better than Fibonacci. (Bases must be at least 3 apart, so if you place a base into column n, you need to leave the next two free.)
In a similar way we can find an even tighter bound for the number of ways to fill two consecutive rows with n columns: O(1.8393^n). Thus, solutions that only construct reachable states and then iterate over all valid ways to fill the next row actually run in O(some polynomial * 2.6957^n). That's quite less than the naive estimate of O(poly * 2^(3n)) = O(poly * 8^n).
For n=13, 2.6957^n is roughly 400,000.
The task is also solvable in O(poly * 2.3325^n) with a more complicated implementation: when going from one state to another you need to generate only the valid ways of filling the next row given the bases you already placed, instead of going through all ways of filling the row in vacuum and filtering out the ones that create a conflict.
I see. Thanks.
For hard, I think something like this works (I haven't coded it yet):
Call a number x special-winnable if P1 wins when we are forced to only play with special numbers in a pile of size x.
Crucial claim: If there exists a pile of size x > 0 where x is special-winnable, P1 wins. Additionally, there exists a winning move for P1 starting from pile x.
Let X be the set of remaining piles (X may be empty).
If X is P2-win, then P1 wins by removing x.
If X is P1-win, then let P1 perform play on the pile x assuming that she is only allowed to play with special moves. P2 is forced to play in the pile x. But P2 is not obligated to play special moves only, or is he? If he plays a non-special move at some point (let's say before that the pile has size x, P1 plays a special move to reduce it to y, and P2 plays a non-special move and reduce it to z. Note that P1 can play on any pile now. If the position is a P1-win, P1 wins. If the position is a P2-win, then P1 could have won by instead reducing the pile from x to z immediately (without playing x->y). She wins in the new position because it is a P2-win (and even if P2 is restricted in playing in the first pile during the next move, it only helps P1).
Note that in both cases, P1 starts by playing in pile x. Hence, our claim is proven.
With this lemma, we can finish off the problem. First, we can determine all special-winnable numbers via a simple dp.
Let us start by determining if a state $$$a_1, a_2, ..., a_n$$$ is a P1-win. If any of the $$$a_i$$$ are special-winnable, P1 wins. Additionally, if a player turns a pile into a special-winnable pile, that players automatically loses by the claim (since the next player can win by performing some move in this pile). Hence, both players now must avoid turning piles into special-winnable piles.
By the definition of special-winnable, we note that if x is not special-winnable, any special move will turn it into a special-winnable pile. Hence, we cannot even perform any special moves if we want to win!
Thus, the rest is easy since not playing any special moves mean that each pile is independent. We can compute the grundy number for each pile and xor everything.
Counting the number of winning states can be done in a similar fashion via brute force since constraints are small.
That's a nice solution :) Thanks.
Thank Lewin for the beautiful problem :)
It seems like the official editorial is ready!
Lewin misof square1001 Can you please help me with SRM 789 Div2 Hard/Div1 easy question ThreeDigits? I tried every input possible I tried to run the script to see if my solution works with 0<=x<100 && 0<=y<100 && 1<=z<100 my solution works for these inputs but when I submit on topcoder it is giving WA. Here is my solution.
I would be suspicious of the part where you do to_string(long double). Try rewriting that step using integer arithmetic only.
(Also note that systests in the practice room will tell you the test case you are failing on.)
I didn't have used much of the topcoder site so can you tell me how can I look for system test cases for SRM or any other competition problems in practice mode?
Edit: Got AC. the issue is with to_string first I have to multiplied the answer by 1000 then divide by 1000 after convert into long then use to_string because to_string doesn't take care of precision by itself