Imakf's blog

Codeforces Global Round 24
By Imakf, history, 2 years ago, In English

Hello Codeforces!

On Nov/26/2022 17:05 (Moscow time) we will host Codeforces Global Round 24. Note the unusual time of the round.

It is the sixth round of a 2022 series of Codeforces Global Rounds. The rounds are open and rated for everybody.

The prizes for this round:

  • 30 best participants get a t-shirt.
  • 20 t-shirts are randomly distributed among those with ranks between 31 and 500, inclusive.

The prizes for the 6-round series in 2022:

  • In each round top-100 participants get points according to the table.
  • The final result for each participant is equal to the sum of points he gets in the four rounds he placed the highest.
  • The best 20 participants over all series get sweatshirts and place certificates.

Thanks to XTX, which in 2022 supported the global rounds initiative!

The problems were written and prepared by Cocoly1990, waaitg and Imakf. 👀👀👀

We would also like to thank:

Round Information:

  • Duration: 2 hours and 30 minutes 🔥🔥🔥
  • Number of problems: 8 problems, one split into 3 subtasks 🤯🤯🤯
  • Score distribution: $$$500$$$ — $$$1000$$$ — $$$1500$$$ — $$$1750$$$ — $$$2250$$$ — $$$2250$$$ — $$$(2000+500+500)$$$ — $$$3500$$$ 🤤🤤🤤
  • There is an interactive problem, so please see the guide of interactive problems if you are not familiar with it. 🤭🤭🤭

As always, hope you all gain non-negative ratings $$$\Delta$$$ in this round! 🍾🍾🍾

UPD1: Editorial

Announcement of Codeforces Global Round 24
  • Vote: I like it
  • +513
  • Vote: I do not like it

Comments Comments (174)
| Write comment?
»
2 years ago, # |
  Vote: I like it +18 Vote: I do not like it

Auto comment: topic has been updated by Imakf (previous revision, new revision, compare).

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

As a participant, I hope the problems are interesting!

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

As a tester, Imakf 🤤🤤🤤

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

omg 3 subtasks round

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

As a tester, I can say that the problems are all very interesting. Thank you for your participation.❤️❤️❤️

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

As a tester, I must say that the problems are all very nice.

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

Genius lgm problemsetter imakf, I'm a big fan of yours! orz imakf, orz waaitg, orz Cocoly1990!

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

So basically everyone who solves $$$G2$$$ and $$$G3$$$ gets $$$150$$$ more points each.

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

As we all know, a problem can be split into subtasks only when it's difficult to solve completely.

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

No matter how the round turns out, had to upvote for the emojis 😌

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

As a tester, I have to say that all the problems are very interesting!

orz Cocoly1990, Imakf and waaitg!

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

    Wait are you the guy who (up)hacked 120 submissions in my round?

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

      Yes, I uphacked some submissions using slow-output functions or languages in your round.

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

Note unusual timing

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

As a writer,i want contribution.

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

omg emoji round

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

As a tester I can say that you will really enjoy the problemset. I would suggest you to read all the problems. Problemsetters and errorgorn have tried their best to make statements easier to understand.

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

As a tester, Orz Cocoly1990.

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

Editorial filled with emotes lol... My reaction for the Global Round as usual ^,^

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

Orz Imakf <《^,^》>

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

The last line is completely illegal, how will be the ratings gonna balanced than?

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

As a tester, i think that the problems are all very interesting.

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

All the problems are very interesting!

orz Cocoly1990, Imakf and waaitg!

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

Consecutive rounds! :O

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

Too many emojis, downvoted. Hope the contest is good tho.

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

As a tester, I'm still curious how the authors found me for testing, I didn't know any of authors :D
btw, don't miss this great, well prepared round from such awesome authors!

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

As a first time tester, this is definitely the best round I ever tested

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

Note :: UNUSUAL TIME OF CONTEST

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

Brillant use of emojis

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

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

omg emoji round

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

Oops

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

as a participant I hope I will get +100 delta.

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

I want another ConstructForces like 836 div.

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

There are 10 subtasks, but I have a feeling only 4 would be doable by < master. Let's see, excited. Hopefully master tomorrow!

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

Thank you coddeforces

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

hoping to solve upto D!! :)

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

hopefully no choking this round

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

Celtic /se

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

Chinese round! /tyt

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

Hello everyone, I am a beginner programmer. I don’t know about the difficulty of Global round 24 . Anyone could explain about difficulty of problem in this round.

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

Because of my university online exam in contest time. I can't participate in this round. Feeling sad.

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

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

