hxu10's blog

Google Code Jam 2022: Round 2
By hxu10, history, 3 years ago, In English

Currently this contest will start in less than 20 minutes, and I find no blog about this contest, so I decide to write one. Here is the link:
Code Jam 2022 Round 2 link

Last year I ranked 1672 and failed to qualify for round 3, this year, I feel that I improve so much, hope I can get a T-shirt. Good luck everybody, and any discussion is welcomed.

(updated: Finally I ranked 484 and won a T-shirt, so excited, see you in round 3! )

  • Vote: I like it
  • +123
  • Vote: I do not like it

Comments Comments (92)
| Write comment?
»
3 years ago, # |
  Vote: I like it +17 Vote: I do not like it

Imagine qualifying to round 2 :(

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

    master didn't qualify to round 2? i can be relaxed then as not qualified expert

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

      As a pupil, I qualified to R2 :)

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

        You had 1761 points. It doesn't count :)

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

I think I should try every problem's subtasks before trying to solve a full problem next time...

The bitmask dp and n^2 dp brutes for Jelly and I, O Bot respectively are practically free 21 points.

I opened last problem with 10 mins left and somehow coded the subtask (and fixed a WA) in the last 8 mins...

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

    How's the dp brute for IO Bot? I only think abt it for the last 10 minutes

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

      Realize that positive and negative positions are independent problems, so assume positive position. Sort a list of zeroes and a list of ones. Any operation you do is beneficial to do on closest remaining numbers. So DP is a[i][j] = the minimal cost to deliver i closest zeroes and j closest ones. From every position there are at most 5 transitions.

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

Basically my performance during this round:

Spoiler
→ Reply
»
3 years ago, # |
  Vote: I like it +14 Vote: I do not like it

Oh, the $$$O(n^2)$$$ solution failed A.

I'm disqualified and my day is ruined.

sobs

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

    I think a lot of people got AC with O(n^2) on the 3rd testset in a, because the testset did not represent the actual worst-case.

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

The analysis for test set 1 in "Saving the Jelly" is incredibly terse.

"With N≤10, recursively enumerating all N! orders that Mr. Jolly could call out the children's names is sufficient. The total complexity is roughly O(N!×N)."

How do we handle sweets that are equal distance from a given child? Backtracking? I guess the worst case is probably all children having 2 sweets at equal distance which is just a factor 2^(N/2) ~ 32. I wonder if a Python solution would pass.

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

    You can fix any order of equally distanced sweets (and try only first in that order). It follows from the proof of correct solution for large. Would make sense to mention that in the analysis, tho

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

      I thought it is provable only if one knows how to solve the large test. Thats weird..

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

        I agree, I don't understand how to provably solve small without solving also large :)

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

          I did bitmask DP for C small in the last half hour after bricking very hard. The complexity is $$$O(4^n n \sqrt{n})$$$. The dp keeps track of which subsets of kids and sweets are left.

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

            The direct bitmask DP brute ($$$dp[childmask][candymask] = \text{is reachable}$$$) that might appear to be $$$4^n \cdot n^2$$$ actually has a much smaller constant factor and works within the time limit.

            Since $$$popcount(childmask) = popcount(candymask)$$$ for any valid state we can reach, the actual complexity is something like

            $$$2^{2n + 1} + \sum_{i=0}^{n} {n \choose i} \cdot {n + 1 \choose i} \cdot i \cdot n$$$

            which is around $$$2 \cdot 10^7$$$ operations for $$$n = 10$$$. So even with an increased constant factor this runs comfortably in 10s for $$$T=100$$$.

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

            I did the same thing, though I thought it was $$$O(4^{n}n^2)$$$. How did you get the square root in the complexity?

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

              I did the same thing but already roughly analyzed the runtime benefit of having only states reachable which have the same number kids as sweets. I calculated:

              $$$n^2 \sum_{i=0}^n{ {{n}\choose{i}}^2} = n^2 {{2n}\choose{n}} = O(4^n n \sqrt{n})$$$
              → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Thanks for the pointer, that makes sense. Also, I wonder how to do it in O(N!xN). My implementation pre-computes the ordered list of sweets by distance for each child. Then, for each child in each permutation, it iterates over the sweets until it finds the first one that has not been "taken" yet. This is O(N!xN^2) and TLEs with Pypy.

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

        I did the same which didn't pass. I then tried pruning which passed first set. Code

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

    Even I was confused after reading this, but one of my friends gave an explanation which sounds intuitively correct to me.

    Suppose there exists a participant $$$P_1$$$ such that two chocolates $$$a$$$ and $$$b$$$ are equally close, both are equivalent here, but suppose there exists some remaining $$$P_2$$$ such that only a is closer than the blue candy.

    In this case, its fine if we wrongly say its impossible since there will be some other permutation where $$$P_2$$$ comes before $$$P_1$$$ and this isn't a problem. More formally, the permutation where $$$P_1$$$ is moved to just after $$$P_2$$$ in the initial permutation should suffice.

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

