Google Code Jam 2022 Round 1C

Just as I thought I almost qualified in round 1B for round 2 with 85 points, here comes round 1C

Yep, its that hard

only got 19 points and cannot even get full score for one question

• 37 hours ago, # ^ | Same. Although, I didn't participated, but I was solving the problems and they felt harder than 1A and 1B. First one felt constructive to me and more, while in second one, you just have to observe that you can do it in at most 22 operations, only if either condition is true: sum≠0sum≠0 or sum_sq=sq_sumsum_sq=sq_sum.

  • 37 hours ago, # ^ | ← Rev. 2 →   +3 The second problem seemed to me like a bit of mathforces (play around with the cases k = 1 and k = 2), while the first one was a greedy/constructive which had a few key details that I initially missed. This somewhat bogged me down and because of this I have a slightly large penalty time.

• 37 hours ago, # ^ | ← Rev. 2 →   +1 CCAAAAATT Isn't it correct ? still WA (:

  • 37 hours ago, # ^ | Yes, my first attempt treated this as impossible. I was thinking hard to find a failing case.

  • 37 hours ago, # ^ | You lost one letter A somewhere. Need 5 letters A, but only have 4 in the answer.

  • 33 hours ago, # ^ | I found your profile on GCJ. Then downloaded and stress tested your latest contest submission. It fails the following testcase: 1 6 DD CAA BBB D DB C (reports IMPOSSIBLE, while DDDDBBBBCCAA is a valid answer).

• 37 hours ago, # ^ | i got WA from 1 4 AB BC CD AA

  • 36 hours ago, # ^ | I did toposort, still WA :(

    • 36 hours ago, # ^ | We cannot perform toposort because the graph might contain cycles.

      • 36 hours ago, # ^ | then the answer won't be possible if graph had cycles, bcz then there would be no possible way to arrange them continuously

        • 36 hours ago, # ^ | What if all the input strings are "A". Then even though it cannot be sorted topologically, but the answer is still possible.

          • 36 hours ago, # ^ | Yeah, that's why I didn't try toposort either. Although I do think some high rated user may have done it in that manner. If anyone has a submission using toposort approach please do share.

            • 36 hours ago, # ^ | ← Rev. 3 →   0 code I upsolved it later. I didn't apply toposort directly, I preprocessed it a bit. This got accepted.

    • 36 hours ago, # ^ | Careful on inputs like AB DE BC to keep the Bs together (even though AB DE BC is also topologically sorted).

      • 36 hours ago, # ^ | ← Rev. 2 →   0 ya i got my mistake , i wasn't checking for multiple components 6 RTTYYUUUII KLZZZXXCCV QQQWWWWEER OOPPAAASDD VBBBNNNMMM DFGGGGHHJJ -> QQQWWWWEERRTTYYUUUII + OOPPAAASDDDFGGGGHHJJ + KLZZZXXCCVVBBBNNNMMM

• 29 hours ago, # ^ | While R1C might indeed be harder than the previous two rounds, you can't just compare the scores like that. There are 3000 strong competitors that had already qualified to R2, so they didn't participate in R1C. Had they participated, the qualifying score could very likely be higher than 34. I think that if you want to compare the difficulties of the rounds, you should compare the solve times of the people in the first couple hundred places.

• 37 hours ago, # ^ | BTW, how to solve without guessing. I got this formula: Spoiler

  • 31 hour(s) ago, # ^ | What is this sorcery?

• 31 hour(s) ago, # ^ | ← Rev. 2 →   +21 Let's look at the case k=2k=2. Let ss be the sum of the numbers from the input and s2s2 the sum of the squares of the numbers from the input. We are interested in finding out xx and yy such that (s+x+y)2=s2+x2+y2.(s+x+y)2=s2+x2+y2. After expanding the left term and doing some clean-up, we get: s2+2sx+2sy+2xy=s2.s2+2sx+2sy+2xy=s2. Let's consider $x$ as a parameter; then, we can rewrite yy in terms of xx as follows: y=s2−s2−2sx2s+2x.y=s2−s2−2sx2s+2x. We are interested in finding an $x$ such that there is an integer yy which satisfies the relation above. Since yy needs to be an integer, 2s+2x2s+2x must be a divisor of s2−s2−2sxs2−s2−2sx (and 2s+2x2s+2x must obviously be non-zero). We can rewrite yy as follows: y=s2−s2−2sx2s+2x=s2+s2−2s2−2sx2s+2x=s2+s22s+2x−s(2s+2x)2s+2x=s2+s22s+2x−s.y=s2−s2−2sx2s+2x=s2+s2−2s2−2sx2s+2x=s2+s22s+2x−s(2s+2x)2s+2x=s2+s22s+2x−s. Now we are only interested in $2s+2x$ being a divisor of s2+s2s2+s2. Note, however, that s2s2 and s2s2 have the same parity. Then s2+s2s2+s2 is even, so 2 is one of its divisors! We can thus find xx such that 2s+2x=22s+2x=2 and we get x=1−sx=1−s. By replacing xx with 1−s1−s in the relation above, we get y=s2+s22−sy=s2+s22−s.

  • 29 hours ago, # ^ | So, for K>=2, the answer is never IMPOSSIBLE?

    • 29 hours ago, # ^ | Never.

      • 23 hours ago, # ^ | The answer can be impossible when s2+s2≡1(mod2)s2+s2≡1(mod2)

        • 18 hours ago, # ^ | I guess that case cannot be encountered since s2s2 and s2s2, both have the same parity as is mentioned by Alex.

          • 18 hours ago, # ^ | ← Rev. 2 →   0 Oh, didn’t read that part. Thanks for pointing it out! Edit: Actually, the user is asking if the answer is never IMPOSSIBLE for K >= 2, but that is not true.