https://mirror.codeforces.com/contestInvitation/e949aed8ba775616b4e21b10a0c1480426f6ff8a

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

Emojforces ☺️

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

Hope for fun with the interactive one and (3 subtasks) one .Best of luck everyone.

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

nice emoji

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

Does score distribution imply that I should skip to G1 after D.

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

Everyone for good luck!

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

omg Imakf round

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

As a participant, this round is my decisive battle.

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

    I lost this game. Though I will got $$$+\varepsilon$$$, my place is around 200 (without any FST).
    Anyway, the round seems good. Though some problems are typical, I love E! Thanks for the writers' and testers' amazing works!

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

don't expect much you will do better.

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

G1 easier than F, E .. intersting :)

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

So G has 3 subtasks? XD

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

The problems are good quality.It suprised me very much.I am looking forward to more contests!

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

Solution videos for problem B on youtube combined have over 1600 views.

Unfortunately, people who uploaded videos didn't show their usernames, but one of them has to be vedantkakade.

MikeMirzayanov

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

The top standings in this contest are a good example of why the scoring system needs to be reformed, in my opinion.

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

    Why is that? Looks like several top scorers were saved by the pretests which allowed them to resubmit. But the penalty put them beneath other submitters who didn't need as many resubmissions.

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

      You have mentioned just penalty aspect when OP (brunovsky, correct me if I'm wrong) is talking about general scoring mechanism. Which is, basically, how many points you will get for solving particular problem at particular moment. The issue is well-illustrated by top-1 scorer who gets more points for speed-solving D (1666/1750) then for late solutions to much harder F (1523/2250) or G1+G2 (1536/2500).

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

:|

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

    Contest is not over yet. Delete it.

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

    There are people who does cheat but using different ways but you my guy did this in the comment section....you could have waited for the round to be over

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

Why is div1+2 D so hard again?

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

    Yeah It was hard and was also interesting. Couldn't solve it though.

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

the solutions to the first three problems were on youtube before the test was over, I think this interferes with the scoring of the round as many can copy and paste the solutions.

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

What was the logic in number B?

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

    If all the numbers have common divisor or factor, then the ans will be maxElement / commonFactor or else ans will be maxElement. Here you can find if the numbers have common factor by taking gcd of the whole array, and if gcd > 1 then it does have a common factor.

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

How could C be approached?

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

    You can think of dividing the vertices into 2 parts. eg. 1 2 2 3 3 4 4 4 5 6 7 7 9 can be divided into two part as following :

    IMP : sort the vertices by their weight

    1) 1 and 2 2 3 3 4 4 4 5 6 7 7 9, Now you can connect the left part's vertices to all the vertices of right part but you cannot connect any vertices of the same part, so total possible edges = len(left_part) * len(right_part) = 11

    2) 1 2 and 2 3 3 4 4 4 5 6 7 7 9, but this configuration is invalid, as you can imagine that left's 2 is connected to right's 2 & 9 so basically you can go 2 => 2 => 9. So here you have to make sure that partition are done in such a way that there are no equal element in both partitions. left_part is strictly less than right_part elements.

    so best configuration we can find is : 1 2 2 3 3 * 4 4 4 6 7 7 9 which is 5 * 7 = 35

    Also edge case is when you can't partition the array. i.e all the elements are equal, so at that time just output n / 2 as you cannot connect more than 2 vertices

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

Scariest problem D

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

How to solve D?

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

    Solution for D:

    Observe:when the deleted pegs firstly form a continuous segment with a length of $$$l \geq n/2 $$$,we get a scheme.

    Enumeration length $$$l=n/2,n/2+1,...,n-1$$$,let's calculate the answer when the continuous segment's length is $$$l$$$.

    First,calculate $$$cnt$$$,which is the number of pair $$$(a,b)$$$ satisfying $$$a+1+b==l,a,b<n/2$$$.

    Then select some pegs outside this continuous segment that can be deleted.

    Suppose $$$i$$$ pegs(outside) have chosen, there are $$$C(n-l-2,i)$$$ schemes.

    The total answer is $$$cnt * \Sigma ((l-1+i)! * C(n-l-2,i)) $$$.

    Because the beginning of a continuous segment can be any peg, we need to multiply the final answer by $$$n$$$.

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

how to solve B?

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

Anyone has the answer in D.(answer like O(1))?I mean an explicit formula

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