First problem was the worst among all codejam problems this year!

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

    No, the second was worse.

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

      Analysis of the third one was worse.

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

    Most GCJ Final problems last year are worse than the first one today :)

    I feel the problems in GCJ are worse and worse these years. Enjoy them.

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

Adhoc Jam

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

KEKL, got AC on B thanks to OEIS (https://oeis.org/A022846)

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

    number of black cells in "correct" circle is easy to count in O(n) how? :)

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

      Just bruteforce x from -R to R, write inequality and move y to left part of inequality. Then you Will have y <= sqrt((R+0.5)*(R+0.5)-x*x))

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

    Holy shit, totally forgot oeis

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

    I got the same sequence without OEIS, but don't know how to use it during the contest.

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

Ugly A and B. And problems were too difficult to properly choose the top 1000.

What's the brute force for $$$N \leq 10$$$ in C? Trying every order of children is not enough because of ties. Do we just say that there can't be many ties? What's the proof? I implemented $$$O(2^{2n})$$$ dp. EDIT: solved in comments above https://mirror.codeforces.com/blog/entry/102849?#comment-912506

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

    I think I have a different bash than the one described in the comments? I iterated over all possible pairings of children to sweets. Then I made a graph based on whether each child had to be before another child based on their distances and ran topological sort. Overall this takes $$$\mathcal O(N^2 \cdot N!)$$$.

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

    U can try to every possible assignments from children to sweets and then reduce the problem to some toposort problem where u add edges from sweets to children if its closer than the the assigned sweet.

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

Ugh failed C because my construction method was bad.

But If i keep the bad construction method (basically just look through all people and put it if min edge), but when I detect a bad state I just shuffle everything and redo the matching, it passes.

(Bad construction worked for small :( so though it might work, since I was sorting edges by distance, and I though the algorithm would do something so that it ensures the construction works, but clearly wrong lol)

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

    Ah even just redoing the matching seems to work, no need to shuffle. I think it's because the matching algo finds min lexicographic matching and since I sorted by distances there's gonna be at least one edge that's minimum in the cycle that includes 1 (since it's lower lexicographical)

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

Did anybody else solve B (Pixelated Circle) by precomputing prefix sums over draw_circle_perimeter in $$$O(R^2)$$$ and hardcoding them?

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

    I didn't hardcode solutions into the source, but I did run a quadratic-time pre-computation at runtime. It was a bit more complex than the official solution, checking whether every possible (x, y) pair (up to some symmetries) would be left as a hole by draw_circle_filled_wrong.

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

Let me explain how I experienced this contest.

I finish the whole problem 1, and small test set of problem 2 very quickly. Then I proceed to problem 3. luckily, I can come up with small problem test set (just bitmask DP), but have no idea about large test set. Then I decide to choose problem 2, large test set. I have 75 minutes, and I think is enough. The bad thing is that problem 2 large test set is so hard， and I cannot make it till the end.

