### MikeMirzayanov's blog

By MikeMirzayanov, 4 weeks ago, Hey!

As I don't see the post discussing the round, I decided to write this.

I do not participate much in contests now. But I love Code Jam. Thanks to problem writers and organizers!

It seemed to me that this round was no more difficult than the previous one. How do you like it?

I liked the problems:

• A (tags: interactive, constructive): strange problem — the most naive approach fits into the requirements on the total cost of requests;
• B (tags: number theory, dp): I wrote some kind of DP with memorization of $(a, s)$, where $a$ is the last element in the sequence we already placed (I build in increasing order) and $s$ is the total sum for the future elements. I don't have a proof why it works fast, probably because of the number of divisors is small.
• C (tags: combinatorics, recurrence): the last occurrence of 1 is the position of $n$, so we can divide sequence with this position on two parts and use DP to calculate the answer (don't forget to multiply on binomial coefficient);
• D (tags: graphs, flows, greedy): I used min-cost-flow to match Ms on the first field and the second in optimal way. I tried all possible values of flow to iterate over all possible pairs of Ms I want to match and took best cost among all choices.  Comments (63)
 » 4 weeks ago, # | ← Rev. 2 →   Anyone else wasted a lot of penalty on problem A because I didn't realize $n$ is constant across all test cases...
 » Screencast with some commentaryIs the last problem known? I was just tired of thinking about it and submitted some greedy.
•  » » Well, You know you are screwed when Um_nik says he hopes to be in under 1000 xD.
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   I don't think this particular setting was known, but it was just obvious 1000th flow problem ¯\_(ツ)_/¯ Happens to the best of us
•  » » » Well, yeah, the flow solution is obvious, but why is it correct? It assumes that with each swap we can move two tiles closer to their destinations, and that's not very obvious to me.
•  » » » » Consider we want to exchange some M and G. Look at any path between them: find first MG and last MG — $\text{MMMMG....MGGGG}$. Make some swaps: $\text{GMMM}\textbf{M}\text{....}\textbf{G}\text{GGGM}$, then we exchanged first and last one, but the bold ones were ruined, reduce to exchange them, that makes the total number of swaps needed is the distance between them.
•  » » » » 4 weeks ago, # ^ | ← Rev. 2 →   Well yeah, that was actually a tricky part, I guess most of the contestants didn't care about the proof (I did though — I considered whether I am able to go from 0011 to 1010 with 3 swaps and then quickly generalized it). However do you want to tell me that you came up with a flow solution, but couldn't prove it, so you went with greedy (I got that impression from last comment)?
•  » » » » » Sorry, by greedy I meant hungarian )) It's not greedy inside, obviously, but I get the same vibe from it in this context "just make the best choice individually without understanding why it's correct"
•  » » It's pretty much the same as a problem that appeared at ptz camp in summer 2016 but with less details : problem G from contest 1.
 » Here's my screencast, which includes a bit of commentary. Thanks for the round!
