MikeMirzayanov's blog

Google Code Jam 2021: Round 2
By MikeMirzayanov, 4 years ago, In English

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.
  • Vote: I like it
  • +659
  • Vote: I do not like it

Comments Comments (61)
| Write comment?
»
4 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

Anyone else wasted a lot of penalty on problem A because I didn't realize $$$n$$$ is constant across all test cases...

→ Reply
»
4 years ago, # |
  Vote: I like it +40 Vote: I do not like it

Screencast with some commentary

Is the last problem known? I was just tired of thinking about it and submitted some greedy.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +47 Vote: I do not like it

    Well, You know you are screwed when Um_nik says he hopes to be in under 1000 xD.

    → Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it +29 Vote: I do not like it

    I don't think this particular setting was known, but it was just obvious 1000th flow problem ¯\_(ツ)_/¯ Happens to the best of us

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +23 Vote: I do not like it

        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.

        → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
        ← Rev. 2   Vote: I like it +5 Vote: I do not like it

        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)?

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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"

          → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
4 years ago, # |
  Vote: I like it +31 Vote: I do not like it

Here's my screencast, which includes a bit of commentary. Thanks for the round!

→ Reply
»
4 years ago, # |
  Vote: I like it +10 Vote: I do not like it

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})$$$.

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +112 Vote: I do not like it

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:

  1. Source to initial color, with cap 1, cost 0
  2. Final color to sink, with cap 1, cost 0
  3. Between opposite colors of the same cell, with cap INF, cost 2*f
  4. 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.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +26 Vote: I do not like it

    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:

    1. create a token anywhere for a cost of $$$f$$$
    2. delete a token anywhere for a cost of $$$f$$$
    3. 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:

    1. $$$S\to v$$$ with capacity $$$\infty$$$, cost $$$f$$$
    2. $$$v\to T$$$ with capacity $$$\infty$$$, cost $$$f$$$
    3. $$$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.

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you please elaborate solution of Problem C?

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it +76 Vote: I do not like it

    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
    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like 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?

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        The number of function calls to solve() is N, as every call eliminates one index.

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
          ← Rev. 6   Vote: I like it 0 Vote: I do not like it

          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))$$$.

          → Reply
          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
            ← Rev. 2   Vote: I like it 0 Vote: I do not like it

            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.

            → Reply
»
4 years ago, # |
  Vote: I like it +19 Vote: I do not like it

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)$$$.

→ Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it +211 Vote: I do not like it

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.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    That's exactly what I did. Took me whole competition to get to this solution.

    → Reply
»
4 years ago, # |
  Vote: I like it +25 Vote: I do not like it

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!

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    I also suffered from chosing to solve small D instead of large C too ;( It really hurts

    → Reply
»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +315 Vote: I do not like it

    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.

    → Reply
»
4 years ago, # |
← Rev. 5   Vote: I like it +13 Vote: I do not like it

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.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I had the same idea for B but stuck due to no proof of complexity!

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 ?

→ Reply
»
4 years ago, # |
  Vote: I like it +61 Vote: I do not like it

The problems seem too straightforward for a R2.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think C was the most beautiful problem although I got it ac only in last minute :)

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How does your top-down B solution work?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +48 Vote: I do not like it

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.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +26 Vote: I do not like it

    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"

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you for the commiseration, that makes me feel better :)

      → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      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 :(

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Feel ya :<. Are you perhaps talking about this contest :P? https://codeforces.me/contest/573/standings

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Exactly :P

          → Reply
          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
              Vote: I like it +11 Vote: I do not like it

            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.

            → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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 :'(

    → Reply
»
4 years ago, # |
  Vote: I like it +39 Vote: I do not like it

I nailed the third problem 1 second before the end of the contest, though it didn't help me to qualify

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    Same here got it in last minute and ranked 1061 but we can still hope they catch 64+ cheaters in top 1000 :)

    → Reply
»
4 years ago, # |
  Vote: I like it +11 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
  Vote: I like it +50 Vote: I do not like it

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.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +31 Vote: I do not like it

    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.

    → Reply
»
4 years ago, # |
  Vote: I like it +12 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I have solved B using a brute force solution with a complexity of around ~36sec.

Code
→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Wow, how can this pass? I just submitted your code. It is not even passing the samples.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I haven't included header files. I have just put the logic.

      I have passed both the test set using this brute force solution

      → Reply
»
4 years ago, # |
  Vote: I like it -10 Vote: I do not like it

for some unknown reasons, in problem B, my code passed both cases:

Code(warning bad formatted)

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?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +24 Vote: I do not like it

    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.

    → Reply
»
4 years ago, # |
← Rev. 4   Vote: I like it -6 Vote: I do not like it

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.

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    why so many people downvote me, what wrong did I say?

    → Reply