As of now, there is no blog, so I'll post this.
How to solve C Large without complex casework?
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
Name |
---|
Auto comment: topic has been updated by maroonrk (previous revision, new revision, compare).
All I could think of during the round: who hurt the problemsetter?
For me the problems were mostly fine?
Do you have clean solutions (i.e. not a shit ton of casework) to A/C large?
For A there is a clean exponential solution (mine solution is some shit tho). In C there is not that much casework. However the solution idea I have is rather tedious to code even though I really like geometry. Not super bad though.
A:
N is odd: simple greedy
N is even: Run backtracking. If the prefixes aren’t equal then greedy works (we know which number is greater, so it has to be as small as possible). If the prefixes are equal then consider all possible choices, but make sure that the digits in the equal prefixes are somehow sorted (in nonincreasing order for example).
I pick a000...000 and b999...999 and try to append to head with equal pairs and tail likes the odd case.
Odd length is simple. For even length, we will check all possible prefixes that will be shared for our numbers. For their first different digits, brute force all pairs that minimize the difference. The remaining suffix can be constructed greedily.
The official analysis provides a $$$O(2^{N/2})$$$ but for the worst case where each digits from 1 to 9 has 4 occurrences, we can further improve it to $$$3^9$$$ cases (choosing 0, 1 or 2 pairs for each digit).
N is odd: trivial.
N is even: I sorted the digits, and used a recursion. In any recursion where we are trying to minimise difference, the leading digits must be adjacent in the sorted list. Try each adjacent pair, taking care not to use 0s in the first case. If the adjacent pair are the same, you repeat the recursion on the remaining digits. If the adjacent pair are different, you are then finding the smallest and largest possible numbers from the remaining set.
I used memoization just to be sure but I probably didn't need to.
I forgot memoization and got TLE, so probably you should.
Yes I realise now why it's needed: you have 35 adjacent pairs, but in the worst case only 17 unique adjacent pairs (in the case 000011112222333344445555666777888999 for example).
I don’t like C, but other problems were quite nice :)
Why Radewoosh dropped to 34th place from 2nd place after getting perfect 100? same with firefly?
They resubmitted their solutions.
Resubmit?
firefly resubmitted to solve B-large.
Radewoosh is at 9th
I'm sorry to be so harsh but IMO A ruined the entire problemset.
Problem A was disgusting.
tfw you would have been able to submit B small to get within qual range if you just had one more minute :(
Not a fan of A at all, and the implementation for B small was a bit bashier than I would have liked, but I will note that D was a very nice problem--too bad that it was stuck at the end of the set!
I think that C large can be solved by first computing an arbitrary triangulation, and then flipping all edges that intersect the two constrained edges.
Screencast (without commentary this time)
Passed B Large with a strange algorithm:
Seems most participants use network flow for B.
I don't even need to search for squares which simplifies the code significantly. I just exhaustively check for 2 rows and 2 columns such that on their intersections I have
/\
\/
and I flip all of these 4 cells.
Flow is the easiest way to construct a grid with given constraints. I knew it can be found constructively in linear time, but didn’t want to bother.
How could you create the satisfied graph without network flow?
Wouldn't greedy (where for every row you mark the columns with the most marks still needed) work? Can't come up with a counter-example.
It works. Proof: let's consider filling rows one by one. Suppose that for some row $$$i_1$$$, we put mark into column $$$j_1$$$ and don't into $$$j_2$$$, where in column $$$j_2$$$ we need to put strictly more than into $$$j_1$$$. Then in some of the next rows (say, $$$i_2$$$), we will have to put mark into column $$$j_2$$$ and not into $$$j_1$$$. Then we can instead put marks in $$$(i_1, j_2)$$$ and $$$(i_2, j_1)$$$ instead of $$$(i_1, j_1)$$$, $$$(i_2, j_2)$$$
For each $$$D_j$$$, find the $$$D_j$$$ number of rows with the largest $$$S_i$$$. We place a slash in each $$$(i, j)$$$, and decrease the corresponding $$$S_i$$$ by $$$1$$$ afterwards.
I also did this. Used priority queues to construct the initial grid row by row: if at any stage you run out, IMPOSSIBLE, otherwise you have a starting grid.
Then my approach was similar except that I moved all /\ pairs to the ends of rows and columns and all \/ pairs to the start, and then repeated that 20 times to iteratively move any newly created problems leftwards/upwards until finally there were no problems left.
They have mentioned this approach in "Flip Flop" section of the Analysis and show that it's finite and the asymptotics are enough. They didn't however mention greedy which makes this task even easier (since flows are only helpful if you solve the task the intended way I feel).
This is the reason why I personally disliked this task since it clearly has two ways two go about it with one significantly easier than the other one. From reading the analysis I got the impression that they realized that there exists this alternative solution quite late in the problemsetting, and I'm not sure why the task was kept after that or not swapped with the first one.
Screencast (solved aBd, one step away from aBD) https://youtu.be/MDTHp_DA-lU
warning: sound is bad
My solution to A matches the editorial and it isn't tedious at all IMO. I guess most dislikes come from people with solutions not as clean.
My solution to C:
I am once again asking for touristreams
rank 26...
Next time I will try to write small tests immediately on complicated problems such as C, D... (>__<)
Surprised to see all the hate for problem A. N odd was trivial, and N even could be tackled by a fairly clean recursion:
Sort the digits
Try each adjacent pair as the leading digit of the two numbers
If the adjacent pair are different, greedily fill the remaining digits. If they're equal, recursively solve for the remaining digits (allowing leading zeros after the first level of recursion)
Take the minimum of these
Congratulation to all 24 finalists. We will know in two months who is the 2nd place of GCJ 2021.
I've a feeling that radewoosh might be 2nd only if mifafaovo doesn't go in god mode.