Then it takes more than 6 minutes to unveil the hidden test set, if more than 1000 people solve large test set of problem 2, I am doomed, so it is the longest 6 minutes I have ever experienced.

Luckily, only 200+ solved problem B large test set, and my final ranking is 484. I am so excited, it is the first time I proceed to round 3 and win Code Jam T shirt! The only regret that I have is that I should tried Q4 for small test set, not struggling for Q2 large, it's much easier.

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

So, my solution for 3rd problem:

For each child sort the allowed edges from closest to the farthest (ties in any order) and run Kuhn algorithm (without heuristic to pre-allocate arbitrary matching). Idea is to claim that it's valid to call this edges in some order.

Can somebody prove to disprove it?

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

    Did it pass? I did the same and it only got me first subtask

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

    I also had the same solution. Proof is based on the claim that in min cost perfect matching, there will be some student that'll be matched to its closest jelly. Then we can use induction.

    Let best[x] denote the closest jelly to student x, and match[x] be the assigned jelly for student x. Also, for a jelly y let match[y] be the student who gets y.

    Then, if you keep going form x to best[x] for each student x, and y to match[y] for each jelly y, you'll eventually get a cycle, augmenting which will result in a better cost. (For each student x in the cycle you're replacing match[x] by best[x])

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

      I think I understand from your explanation, why "there exists matching" is equivalent to "there exists a valid order of calling children".

      But what's not clear for me, why unmodified Kuhn algo will find it (and will it always) For example, if we had a blackbox which just find any matching if it exists, it won't be enough. E.g for case

      0 0
1 1
100 100
0 0
1 1

      we are allowed to print

      1 2
2 3

      or 

      2 3
1 2

      but not 

      1 3
2 2

      which is also valid matching

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

        Ah! I confused Kuhn's with Kuhn–Munkres. In my solution, I had costs equal to the rank in priority order, instead of just sorting the adjacent edges and running Kuhn's.

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

          I thought about that but but though O(n^3) will be too slow. I know Kuhn also technically cubic, but it's hard to achieve big number of edges and NM complexity at the same time

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

        A matching is invalid if and only if there is a augmenting cycle that gives every student in it a closer jelly.

        Kuhn with your edge ordering will never produce such augmenting cycles: If an augmenting path were to produce such a cycle, it could instead have gone the other way around the cycle, which would use a lower-index edge at the vertex where it first enteres the cycle. In particular, Kuch with your edge ordering would find this augmenting path instead of the original one. (In other words, we could xor the augmenting path with the cycle to get a different augmenting path, that Kuhn would find first.)

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

Undoubtedly one of the CP contests of all time

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

Not a well balanced set at all. A huge portion of people qualifying are through just or mostly from partials (including myself). That wouldn't be an issue if the subtasks weren't so terribly bland. I don't recall doing anything smart at all the entire round. Seems it all came down to who decided to skip the full solutions sooner.

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

How does $$$O(N^2)$$$ TLE/MLE A hidden???

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

    Because $$$T$$$ is $$$100$$$ and $$$N$$$ can be as big as $$$10^4-1$$$. So $$$T\cdot N^2$$$ can be as big as $$$10^{10}$$$, which is too slow.

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

    My $$$O(K)$$$ solution passed.

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

      Same lmao

      If they didn't want it to pass, they shouldn't have given us 20 seconds!

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

        Or they should have given the usual $$$N\leq 10^5$$$ if they wanted $$$\mathcal{O}(N)$$$. Then no one would have even risked $$$\mathcal{O}(T\cdot N^2)$$$ for 20 seconds.

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