•  » » 4 weeks ago, # ^ | ← Rev. 6 →   Plugging a few other people who did screencasts for this round. Thanks everyone!linguo https://www.youtube.com/watch?v=Z5GdUnpb1p0 (cf profile seems inactive but he was a finalist in 2015 https://www.go-hero.net/jam/15/name/linguo)EDIT: added links from comments and a few more that came up in search
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   You got the wrong link for Errichto :D. It should be 2021 https://www.youtube.com/watch?v=keDpEFGeWfM
•  » » » SnapDragon https://youtu.be/Yqzj6PIygQg(A veteran who has been ICPC WFs judge for 15 years.)He said in the stream — """I plan to stream GCJ practice at https://twitch.tv/snapdragon64 on Friday evenings (9:00 PDT). It'll be mostly the same format, but I'll also answer questions."""
 » You can also directly do D with min-cost circulation. Add a dummy vertex, an edge of cost $-L$ for some large $L$ from the dummy to to every M in the initial tiling, and an edge of cost $-L$ from every M in the target tiling to the dummy.Then add an edge of cost $s (|x_i - x_j| + |y_i - y_j|)$ between $i$th M in initial tiling and $j$th M in target tiling, and an edge of cost $f$ from every M in initial tiling to the dummy, and an edge of cost $f$ from the dummy to every M in the target tiling.Output cost of min cost circulation plus $L \cdot (\text{number of M's})$.
 » 4 weeks ago, # | ← Rev. 2 →   For D, there is a solution with O(r*c) nodes and edges.It uses min cost max flow. The graph has 2 + 2*r*c nodes. Two nodes are for the source and sink, and there are two nodes for each cell of the grid, representing the two colors. There are 4 types of edges: Source to initial color, with cap 1, cost 0 Final color to sink, with cap 1, cost 0 Between opposite colors of the same cell, with cap INF, cost 2*f Between adjacent cells of the same color, with cap INF, cost s The max flow of this graph is always r*c, and the mincost flow divided by 2 is the answer.
•  » » I had a similar solution using flow with demands. The way I thought about it was, let magenta = tile with token on it, green = absence of token. We are given the initial and final positions of the tokens, and we can do the following operations: create a token anywhere for a cost of $f$ delete a token anywhere for a cost of $f$ move a token to an adjacent tile for a cost of $s$ Now let $S$ be the source, $T$ be the sink, and one token = one unit of flow. Then the operations above correspond to the following edges: $S\to v$ with capacity $\infty$, cost $f$ $v\to T$ with capacity $\infty$, cost $f$ $v\to u$ with capacity $\infty$, cost $s$, where $v$ and $u$ are adjacent tiles Then for each initial position of a token, add an edge $S\to v$ with capacity 1, demand 1, and cost 0, and for each final position of a token, add a similar edge $v\to T$.Min cost of any flow satisfying the demands is the answer.
 » Can you please elaborate solution of Problem C?
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   I wrote recursive function long solve(int n, int[] a, int l, int r, int d) meaning: the input array is $a$ and has length $n$; function call solves subproblem for subarray $l \dots r-1$; we need to subtract the value $d$ from each element of the subarray $l \dots r-1$. The root call solve(n, a, 0, n, 0) solves the problem. In this call it is easy to see that the last 1 in $a$ corresponds to the position of $n$. If this position is $p$ (i.e. $a[p]=1$, $l \le p < r$ and $p$ is max), then we have two subproblems $[l, p]$ and $[p + 1, r]$.We solve the first subproblem: just to recurrence call solve(n, a, l, p, d). We solve the second subproblem: just to recurrence call solve(n, a, p + 1, r, d + 1) (we need +1 for $d$ because after placing max we have extra pancake under all pancakes of the second subproblem).We need to multiply solve(n, a, l, p, d) * solve(n, a, p + 1, r, d + 1). Also, we have many options to choose what elements will work for the first subproblem and what elements will work for the second. The number of ways is ${r - l - 1\choose p - l}$. So multiple the result on it. code private static long solve(int n, int[] a, int l, int r, int d) { if (l + 1 > r) { return 1; } TreeSet integers = pos.get(d + 1); if (integers == null || integers.isEmpty()) { return 0; } Integer p = integers.lower(r); if (p == null || p < l) { return 0; } int sizeL = p - l; int sizeR = r - p - 1; long result = (solve(n, a, l, p, d) * solve(n, a, p + 1, r, d + 1)) % M; result = (result * facts[sizeL + sizeR]) % M; result = (BigInteger.valueOf(result).multiply(BigInteger.valueOf(facts[sizeL]).modInverse(MM))).mod(MM).longValue(); result = (BigInteger.valueOf(result).multiply(BigInteger.valueOf(facts[sizeR]).modInverse(MM))).mod(MM).longValue(); return result; } 
•  » » » What is the time complexity of this recursive solution?it seems like there are O(N^2) number of calls to solve function and N is up to 10^5. Did this solution not time out for the large input?
•  » » » » The number of function calls to solve() is N, as every call eliminates one index.
•  » » » » » 4 weeks ago, # ^ | ← Rev. 6 →   akshaygahlot73 I'm not familiar with java but does TreeSet search the element in the subarray in logn? If not, would it not be $n^2$ ?P.S. I submitted the $n^2$ solution (searching the minimum in the subarray by iterating) and it passed which I believe shouldn't have too. The test case, I believe it would fail at easily would be $(1,2,3, ..... 1e5)$. Not to forget, $T$ was $100$ too.P.P.S. This issue can be fixed with a segment tree, to convert the minimum searching process from $O(n)$ to $O(log(n))$.
•  » » » » » » 4 weeks ago, # ^ | ← Rev. 2 →   I commented only on the number of function calls to solve(), not the overall complexity. I'm not familiar with with java (and TreeSet) either and used segment tree during contest.
•  » » » Apart from running the biggest cp website in the world, i like how mike is still doing what he loves most.
 » In B the number of edges inside a polygon with $a$ edges is less than $a$ so you only need dp values of kind $(a, n \% a)$.
 » 4 weeks ago, # | ← Rev. 3 →   I had an $O(n \log n)$ solution to B. Notice that the answer is of form $a + ab + abc + \ldots = n$. Rewrite as $a(1 + b + bc + \dots) = n \Leftrightarrow b + bc + \ldots = n / a - 1$. That is basically the form of the answer for $(new~n) = n / a - 1$. So to get the answer you can just do $ans_n = \max \limits_{d|n} ans_{n/d-1}+1$ plus-minus the polygons of size 2 case.
•  » » That's exactly what I did. Took me whole competition to get to this solution.
 » A bit weird that very trivial A costs more than not-so-trivial D-small.For me, the round was OK, but, unfortunately, concentrating on D small instead of very doable C-large costed me advancement to the next round. Participating in like 5 contests a year also does not help :) Anyway, the contest was nice, and it feels good to come back from "retirement" from time to time, so thanks to the organizers!
•  » » I also suffered from chosing to solve small D instead of large C too ;( It really hurts
 » What do you think your rating would have been if you actively took part in codeforces contests? (My guess is around 2700)(I'm excited to hear your opinion) Thanks.
•  » » I think that if I start writing rounds, then at first the rating after stabilization will be approximately mid-orange. If I write a lot and upsolving, then I suppose that I will become red.Unfortunately, every Codeforces round I have to monitor the system, provide technical support, etc. I don't have opportunities to participate regularly. But I love to solve problems.
 » 4 weeks ago, # | ← Rev. 5 →   The way I did D had (R * C + 3) nodes, 4 * R * C edges: One for each cell, a source, S, and two sink D' and D. We use the two sinks to limit the max Flow. (We want to fix how many Magentas we move to a valid position, and then do flips for the others). Construct the R * C graph by adding edges to neighbors of inf capacity, SwapCost.For every cell M that should be G, add edge from S to it, 0 cost, 1 capacity. For every cell G that should be M, add edge from it to D', 0 cost, 1 capacity.Then fix the number of Ms we want to solve by SWAPing to destination, i, from 0 to M inclusive. Make the edge D' to D be equal to that number. Do min-cost flow. Result for this being fixes is:flowCost + (total_bad — 2*i) * FlipCost (take min of all of these).Since you're only increasing the edge once, the flow you computed at the previous step is already valid, so you'll only need to do one iteration to update it.Locally my code ran in ~0.2 sec for all tests.
 » I had the same idea for B but stuck due to no proof of complexity!
 » I was able to solve only A and B, So this time also no advance to round 3. Also can someone please give out an estimated problem difficulty rating for all the problems ?
•  » » Minimum Sort ~ 1000-1200Matrygons ~ 1800Hidden Pancakes ~ 2200-2300Retiling ~ 2500-2700
•  » » » I'd say:A — 750B — 1750C — 2250D1 — <2000D2 — 2500My screencast, 1004th place. Please, anybody, find at least 4 cheaters...
•  » » » » cheatbuster cheat_buster please find this guy 4 cheaters.
 » The problems seem too straightforward for a R2.
 » I think C was the most beautiful problem although I got it ac only in last minute :)
 » I was very surprised at problem A. I did B first because I saw interactive and decided to leave it. After solving B I went back to A and did it in less than 10 minutes, and I only took that long because I was sceptical that it could be that easy.I don't think either of my solutions for B or C were the intended ones — I solved B top down (analysis says solve it bottom up), and I solved C using a segment tree and recursion (analysis says straightforward DP).D I got only the small and I was a bit fortunate because I had been brushing up on bipartite matchings recently.In general I found the contest more accessible than most of the round 2s I did in practice. In previous years at my current level I would have expected to progress less than 50% of the time, so today was a good day for me, which I think means the problems were not too hard.
•  » » How does your top-down B solution work?
•  » » » Define a recursion rec(target = X, max_used = M), and begin with rec(N,1) End the recursion as a failure if X % M != 0, or as 0 if X = 0. Then for each factor f_i of X (precomputed for all numbers up to 10^6 using sieve), rec(X,M) = 1 + max_i(rec(X — f_i, f_i)). Obviously if f_i doesn't meet the requirements (i.e. isn't a multiple of max_used), we bottom out and fail.Here is my code. My GCJ handle is the same as my CF handle.
 » 4 weeks ago, # | ← Rev. 2 →   I'm really devastated... my goal for the past 4 years has been to try to get top 1000 for the code jam t-shirt. This year I was finally going to get 950th place by solving A, B, and C. Except when the contest ended, my placement was 1806, not 950. Because my C hidden cases failed.Because I forgot 1 very trivial, very important line of python at the top of my code.I will never, ever, forget this fucking line again.  •  » » We feel ya :p I remember that I had this goal that I was not able to achieve for a very long time — solve the last problem of a Codeforfes round. Once I was late literally 0.5s cause I managed to upload it, but didn't manage to hit "submit" and it got accepted afterwards. What is more I ragequitted that contest halfway through without reading E and came back to read it out of curiosity some time later (15-30 mins) only to find out that it was algorithmic version of one of my favourite math problems ever. Second time I was solving some other hardest problem of the round, noticed that some variable could overflow int, so I declared it as long long, but computed it as a result of multiplication of two ints while not preceding it with "1ll *", which made it overflow anyway. That was the last straw that made me to finally become fully engulfed by the wisdom of "#define int long long"
•  » » » Thank you for the commiseration, that makes me feel better :)
•  » » » I had a similar experience :P Many years ago I solved a Div1.E in a contest, fixed all the bugs 2 mins before the contest ended, then my internet died so I couldn't submit... If I submitted successfully that would be the only "valid" AC solution during the contest since the other one was some hackable bullshit, but instead I got -100 :(
•  » » » » Feel ya :<. Are you perhaps talking about this contest :P? https://codeforces.com/contest/573/standings
•  » » » » » Exactly :P
•  » » » » » » Yeah, we all remember that memorable win by Marcin_smu which he followed immediately with another win in the very next round. Moreover in both of them he was followed by mnbvmar at the 2nd place and both of these times Marcin got hackable solutions (in the contest you mentioned his solution was total bullshit, but in the second one the idea he had in C was correct, but there was some mistake in the implementation that system tests didn't cover). I remember that after this second contest mnbvmar sent him a file called "LubieHakowacRozwiazaniaZwyciezcow.in" which when translated means "ILikeToHackWinnersSolutions.in" which, obviously, contained a test which Marcin's C solution failed on.
•  » » Feel for you. Next year! I submitted O(\tilde{O}^2) solution being sure it is \tilde{O}(n) one and then even did nothing last minutes of the contest :'(
 » I nailed the third problem 1 second before the end of the contest, though it didn't help me to qualify
•  » » Same here got it in last minute and ranked 1061 but we can still hope they catch 64+ cheaters in top 1000 :)
 » In D, I wrote an algorithm to find random non-optimal greedy answer which I ran for 10^5 times and took the best answer out of them, which passed test 1
 » I was a bit salty about cutoff for round 3 being too high. At one point I even considered sitting back and watching ranklist after I solved all visible subtasks. Glad that I didn't do it and solved C large as well. Anyways these are cutoff for round 3s (or score of 1000th rank in round 2) (if anyone is interested) -2021 — 66/100.2020 — 39/100.2019 — 32/100.2018 — 44/100.2017 — 23/100.2016 — 29/100.2015 — 22/100.2014 — 40/100.
