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.
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 commentary
Is 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.
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.
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!
Plugging a few other people who did screencasts for this round. Thanks everyone!
Um_nik https://www.youtube.com/watch?v=S-BINlxNvdg
neal https://www.youtube.com/watch?v=6q_dhs_1jKo
Geothermal https://www.youtube.com/watch?v=5j0oN_yKBRw
Errichto https://www.youtube.com/watch?v=keDpEFGeWfM
SecondThread https://www.youtube.com/watch?v=hJ6DWbZwLKo
galen_colin https://www.youtube.com/watch?v=1MLzXUXzoxo
Golovanov399 https://www.youtube.com/watch?v=8IhygelshaQ
tmwilliamlin168 https://www.youtube.com/watch?v=kKVoPoYdAPM
jonathanpaulson https://www.youtube.com/watch?v=pyUomAtybIk
SnapDragon https://youtu.be/Yqzj6PIygQg
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
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})$$$.
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:
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:
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:
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?
I wrote recursive function
long solve(int n, int[] a, int l, int r, int d)
meaning:The root call
solve(n, a, 0, n, 0)
solves the problem. In this call it is easy to see that the last1
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 callsolve(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.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.
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))$$$.
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.
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)$$$.
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.
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-1200
Matrygons ~ 1800
Hidden Pancakes ~ 2200-2300
Retiling ~ 2500-2700
I'd say:
A — 750
B — 1750
C — 2250
D1 — <2000
D2 — 2500
My 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.
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.net/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 sec
Final 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.
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:
my idea was just to brute force to start with any number bigger than 2, then either multiple it by 2,3,4,5,6. And check the best result. Such a solution should get wrong answer(according to my knowledge I guess). Can anyone contradict/proof if my solution is correct/incorrect?
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!
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.
why so many people downvote me, what wrong did I say?