One of the worst rounds I ever solved:
A is simple trash: you can't even easily fill the board to brutforce. I got idea, but it's really hard to implement (look at tourist's 138 lines, for example). I thought that last year's problem with clocks was bad, but forget, that was brilliant task
I was late 15 minutes, but when I opened standings, I saw only about 5 people who got AC. It's awful. First problem should be easier
B is trash too: no idea in first subtask (just copy the code from statemnet and count diff), second is hard math with some handwaving proofs and praying that round and sqrt work fine: 

bool correct = x * 1ll * x + y * 1ll * y <= R * 1ll * R;
//bool correct = round(sqrt(x * 1ll * x + y * 1ll * y)) <= R;

Note that result in different when using NORMAL check if point is in circle

C: could be nice problem. But how to prove that N! in small works??? I saw N = 10 and thought about permutations, but moment later I found example with equal distances that makes this solution run in N!^2. Solving hard? Guess with AC because nothing else?
D: first subtask is nice. But large is some dp optimization with hard and handwaving proofs again.
I liked D problem, but one(last!) out of four?
Also using of subtasks was really strange: you either code some easy bruteforce or solve full

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

    For A I think I came up with a reasonably easy to implement solution. If N <= 5, just hardcode all solutions. For larger N+2, all lengths can be achieved by going to the top-left corner of N – either by not using shortcuts at all or going immediately right and down; so we check if we can still finish by avoiding shortcuts on this level and reduce the problem to the smaller one.

    Still didn't enjoy the task though.

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

      Its possible to code it fairly cleanly, without requiring any hard coding of small $$$n$$$.

      Basically realize that the difference when we move from a cell to the "inner" adjacent cell depends only on

      1. The side length of the current subsquare.
      2. The side we're on (top / bottom / left / right).

      If you count these, for a given side length $$$s$$$ you get:

      • top: $$$4s - 5$$$
      • right: $$$4s - 7$$$
      • bottom: $$$4s - 9$$$
      • left: $$$4s - 11$$$

      Now we can realize that all odd numbers from $$$1$$$ to $$$4n - 5$$$ exist in this set. Since all skips are odd length, we can only save an even distance over the normal path.

      So now we can treat this as having a decreasing set $$${x, x - 1, x - 2, \ldots, 1}$$$ (just multiplied by 2) and we want to select some cells such that their sum is $$$y$$$. Clearly the easy greedy of taking the largest cell we can at any stage works fine.

      As for the actual cells we move through, we can realize the middle element of each initial layer works on any layer. Their value for the first layer is just $$$\frac{n + 1}{2}$$$ for the top side plus $$$n - 1$$$ for each of the remaining sides on the layer. Then calculating this as we move to inner layers is trivial using the previously calculated side length values.

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

    Though I also did not like the problems AB, what you described was not the case for me:

    In problem A, after some thought, I ended up with smth like 20 lines of meaningful code, which involved no cases (I do not consider printing IMPOSSIBLE when needed as "handling cases").

    In problem B there was no need to pray for precision, it was not so difficult to rewrite inequalities of type round(sqrt(x)) < y until all sides are integer.

    Honestly, I do not know how to guess the solution to C without proving it. It probably depends on the solution itself. The only unproven thing about ABC I had during the contest was the fact that my solution for C was fast enough (Hungarian).

    You may refer to https://youtu.be/AaweAsTZT8o for details of my solutions, once it is uploaded.

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

such $$$O(n^2)$$$ passed in IOBot

vector<int> p01(n+1, -1), g01(n+1, -1);
for(int i=n-2; i>=0; --i) {
	if(s[i] == 0) {
		for(int j=i+1; j<n; ) {
			if(s[j] == 1) {
				p01[i] = j;
				break;
			}
			if(p01[j] == -1) break;
			j = p01[j] + 1;
		}
	}
}
→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Had cleared round 2 with 100 points , in my dream :)

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

It could have been worse... (no pun intended)

Round 2 last year was actually much worse. There were 2 cakewalks, 284 full scores and solving 3/4 tasks was not enough to qualify.

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

    giga plus

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

    I thought this year's round 2 was much worse than last year's. At least last year, the problems were ok. This year, I did not enjoy any problem I attempted (for the same reasons that many other people have commented above). Halfway through this contest, I realized I wasn't even having fun anymore, even though I eventually qualified.

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

      My contest experience is summed up by me repeatedly asking myself "What is happening???" for 150 minutes straight. This is despite having the right ideas for problems A and B early on and eventually implementing it. My family probably thought I was delirious. Well, they are right.

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