•  » » I wonder if there is a hard constraint on the inclusion of an interactive problem in each round, but this A is at most a qualification round's problem. B being easier than a lot of A's in the past didn't help, either.
 » I was feeling sorry for 1001th rank guy , He literally disqualified for 1 secFinal time of 1000th rank guy:2:29:13 Final time of 1001th rank guy:2:29:14
 » I have solved B using a brute force solution with a complexity of around ~36sec. Codeconst int N = 1e6 + 5; int dp[N]; void fun(int prev, int sum, int cur) { if (sum >= N) { return; } dp[sum] = max(dp[sum], cur); for (int i = 2; i < N && sum + i * prev < N; i++) { fun(prev * i, sum + i * prev, cur + 1); } } void solve() { int n; cin >> n; int ans = dp[n]; cout << ans << endl; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); for (int i = 3; i < N; i++) { fun(i, i, 1); } int test; cin >> test; int tc = 1; while (test--) { cout << "Case #" << tc++ << ": "; solve(); } return 0; } 
•  » » Wow, how can this pass? I just submitted your code. It is not even passing the samples.
•  » » » I haven't included header files. I have just put the logic.I have passed both the test set using this brute force solution
 » for some unknown reasons, in problem B, my code passed both cases: Code(warning bad formatted)#include #define endl '\n' #define modulo 1000000007 #define int long long #define PI acos(-1) #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3") //#pragma GCC optimize("trapv") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.2,popcnt,abm,mmx,avx2,tune=native") #pragma GCC optimize("-ffast-math") #pragma GCC optimize("-funroll-loops") #pragma GCC optimize("-funroll-all-loops,-fpeel-loops,-funswitch-loops") #define sinDegrees(x) sin((x) * PI / 180.0) #define cosDegrees(x) cos((x) * PI / 180.0) #define tanDegrees(x) tan((x) * PI / 180.0) #define atanDegrees(x) atan(x)* 180.0 / PI #define asinDegrees(x) asin(x)* 180.0 / PI #define EPS 0.000000001 using namespace std; int power(int x,int y,int m) { int temp; if(y == 0) return 1; temp = (power(x, y/2,m))%m; if (y%2 == 0) return ((temp%m)*temp); else return ((x*temp%m)*temp%m)%m; } int inv(int x,int m=modulo) { return (power(x,m-2,m))%m; } ///IOI 2021 bronze medalist isA int N,testcases; int REC(int num,int TOT){ if(TOT>N) return INT_MIN; if(TOT==N) return 1; int maxer=INT_MIN,i=2; while(TOT+num*i<=N&&i<7) maxer=max(REC(num*i,TOT+num*i)+1,maxer),i++; return maxer; } int32_t main() { //freopen("output.txt","w",stdout); //freopen("input.txt","r",stdin); cin.tie(0),iostream::sync_with_stdio(0); cin>>testcases; for(int i=1;i<=testcases;i++){ cin>>N; int maxer=0; for(int i=N;i>2;i--) maxer=max(REC(i,i),maxer); cout<<"Case #"<
•  » » You got lucky, there are some cases where your solution fails (but not that many).The smallest N where you fail is N=250: you output 3 but there is a solution in which the polygons have 5, 35, 70 and 140 vertices.
•  » » » Wow, okay. Thanks for your reply!
 » 4 weeks ago, # | ← Rev. 4 →   I ranked 1672 in code jam round2 , so sad that I didn't make it to next round. This year contest is much easier. Usually solving two whole problem and an additional small test set will guarantee you with top 1000 and make it to next round, this year even solving three problems cannot pass.
•  » » 3 weeks ago, # ^ | ← Rev. 3 →   why so many people downvote me, what wrong did I say?