Блог пользователя Imakf

Автор Imakf, история, 2 года назад, По-английски

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

  • Проголосовать: нравится
  • +513
  • Проголосовать: не нравится

»
2 года назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

As a participant, I hope the problems are interesting!

»
2 года назад, # |
Rev. 2   Проголосовать: нравится +69 Проголосовать: не нравится

As a tester, Imakf 🤤🤤🤤

»
2 года назад, # |
  Проголосовать: нравится +41 Проголосовать: не нравится

omg 3 subtasks round

»
2 года назад, # |
  Проголосовать: нравится +90 Проголосовать: не нравится

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

»
2 года назад, # |
Rev. 2   Проголосовать: нравится +44 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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

»
2 года назад, # |
Rev. 2   Проголосовать: нравится +78 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится +61 Проголосовать: не нравится

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

orz Cocoly1990, Imakf and waaitg!

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

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

    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится +4 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Note unusual timing

»
2 года назад, # |
  Проголосовать: нравится +203 Проголосовать: не нравится

As a writer,i want contribution.

»
2 года назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

omg emoji round

»
2 года назад, # |
Rev. 3   Проголосовать: нравится +8 Проголосовать: не нравится

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.

»
2 года назад, # |
  Проголосовать: нравится +45 Проголосовать: не нравится

As a tester, Orz Cocoly1990.

»
2 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

»
2 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Orz Imakf <《^,^》>

»
2 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

All the problems are very interesting!

orz Cocoly1990, Imakf and waaitg!

»
2 года назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Consecutive rounds! :O

»
2 года назад, # |
  Проголосовать: нравится +49 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится +26 Проголосовать: не нравится

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!

»
2 года назад, # |
  Проголосовать: нравится +31 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Note :: UNUSUAL TIME OF CONTEST

»
2 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Brillant use of emojis

»
2 года назад, # |
  Проголосовать: нравится +139 Проголосовать: не нравится

»
2 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

omg emoji round

»
2 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Oops

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

I want another ConstructForces like 836 div.

»
2 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Thank you coddeforces

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

hoping to solve upto D!! :)

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

hopefully no choking this round

»
2 года назад, # |
Rev. 2   Проголосовать: нравится -12 Проголосовать: не нравится

Celtic /se

»
2 года назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

Chinese round! /tyt

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
2 года назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится +22 Проголосовать: не нравится

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Emojforces ☺️

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

nice emoji

»
2 года назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Everyone for good luck!

»
2 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

omg Imakf round

»
2 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится
»
2 года назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

don't expect much you will do better.

»
2 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

G1 easier than F, E .. intersting :)

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

So G has 3 subtasks? XD

»
2 года назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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

»
2 года назад, # |
Rev. 4   Проголосовать: нравится +7 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится +41 Проголосовать: не нравится

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

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +22 Проголосовать: не нравится

    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.

    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 года назад, # |
Rev. 2   Проголосовать: нравится -28 Проголосовать: не нравится

:|

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Contest is not over yet. Delete it.

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

»
2 года назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

Why is div1+2 D so hard again?

»
2 года назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится

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.

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What was the logic in number B?

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
2 года назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

How could C be approached?

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    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

  • »
    »
    2 года назад, # ^ |
    Rev. 3   Проголосовать: нравится +7 Проголосовать: не нравится
    Hint
    Solution
»
2 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Scariest problem D

»
2 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

How to solve D?

  • »
    »
    2 года назад, # ^ |
    Rev. 4   Проголосовать: нравится +14 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

how to solve B?

»
2 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

What a tough contest :(((

»
2 года назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

C was quite tough to spot the right answer.

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    I do agree

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I guessed the solution but I can't prove it

»
2 года назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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.

    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

D actually ended up being fun lol

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 года назад, # |
Rev. 3   Проголосовать: нравится +146 Проголосовать: не нравится

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!

  • »
    »
    2 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    2 года назад, # ^ |
    Rev. 3   Проголосовать: нравится +2 Проголосовать: не нравится

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

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    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.

  • »
    »
    2 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

    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)

»
2 года назад, # |
  Проголосовать: нравится -9 Проголосовать: не нравится

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

»
2 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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.

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
2 года назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 года назад, # |
Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится +27 Проголосовать: не нравится

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.

»
2 года назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

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

»
2 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

finally a round i enjoyed :)...

»
2 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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!

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

Problem D really pegged me.

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

UnRated?

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
23 месяца назад, # |
  Проголосовать: нравится +32 Проголосовать: не нравится

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