Problems so bad, after 2 min of contest I lost all motivation to solve problems. (Though, as jqdai0815 said, it could be worse)

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

I am astonished as to why highly experienced contestants could not solve both test sets for B. One could brute-force the solution locally to precompute all possible answers from $$$1$$$ to $$$10^5$$$ and simply look up the answer in an array in the actual submission.

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

    The limit on the source code is 100KB. You only get 1 byte per possible answer for precomputation.

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

      Oh I totally missed this point. Although you can still use some tricks to compress the data (python zlib for example).

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

        Compressing doesn't improve much when numbers are mostly random. e.g. simply try zipping a file containing all answers only reduce the file size by 2x, which is not enough for this problem.

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

      there is a nice precomputation solution by dacin21, which uses some clever trick (if I understand correctly he only pasted prefix sums for n divisble by 20 and then computes the rest when needed)

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

        Yes. I used that approach too. I felt that computing the whole table was quite easy, but you have to compute the rest (answer for small interval) for each tests as well, I think that part is pretty tedious to write.

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

      Each wrong circle, starting with $$$r = 2$$$, has either 4 or 8 more black cells than the previous circle; therefore, it can be encoded using 1 bit per layer. Here is the working code; I grouped bits by sextuplets encoded by [0-9A-Za-z.,].

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

Shit round!! It wasn't even a CP round. People qualified for "global top 1000" using partial points which involved translating given pseudocode or some kind of stupid brute force.

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

Horrible problemset

→ Reply
»
3 years ago, # |
  Vote: I like it +94 Vote: I do not like it
Round 2 is a different kind of a challenge, with no easy points on the table

Interestingly enough, I disagree with "no easy points on the table" in both cases. Last year had a lot of full-scorers, and this year has at least B-small.

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

During the contest: Made a lot of mistakes, bogged down in implementation, barely got through problems A and B, see my rank is 2000, giving up... After system tests: Jump up to rank 406

Thanks, problem B! Finally getting that GCJ T-shirt

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

    Svlad_Cjelli I had the exact same experience! Was so despondent when my rank was 2000+ while struggling with problem B thinking way over 1000 people already had full submissions. Kept trying to go for B in full and when I submitted problem B and my rank was still 1800, gave up hope. Totally shocked after score reveal.

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

Nice comeback bro

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

Congrats with qualifying! Will be there next year too :)

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

I was rather surprised that I succeeded on D large: my solution is quadratic time (basically the official solution for test set 1), just optimised to use linear space.

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

Man. I get the whole visible/hidden thing adding excitement but this was a contest that just rewarded giving up on large solves. I was bitten in the backside for sticking too long with B large because it appeared highly likely I'd need it; turns out I could've just brute forced C small and been fine. I don't feel like brute force solving should be deciding things at this stage in the competition (though I wish I had done it).

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

    Brute force solving shouldn't, but understanding that you are better off reading all problems and submitting all of the easy subtasks probably should

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

      Disagree. That entirely depends on the contest, and only with hindsight of how many large solves each question has. Last year (when I did qualify) had I followed that advice I would have wasted valuable time submitting small subtasks and failed. This year, it transpired after the contest that such an approach would have sufficed, but when the hidden scoreboard said > 2000 solves on B, there was no way of knowing that.

      This contest rewarded giving up easily on large solutions. Last year's rewarded sticking at the complete problems. It feels like going to the effort of learning more complex techniques and honing implementation skills essentially counted for nothing — the cheap points won the day. To me that feels hollow, and not how a CP contest should be settled.

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

        It does depend on the contest and I completely agree with your second paragraph, but if you wanted to maximize your result you should've noticed that 10 + 11 easy points is greater than 16 probably harder points on a weird problem and you should've prioritized the easy ones.

        → Reply