What a tough contest :(((

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

C was quite tough to spot the right answer.

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

    I do agree

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

    i was going in the direction of frequency and hashmap that how many smaller elements can be between 2 greater elements or how many greater can be between 2 smaller

    please provide a hint

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

      The brief idea is to sort the array and split it in half then connect every edges between two halves. This won't violate the rule. Now you have to consider the case where there are same elements (which is a little bit complicate).

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

    You're right.I spent an hour and a half doing problem C.

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

    I guessed the solution but I can't prove it

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

Solved problem F in a Div 1+2 Round for the first time! Yay

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

How to solve Problem D when n % 2 = 1?
In even cases, ig we had to consider diagonals, so, in the odd ones triangles?

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

    In fact, it is wrong to consider diagonal.

    Consider $$$n=6$$$,$$$[1,3,5,6]$$$ is a valid scheme,although $$$1,3,5$$$ deleted all diagonals.

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

      Oh, I was thinking about calculating the ways in which the game ends with either a diagonal or a triangle 'breaking'.
      In the above case, the triangle 4-2-6 'breaks' in the end.
      I forgot to consider 'triangles' for even cases as well.

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

D actually ended up being fun lol

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

    how did you solve it?

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

      combinatorics

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

      after all operations we must be left with some chunk with size $$$\le (n + 1) / 2$$$ (and possibly gaps in between).

      The last operation must've been removing a peg in the diametrically opposite chunk.

      Then just count the number of ways to do this using binomial coefficients and factorial

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

Only solved till C but my best div 2 round so far.

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

Any hint of problem C , (PLEASE DON'T GIVE COMPLETE SOLUTION)

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

    You should think about the GCD.

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

    Quick sort partitions

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

    If you need more help just reply!

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

182673131

what was the problem in this approach can anyone tell ? i was checking if all were divisible! if then ans is max/min else ans is max why i got WA in this approach didn't understand

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

    answer is $$$\max(S)\div\gcd(S)$$$

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

      what if i don't go for GCD then?

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

        then you get WA...

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

          got it [15, 20, 25] here 20 & 25 is not divisible by 15 but all are multiple of 5 so answer is 25/5= 5 that's why gcd works

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

Here is some feedback on the problem set:

  • A: Nice easy problem. First time in my life I submit without checking the correctness on the examples.
  • B: Somewhat standard, but ok (set of integers, operations, what can you get? -> gcd). I enjoyed it.
  • C: Ok problem. I did not prove my solution, though I think that I can prove it in 5 minutes.
  • D: Standard problem, appropriate difficulty. I am not a fan since I knew what to do immediately after reading the statement (and then I did a mess... but that's another story).
  • E: Wonderful. I sent 3 solutions, and I thought I had a proof for all of them. But the first two were wrong (not a bug, the algorithm was wrong). I really enjoyed this one. One is naturally lead to try and "get the biggest possible number" but the correct strategy is to go backward and I needed quite some time to understand it.
  • F: Ok problem. The statement is far from interesting. The observation that we can understand if $$$i,j$$$ are adjacent by looking at $$$f(i,\cdot)-f(j,\cdot)$$$ is cool (I was lucky and it was the first thing I tried). Then, I passed the pretests with a randomized solution which I am not 100% should pass the tests (since it may be too slow).
  • G: Thought about this one for 30 minutes straight. Not a single idea. I cannot solve it even with $$$n$$$ queries. Truly seems impossible, great problem. [edit] After reading the solution, I don't think anymore it is a great problem, still a very nice one though (because it seems totally impossible without the right idea).
  • H: Not read.

Overall the contest was very well prepared, the problems were nice, and the difficulties were on the spot. Congratulations to the authors!

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

    On G, I had the following order of observations:

    1) You can find the maximum value in ~10 queries

    2) There are only at most two values which are unpaired with $$$k=2$$$: $$$1$$$, and potentially the maximum value.

    I couldn't finish from here in the contest, but someone gave me a hint afterward: The idea is that we can query $$$[a, m]$$$ and $$$[m+1, b]$$$ for a range $$$[a,b]$$$ and $$$m = (a+b)/2$$$. This tells us how many unpaired values there are on the left and right; since there are atmost two unpaired values, we can go to the correct side.

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

Auto comment: topic has been updated by Imakf (previous revision, new revision, compare).

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

Please dont do cheating guys,it hurts alot especially in rankings and ratings

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

Why does taking gcd of the whole array and then dividing it by the last number work in Problem B?

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

    $$$\gcd(x,y) \vert x$$$ and $$$\gcd(x, y) \vert y \Rightarrow \gcd(x, y) \vert (x - y)$$$

    Thus any element we add will still be a multiple of the $$$\gcd$$$ of the entire set.

    However, by the Euclidean algorithm, we can always get $$$\gcd(S)$$$ to be in $$$S$$$ after some number of operations.

    Thus we can get $$$\max(S) - k\cdot\gcd(S)$$$ to be in $$$S$$$ for any $$$k=0,1,2,\cdots,\frac{\max(S)}{\gcd(S)}-1$$$ (For greater k values the number would not be positive)

    Thus the max size of $$$S$$$ is $$$\max(S)\div \gcd(S)$$$

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

      Thank you very much, great explanation!!!

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

    It is kind of clever use of gcd algorithm that one learns in high school, i.e. gcd(x,y)=ax+by for some a and b.

    Note that if 1 is in array, then you can construct any element from 1 to a[n-1], and if you can construct 1 then also you can construct any element from 1 to a[n-1]. (basically you can construct 1 only if two elements have gcd 1 in the array).

    Similarly, you can work it otherwise.

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

    I don't have a formal proof, but this is what I thought of :

    Base : If array has 1 or we managed to generate 1 then it is possible to generate each and every element from 1....max(array).

    Now let's do some case work :

    1) gcd is 1 for the whole array, so it means that there lies 2 elements which does not have common divisor, so let's assume it as 4 and 599, now you can generate values as 599 — 4, 599 — (4 * 2), ....., 599 — (4 * x), now this 599 - (4 * x) term will be surely < 4 as we already know that we can't reach to 4 as 599 is not divisble by 4. so any value of 1, 2, or 3. Now in case of 1 & 3, we can generate 1 by either (4 — 3) or (4 — 1) = 3 then (4 — 3) = 1. so we generated 1. Now if we have 2 then (4 — 2) is 2, but again 599 & 2 are not divisble, so 599 — 2, 599 — (2 * 2), and ..... we will get last value as 1. So in short whenever we have non divisible numbers we can go upto 1 for generation by successive subtraction.

    2) gcd > 1, let's say gcd is 5, so now whatever you do in the array your subtractions will result into a multiple of 5 as when you subtract two number which has x as common divisor, you will have a result that will also be divisible by x. so you have to output the number of multiple of gcd that you can fit in the array

    so ans is => max(array) / gcd(array)

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

Who else agrees that the 2nd sample test case for problem C should be explained as well

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

So close to solving D.

if n is even, go over all pairwise points, pretend this is the arc when it first touches the blue pin. We know that this can only happen with the smaller arch, and that the last point removed before it gets to this arc must be one of the opposite pin with the smaller arc. From there just do nCk and multiplies with factorial of two sets of points.

if n is odd, solve similarly, except the outer arcs count before getting to this arc is the number of edges of adjacent pin instead of the number of points.

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

    Don't loop over all pairwise points, but instead over all possible arc lengths when it touches the blue pin and then multiply by n.

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

a similar problem as problem B: https://mirror.codeforces.com/contest/347/problem/C

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

    A similar problem appeared recently but with lower constraints so you could simply add the missing numbers while you there's a missing number. I couldn't find it but I'm pretty sure it's in a CF round that happened durin 2020-2022.

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

    mmm an even more similar problem lol https://mycode.prepbytes.com/problems/sorting/ELMT

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

Thanks for the fast editorial! Also thanks for the round.

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

Problem E:

How can the answer of input

1

3 5

3 2

2 1

1 2

be "YES"?

I got WA2 and this is the case I failed :(

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

    Use permutation [2, 3, 1], then 1, 3, 5 can be colored in this order.

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

Thank you for problem G!
Actually reloaded the page a couple of times to make sure it's $$$\le 30$$$ queries, not $$$30 n$$$ or something.
The feeling of just how impossible the problem seems at first... priceless.

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

Ratings updated preliminarily. We will remove cheaters and update the ratings again soon!

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

B is pretty hard for usual B imo. It’s an easier version of a 1800 rated problem. And that problem has negative numbers

it’s so bizarre that B has so many submission.

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

finally a round i enjoyed :)...

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

Completely forgot that on resubmission previous submissions are skipped, Resubmitted D for stupid reason, got -50 and +25 minutes.:(

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

Thanks for the great problems and well-balanced round!

The only negative thing I noticed is score distribution. Complexity jumps between A-B and B-C is definitely smaller then the ones between C-D and D-G1 (cannot say about other problems), but the point difference is two times bigger.

Anyways, kudos to the problem setters and testers for an awesome job!

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

Thanks for the round! I think F is incredible, and C is fun too.

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

Problem D really pegged me.

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

Intially I thought of Bipartite Solution

">" -> Red edges, "<" -> blue edges and then For "=" I did not understand which color to assign and thought Bipartite wouldn't fit.

To add Fire to above thought. I came up with a pattern which is giving solution for 2nd example

1) sort the array 1 2 2 4 5 5 In Most of Hill and valley problems this pattern helps 2) And use the pattern [a1,a2,a3,a4,a5,a6] => [a1,a4,a2,a5,a3,a6] 3) In above pattern if we connect edges to adjacent and also connect each vertex with every vertex alternatively I got all the edges so dumped the idea of bipartite and tried to code the above approach

What is that C question ?. I tried it for almost one day. I went nowhere

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

    I did it considering a bipartite graph(maximum edges it can have is x^2/4 , x->vertices). Check out my submission for this problem.

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

UnRated?

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

For me, E is very very easy, even easier than C. I can't understand why people struggle with it. When I saw problem E I was like, well, this problem can't be just a straightforward greedy problem, there must be something that I missed, but indeed it is. You just sort the colors by $$$x$$$ and then find the maximum position that could be colored by colors other than $$$1$$$. I did struggle a lot on C and D. In C I didn't realize that the resulting graph could only be a bipartite graph, In D I ended up with a much more complicated approach using Inclusion-Exclusion Principle. To be clear, I'm not complaining, I'm just curious that maybe some people would have the same feeling as mine.

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

I think my F would be a little better than std.
The beauty of this problem lies in $$$f(x,x)$$$. It is not difficult to find that the closer the point to $$$x$$$, the more times the point is repeated, and the different $$$x$$$, the different times each edge is repeated ~~ (isn't it obvious) . So we can actually figure out the distance between any two points based on this property. Here's an example (in the figure, the red number indicates the number of counts) :

You will find that all the edges are repeated the same number of times except for the number of times that the edges between the two $$$x$$$are repeated, so you can consider the inclusion repulsion, which is actually $$$dis_{x_1,x_1}+dis_{x_2,x_2}-2 \times dis_{x_1,x_2}$$$. This should make sense, and when you're done, you actually find that the point between the two $$$x$$$has been calculated exactly $$$n$$$. In fact, it is easy to prove that for $$$2 \times dis_{x_1,x_2}$$$the middle of the two $$$x$$$must not be counted because it is already looped, And then $$$dis_{x_1,x_1}+dis_{x_2,x_2}$$$actually understands that every point is on the edge between these two $$$x$$$, so repeat the $$$n$$$ calculation. So we've figured out the distance between any two points, and now we want to generate a tree, and in order to satisfy the distance that we figured out before, we need to minimize each edge, so we need to minimize the spanning tree.

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

Congratulations to tshirts winners! In a few weeks you will be contacted via private messages with instructions to receive your prize.

As usual, we used the following two scripts for generating random winners, seed is the score of the winner.

get_tshirts.py
randgen.cpp
List place Contest Rank Name
1 1764 1 QAQAutoMaton
2 1764 2 jiangly
3 1764 3 maroonrk
4 1764 4 fivedemands
5 1764 5 Vercingetorix
6 1764 6 ecnerwala
7 1764 7 gyh20
8 1764 8 GoRed
9 1764 9 p_b_p_b
10 1764 10 Ormlis
11 1764 11 duality
12 1764 12 Maksim1744
13 1764 13 neal
14 1764 14 353cerega
15 1764 15 PubabaOnO
16 1764 16 Egg_Tart_Forest
17 1764 17 dlalswp25
18 1764 18 hank55663
19 1764 19 Y25t
20 1764 20 ugly2333
21 1764 21 budalnik
22 1764 22 antontrygubO_o
23 1764 23 Sol1
24 1764 24 Endagorion
25 1764 25 ko_osaga
26 1764 26 turmax
27 1764 27 Kapt
28 1764 28 1092515503
29 1764 29 yuto1115
30 1764 30 liuhengxi
32 1764 32 arvindf232
43 1764 43 hitonanode
107 1764 107 hos.lyric
138 1764 138 jinmingli
140 1764 140 socpite
178 1764 178 Noam527
197 1764 197 physics0523
221 1764 221 US3RN4M3
243 1764 243 pavement
248 1764 248 ghoul932
364 1764 364 realcomplex
374 1764 374 yulik.daniel
388 1764 387 HollwoQ_Pelw
414 1764 414 Muelsyse
425 1764 425 SorasakiHina
426 1764 425 bcollet
434 1764 434 CRH380BL
464 1764 464 Andycipation
492 1764 492 lmqzzz
495 1764 495 kriepiekrollie
→ Reply