shishyando's blog

Codeforces Global Round 16
By shishyando, 3 years ago, In English

Hello, Codeforces!

On 12.09.2021 17:35 (Московское время) we will host Codeforces Global Round 16.

It is the fourth round of a 2021 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 2021:

  • 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 2021 supported the global rounds initiative!

The problems were written and prepared by shishyando and Artyom123.

We would like to thank these people:

You will have 2.5 hours to solve 8 problems. As always, we highly recommend reading all problems. Moreover, we really hope you upsolve the problems after the round, there are some interesting things to find out!

One of these problems is interactive, please see the guide of interactive problems if you are not familiar with it.

Score Distribution:

500 — 750 — 1000 — (750 + 1000) — 2000 — 2500 — 3000 — 3750

Editorial:

The editorial

Winners

System testing finished, congrats to the winners!

  1. Radewoosh
  2. tourist
  3. QAQAutoMaton
  4. jiangly
  5. ksun48
  6. Alice_foo_foo
  7. He_Ren
  8. Benq
  9. tatyam
  10. hitonanode
Announcement of Codeforces Global Round 16
  • Vote: I like it
  • +692
  • Vote: I do not like it

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

As a coauthor I need contribution

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

As a devoted tester who tried to make the round better, I wholeheartedly invite you to the contest. Will be fun, I promise!

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

As a soon to be Candidate Master I need your love and support.

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

Looks like there won't be rickrolling here, thank god

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

This round is going to be awesome. How do I know? Well, shishyando and Artyom123 made a round 6 months ago which unfortunately went unrated. That was one of the best contests I participated in on Codeforces. It had every single quality one could hope for. I even wrote about it after the contest https://codeforces.me/blog/entry/88750. If you also enjoy similar problems, you will love this one.

All the best to every participant. And thanks a lot to the authors!

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

As a participant, pls give me upvotes, its at -10 now ;-; wishing y'all high deltas!

In case you're not aware of it, below are some backup links of codeforces in case the main site goes down during the contest!

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

    Oops, pressed downvote by accident

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

    don't try to earn contribution begging for upvotes unless you're a tester, as you can see people don't like it just a useful advice)

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

    Will the universe balance my negative contribution with positive rating deltas? ;-;

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

As a problem researcher, I hope my testing is worth some contribution and a t-shirt. And of course, what I desire most is, your memorable ​experience in the round!

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

Again, where are my pants

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

Where memes??????????

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

As a tester, read all problems (and then solve everything).

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

Hope I can become GrandMaster after this Round.

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

Ngl , the meme announcement>>the actual one ;)

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

I hope I can change the color of my name in this round

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

I wanna get high rating!

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

As a tester, I found this round to be one of the most interesting rounds I've ever tested. Good luck and have fun!

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

Why is the contest always at Sunday but not Saturday？

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

My first round in around 40 days. Waiting for negative delta :'(

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

I have a question why can't there always be a contest in one the two weekend days ? in other days I wake up early and I'm the type of a guy that if he wakes up early he spends the day like a zombie and when i come back from work I'm a exhausted and would do like shit in contests (I know I won't do that better if not but I'm doing worst than when I'm not tired)

of course let's not only put contests in weekends but maybe if there's a contest in friday shift it to saturday so it depends on the authors time ? or others don't agree with me with making a contest in weekends for some reason

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

    What's wrong in having a contest in weekends like do you prefer to come back from work/college/school and participate or wake up when you want drink a cup of tea do some yoga and then participate in the contest wouldn't you perform better in that case?

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

      For me, It is on Sunday night. And So, It's was good for me. You know, authors can't make everyone happy with time because of timezones. and different preferences. Try Atcoder maybe their contest timings suits you.

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

    we dont care about you

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

      it's a universal holiday so that would fit others time I'm not talking about my own time noob

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

        noob boob

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

        Bro, majority of us ( the peoples who share similar time to that of IST) are night owls, therefore we prefer this time... For me this is the best time for the contests to be commenced, If it would have had been on some different time, I don't know wether I would have been able to appear for it in the first place.

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

          I didn't mean what hour the contest is but which day if it's Saturday or Sunday which most people don't have work/college/school they would have better focus because they're not tired from what their work

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

            I can't say anything regarding this... On the days of contest I try to keep myself calm and try my best to keep my brain empty all day so that I can do best during the contest... I don't know whether it works or not but atleast I feel such... also, It is organised globally so It can't be on Sunday for everyone. Like it's Monday now in India but Sunday in America... so If you look closely, there are peoples who are giving the contests in adverse conditions, like at some places, maybe they need to wakeup at 3:30 am to give it... thinking about it, we are in much better position regarding the timing and days of the contests.

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

I hope to return expert after this round . Good luck to all of us.

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

why could this fucking stupid blue name so frequently hold contests?

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

Is this round going to be rated for everyone?

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

Will this be rated for div3?

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

Why all the big contests are in sunday. I am the only one who is watching Premier League? :))

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

Who can tell me the range of rating in this game? I didn't see anything about rating in the game statement.

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

I wished to participate in my first Global round but unfortunately, today is Navi vs Vitality finals : /. https://www.hltv.org/matches/2350388/vitality-vs-natus-vincere-esl-pro-league-season-14

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

This is my channel on youtube for problem solving that can help you :

https://www.youtube.com/channel/UCwlL7AyWLjUlrF6SHHB_nIA

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

    that can help in cheating

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

      No I don't upload any videos while contest

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

        what about this?

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

          Do you see any videos uploaded while contest Mr Conan ??

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

            but what is the purpose of making such a vid on the contest? you should solve problems in that time

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

hope don't see "in queue" !

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

Amazing round well balanced quests.

I personally felt first 4 quests easy.

And so did most of the others according to number of submissions.

over all well balanced quests. And indeed this round is for everyone

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

Bruh speedforces

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

who is sus

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

This (div1 + div2) = div3

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

congrats to radewoosh for getting first! but tourist's rating might decrease again :/

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

Actually, it was a good round. :)

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

Greedyforces

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

Is this approach correct for E

I got a silly runtime error in last minute.

https://ideone.com/ngaPsL

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

sample tests were quite good today :) ... lovely round authors

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

It took me at least 1 hour to understand what exactly D2 is meaning for.

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

How to solve F?

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

    Best end points b/w each $$$a_{i}, a_{i + 1}$$$ (till where $$$a_i$$$ goes right, and till where $$$a_{i + 1}$$$ goes left) is independent of any other end points, it depends only on whether points $$$a_{i}$$$ and $$$a_{i + 1}$$$ each go left and then right or vice versa.

    So we can just use an $$$n \times 2$$$ dp for this state (position, left then right / right then left), and just use two pointer to calculate the optimal split point between $$$a_{i}, a_{i + 1}$$$ in $$$O(n + m logm)$$$ time. Removing ranges that already cover some $$$a_i$$$ makes the implementation easier since every range is now strictly between some $$$a_i$$$ and $$$a_{i + 1}$$$. (consider $$$a_0 = -INF$$$ and $$$a_{n + 1} = INF$$$).

    Detailed explanation of 'use two pointer'
    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can some explain how to do the C problem in brief . I was getting WA on pretest 2 :(

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

    Its always worth it to either leave a element alone or merge it with an adjacent one. Elements with mex 2 will always be alone and 0 and 1 should always be paired if they are adjacent. In that case, you just need to iterate through the indices and see if the previous one is the opposite of the current one and if it wasnt paired before to merge them.

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

    some observations are:

    1. column [1, 0] and [0, 1] are the best, and they shouldn't be combined with any other columns (it won't increase the MEX sum)
    2. column [0, 0] is okay itself, but combined with [1, 1] is better.
    3. column [1, 1] itself yields no MEX points, but with a [0, 0] they can contribute 2

    so you can greedily scan the columns from left to right, if you encounter [1, 0] or [0, 1], just add 2 to your answer, if you encounter a [1, 1] ([0, 0], respectively) column, first examine whether the next column is [0, 0] ([1, 1], respectively)

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

Is it just me or the questions were actually simple today. I solved 5 of them for the first time.

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

How to solve E?

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

    Think about the composition of your tree into buds. The optimal solution is always taking all of the buds and putting them one on top of the other. Each time you do this, the number of leaves in total decreases by one. That way you just need to count the total ammount of leaves — the total ammount of buds+1.

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

      In this case, the answer is 2, right? Sorry if I misunderstood, but doesn't your approach say it is 1? 0.8

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

        It should be (total amount of leaves (including leaves in buds) after removing all buds) — (number of buds).

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

      F

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

Randomised strategy in G:

Answer is minimum over

  • Sum of three edges adjacent to a vertex
  • Sum of two edges that are not adjacent

The first is easy to compute. For the second, randomly pick 0 or 1 for every vertex, and take the sum of min-cost edge between two 0-nodes and the min-cost edge between two 1-nodes. I did offline dynamic connectivity to do this for every time step.

Complexity is like $$$\mathcal{O}(100\ n \log n)$$$ for $$$1 - \left(\frac{7}{8}\right)^{100} \approx 1 - 10^{6}$$$ chance to answer a query correctly. Barely fits TL. Somehow I also passed pretests with 50 iterations, but resubmitted 100 because I was too scared.

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

    That sounds cool. My approach to find the two disjoint edges with smallest weight was:

    Let $$$(u, v)$$$ be the edge with smallest weight. Take the next two smallest edges connected to $$$u$$$ and the next two connected to $$$v$$$. Also take the smallest edge $$$(x, y)$$$ that is disjoint from $$$(u, v)$$$. Somehow I convinced myself that the answer will be a pair of these $$$6$$$ edges. The only thing remaining is to find $$$(u, v)$$$ and $$$(x, y)$$$ for each query. For that I threw everything in a horribly messy segment tree that got TLE, but I'm guessing there is a better way.

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

    I don't understand, why do you need dynamic connectivity?

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

      I guess you don't need it, but I don't see how to do this without the $$$\log n$$$ factor and guess it's faster than going through in order with sets.

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

        You can solve it with DSU with union by size + path compression to make that logn go down to ackerman inverse (and easier to code).

        Basically instead of a set that gives you lower bound, use the DSU to merge the ranges and give you the lower bound.

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

          I don't quite understand, how do you handle edge removals with that?

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

            Before anything, have the edges ordered.

            Then pass through edges in order. If the edge is good, then take the untaken positions in the range [l, r] that are alive and make them have the cost of this edge. The dsu is over the time of the queries, if we want to know the next untaken position after l then it's just the rightmost position in the component of l. Use up that position and unite it with the next position while it's <= r.

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

    Resubmit solution with $$$100$$$ iterations was the right decision. Probability of accept is $$$(1 - (\frac{7}{8})^{iteration})^{test\underline{ }count}$$$. Problem have more than $$$750$$$ test. With $$$50$$$ iterations probability of accept is about $$$0.39$$$, with $$$100$$$ iterations is $$$0.998$$$.

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

      I don't understand one thing: isn't that the probability for 1 individual query? How does it pass, given that each test gives like 10^5 queries lol

      I think that means that the tests don't have much variety of pairs of edges pairing up to give the min answer but idk

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

      I think it's worse than that, and even with 100 I was lucky to pass.

      If you have a case where initially there are some random 4 super expensive edges, then in query $$$i$$$ you add an edge between $$$2i$$$ and $$$2i + 1$$$ of cost $$$Q - i$$$, the optimal pair of disjoint edges to take changes after every operation, and for every one of those pairs you need some colouring where they are both monochromatic and different colours.

      The events that you get correct answers aren't independent, but every second one is, so probability to succeed is at most $$$\left(1 - \left(\frac{7}{8}\right)^{iterations}\right)^{queries / 2}$$$ which for $$$Q = 10^5$$$ is already just 0.92...

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

A,B,C,D1 all felt like Division 3 level of difficult increments.

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

someone help me with A question ,this was my first contest

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

    find the position of the median "pos = ceil(n/2.0)". before this position, consider all elements to be zero. So we have to distribute the sum s among the leftover places "left = n-pos+1". The answer simply will be "sum/pos". Since, if the sum can not be divided equally among the leftover positions, the remainder will be added to the positions greater than pos. As we are finding the median the array should be sorted non decreasingly at all times.

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

    Inspired by the n=7, s=17 test case (optimal distribution: 0, 0, 1, 4, 4, 4, 4), My strategy is to put the largest possible value M over $$$\frac{n}{2}$$$ times. (to reach the median place)

    more formally, let's consider 2 cases:

    1. n is odd, which means we should put M $$$\frac{n+1}{2}$$$ times
    2. n is even, which (by the definition of median in this problem) means we should put M $$$\frac{n}2+1$$$ times

    so the largest possible median value M can be derived:

    1. $$$M\leq \frac{2s}{n+1}$$$, if n is odd
    2. $$$M\leq \frac{2s}{n+2}$$$, if n is even
    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone tell why my this solution of C give tle https://codeforces.me/contest/1566/submission/128642893 ?

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

    probably big overhead of recursion + overcomplicated + O(n*8) instead of O(n) + maybe cache misses

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

      n = 10^5 na so i don't think recursion stack can be big enough to give tle.

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

Can we just appreciate this?
werew

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

    Frankly, it looks like div3 gradient and this is not particularly good. I don't complain though

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

      -100 rating prediction here just because I overcomplicated myself on D2 and couldn't debug it. Amazing round.

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

I guess pretest for D2 are very weak. My n*m*log(m) works in just 46ms. Expecting a lot of FST's there

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

    Why would n*m*log(m) not work?

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

      n*m*log(n) definitely would. i mean, my friend uses something different and got 600ms and he will probably FST. I pointed on n*m*log(m) time just to show that samples are not that good, because it should work longer (but still pass) at max test, i think.

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

        Why would it? $$$O(n * m^2)$$$ is just $$$300 \times 10^5$$$ = $$$3 \times 10^7$$$ operations which should easily pass consider its not even something heavy like modulo. My $$$O(n * m^2)$$$ soln also runs in 46ms on pretests.

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

        Ok, i was wrong, there is not much failed solution, but my friend got TLE, so i wasn't that wrong

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

    but n*m*log(m) is like O(10^6), it should totally pass...

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

    According to me O(n*m*m) will also work on an average. Don't know whether I will fst or not.

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

    My O(n*m²) code works in just 62 ms: 128625308

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

    Please don't spread fud, you will scare the noobs :(

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

I think score for D2 should be at least 1250

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

    But if score for D2 was 1250,the total score of D would be equal to score of E, but E is much harder than D.

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

Is pretest too weak in D1 and D2 ? O(m^2) passed on D1 ?

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

    Its strange that youre the second person saying that pretests were weak because a solution that should pass is passing

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

    $$$n, m \leq 300$$$ in a given test. $$$O(n \times m ^ 2)$$$ is equivalent to $$$O((n \cdot m) \times m)$$$, we know the first term is bounded by $$$10^5$$$ and the second is bounded by $$$300$$$, the worst possible is $$$3 \times 10^7$$$.

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

    $$$t <= 100$$$

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

Online judge is slow again today !!

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

Gread round solve 4 problems for the first tme ever

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

When is the rating coming out??

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

    Some time after the problems are tested. Unfortunately there were a lot of submissions this round so I think this might be slowing down the process.

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

The first 5 questions of this contest (D1 & D2 separated) should be fine and easy to implement for intermediate coders.

The sixth question E (tree problem) is a little complex since not all cases of bud-leave trees are shown in the test case, but it should also be fine (check the editorial for solution).

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

Codeforces server right now

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

    I'm at least happy it only went full potato mode now and not during contest :P

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

    Does that actually work?

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

    Meanwhile, G having 630+ (and counting) tests..

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

      740+ and counting...is this the highest number of tests any problem on cf ever had :thonk: XD

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

Problem G systests o_0 image please load

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

A nice contest,i feel very good.

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

G has 753 tests but still I uphacked my solution...

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

    And our beloved Systests have gone somehow. Take a look at the number of tests of this submission 128675942. Maybe something went wrong due to exceptionally large datasets? isaf27

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

      I think that's why system testing was so slow

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

      We added 750 more random tests just to hack some random wrong solutions (aka while not TL) for that problem. On polygon, such solutions failed with good probability, but it doesn't help on Codeforces (maybe faster testing machines).

      To make it possible to upsolve the problem without 10 mins waiting we decided to remove these added tests.

      Maybe system testing was slow because of this, but the size of the package for that problem was normal (25 Mb).

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

        I don't think that adding tests during the contest after reading competitors' solutions and aiming at them is nice (and should be announced).

        Also, mine and mango_lassi's solutions are provable (OK, mine is with greater TL), while in H I've implemented a poor heuristic, which maybe can be fairly hacked. I'm not sure that the priorities were good.

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

          In H we had pretests = tests and of course, we doesn't change tests, because they won't be random in this case.

          My opinion about changing tests: it is ok because it is the participant's problem, that their solution is incorrect. For example, we add all successful hacks to tests before system testing. Also, it is fairer to the participants who solved the problem correctly. In Codeforces with pretests format, you should understand that your solution may fail if it is incorrect (but passed pretests).

          After that case, I understood that there is a big minus of this: some good randomized solutions like yours (that works with probability 10^(-3) for example) may fail after such "stress testing". I don't want to do such things in the future (with many tests) and will add tests only in case of single counterexamples to the solution.

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

            I strongly don't agree. After years of experience I can tell that "probably tests are weak and something not exactly correct will pass" is a good assumption and a part of strategy (at least on CodeForces) which worked many times.

            Of course, the best thing to do is to make this assumption wrong and make everyone forget about it, but adding tests during the contest is not a good way.

            In H I totally forgot that the statement says that the tests are random, sorry for that.

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

            If you are a contest setter/admin, please don't add tests from reading submissions in any situation. This contradicts the objective nature of programming contests. It also encourages people to obfuscate their code so that a coordinator won't be able to understand it and produce a countercase.

            If you have ideas for tests to break bad random solutions, you should add them before the contest. Besides hacks (which are built into the contest rules) the tests should be finalized, and if there is an extreme need to fix the cases it should not be based on things realized during the contest.

            It is a bit sad that this needs to be stated, especially to someone who is supposed to be overseeing other problemsetters.

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

              IIRC obfuscating solutions are against the Codeforces rules.

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

              Besides hacks (which are built into the contest rules)

              And which are limited to people in your room, making it practically impossible to gang up on someone.

              (And are almost non-existent recently, but that's another topic.)

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

            This is so wrong.

            You're seriously damaging competitive integrity by interfering fair competition :(

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

            it is ok because it is the participant's problem, that their solution is incorrect

            That's fucking stupid. I'll say it again to emphasise how fucking stupid it is: that reasoning is fucking stupid. Sorry, not sorry, there's no other way to put it because it's a topic that's been discussed to death.

            You can add tests that break one solution but not another. For one contestant, you thus say "incorrect solution? your fault", while for another, you say "it may be incorrect but it passed tests so it's fine xD :P". That removes any trust in impartiality of judging — why should we trust that you're not focusing on someone in particular? If you make sure e.g. tourist's wrong solutions fail no matter what, then it's not fair to tourist because he's forced to play under different rules than everyone else. It's called fairness.

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

          Both solutions hacked :|

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

        Adding test data in the middle of a 2.5h contest is not OK.

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

In the sample 3 of D2, how the minimum answer is 4. Shouldn't it be 2 if we arrange people in this manner — 1 1 3 1 4 4 1 1 2

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

    persons with lower eye sight should be given seats with lower numbers but in your sequence 3,4 is bigger than 1,2 one should consider the total sequence not for each sequence

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

    As stated in the problem statement:

    • for any two people i, j such that ai<aj it should be satisfied that si<sj.

    Therefore, the people can only be arrange in an increasing order.

    (similar to what SuryaManikanta said)

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

We are sorry for a slow system testing.

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

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

To easy D1 and C for global round, that's why it was fastforces, not code. But still, thank you for this round

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

I screwed up because under the influence of problem B I interpreted C as "each column value is in exactly one bi-table". lol

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

deleted

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

Since the official announcement isn't here yet and I'm an impatient person, I've decided to find out who won the t-shirts for myself.

As always, you can do the following steps to get the t-shirts winners of Global Rounds:

1) Download testlib.h from Mike's github repo.

2) Use it to compile randgen.cpp :

randgen.cpp

3) Run the Python script winners.py, replacing the number in contest = [] with the ID of the contest in question (in this case, 1566):

winners.py

Both of these scripts are taken from the official winners announcements in previous Global Rounds, but if you have any doubts you can always check these results against the official ones later.

With that out of the way, congratulations to the (unofficial) t-shirt winners:

List place Contest Rank Name
1 1566 1 Radewoosh
2 1566 2 tourist
3 1566 3 QAQAutoMaton
4 1566 4 jiangly
5 1566 5 ksun48
6 1566 6 Alice_foo_foo
7 1566 7 He_Ren
8 1566 8 Benq
9 1566 9 tatyam
10 1566 10 hitonanode
11 1566 11 hanbyeol_
12 1566 12 kotatsugame
13 1566 13 fivedemands
14 1566 14 sansen
15 1566 15 blackbori
16 1566 16 Ormlis
17 1566 17 maroonrk
18 1566 18 snuke
19 1566 19 duality
20 1566 20 mango_lassi
21 1566 21 aid
22 1566 22 Rewinding
23 1566 23 Argentina
24 1566 24 voidmax
25 1566 25 nick452
26 1566 26 cnoi
27 1566 27 dorijanlendvaj
28 1566 28 huhaoo
29 1566 29 Geothermal
30 1566 30 Maksim1744
40 1566 40 m_99
69 1566 69 alireza_kaviani
168 1566 168 Kite_kuma
195 1566 195 PubabaOnO
234 1566 234 Plasmatic
256 1566 256 Seyaua
291 1566 291 foolishgoat
315 1566 315 tobias.glimmerfors
335 1566 335 usuyus
345 1566 345 nok0
348 1566 347 _dg_
367 1566 366 ButterflyDew
383 1566 383 dimdum
405 1566 404 fishy15
420 1566 420 JeffreyLC
434 1566 434 faustaadp
447 1566 447 wh2005
448 1566 448 Jarif_Rahman
451 1566 451 suyiheng
483 1566 481 Aelhurn
→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Can somebody help me in finding a smaller test case in which this code is failing. This is the code for Problem D2. Thanks in advance:)

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

Congratulations to snuke for returning to LGM

(For not disturbing him I didn't ping his name)

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

Here is some feedback on the contest (a bit late).

  1. Median Maximization. Nice, clean, not trivial. A very good cakewalk problem.
  2. MIN-MEX Cut. An easy problem which still requires observations with a natural statement. Easy to implement. Very good.
  3. MAX-MEX Cut. The statement is complicated and not interesting, the solution is standard. This felt too easy for its position.
  4. Seating arrangements. Nice problem, I think it was a good idea to split it into two subtasks. The hard subtask required me to stop and think and I enjoyed implementing it. I like that the implementation is somewhat demanding (for the problem position). It was a good idea to use the constraint $$$n\le 300$$$ instead of $$$n\le 2000$$$ which would have been just a pain without adding anything to the problem.
  5. Buds Re-hanging. The sudden realization that one can create a "bud-decomposition" was satisfying. The solution is both very clean and unexpected. This one is the typical problem that, with 50% probability, I get stuck on (this time I was lucky).
  6. Points Movement. Standard but nice problem. I am pretty sure I had seen something similar, still it was cute and I enjoyed solving it. For experienced contestants, the vast majority of the necessary observations are standard.
  7. Four Vertices. The statement is not very interesting (the problem is not really about graphs), but the solution is nice and nonstandard. During the contest I was very close to solving this one, but I was too slow on the other problems and I didn't have enough time. I am quite disappointed that the tests were weak and you decided to add tests during the contest, please refrain from doing that in the future (for all the reasons explained here).

I had fun participating. It was a well-balanced contest with good problems. Apart from adding tests to problem G, everything else was well prepared. Thank you to the authors.

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

    Just a note about D2 — Looking at your submission (128615822) I think you overkilled the implementation. I felt it was much easier with regard to implementation than the average D level problem.

    Example of an easy way to implement it — 128621602.

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

I was trying to hack this submission 128743016 to problem G, but it returned "Unexpected verdict" (hack 756413). I wonder if there are any problems in the system, or my input is invalid?

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

Good contest GG :>

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

My solution 128624580 for problem 1566C has been skipped due to some similarities found with other codes. I feel that such similarities are bound to happen in such types of questions. I compared my code with the people who have written similar codes, and I can definitely see some similarities, but these similarities are bound to happen, due to the nature of the question, as the logic was pretty straightforward, and not much can be done in order to write very distinct code. It is quite normal to use ans variable to store the final answer, run for loop to traverse through the string and update the ans variable. I don't think this is a case of any kind of plagiarism as this is highly possible when thousands of people are submitting their solutions. I have always been honest while submitting my solutions, and I can say that this is not a case of plagiarism. I request the admin to kindly accept my solutions, as they have been honestly written by me.

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

Today I got a Notification that Your solution 128625122 for the problem 1566C significantly coincides with solutions milan0027/128625122, shalini_agrawal/128645632. I don't know why this happened. I didn't copy code from anywhere. I wrote my own solution. You may also compare the coding style of both the solution they are significantly different. If it's a system glitch kindly rectify it.

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

Today I got the notification that my solution 128612189 for the problem 1566C significantly coincides with solutions yashmittal19/128612189, ooz/128628009.Since ooz submitted solution around 25 minutes after me, so accusation is basically of sharing my solution. But I have not shared any of my code nor did I use sites like ideone. And even I don't know him. I don't know how to proof this but I have been giving contest regularly since last year and have never indulged in such malpractice. So I request admin to accept my solution.

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

I got notification that Your solution 128607740 for the problem 1566C significantly coincides with solutions Candidate_noob/128606285, deepanshu55/128607740. This is clearly a coincidence. I don't know how to prove that but problem logic was pretty straightforward and you can compare coding style with my previous submissions. I don't even know Candidate_noob.

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

This is another comment about having received a notification of plagiarism in problem 1566C. I did not share my solution or use online code editors.

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

Sir, I recently got a notification about plagiarism in Codeforces global round 16 and the problem is 1566C and the notification says I got the same answer as the other contested but I didn't copy and not even shared the solution and not even got it from any publicly available codes I wrote it on my own and I even want to say that problem is so simple that its solution may come same for some people in that large participants. Please think about this and that's all I want to say, So please accept my solution. I hope I will get my rating back soon.

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

I got the notification from Codeforces stating "Your solution 128612338 for the problem 1566C significantly coincides with solutions apoorv17/128612338, sajjad.h/128647926." I have neither shared my solution nor ran it on ideone. I don't know the other person in fact we belong to the different countries. Since the problem was trivial so it can easily happen that two person use a similar approach, I don't have any proof to prove this but such false plagiarism claims and reverting the ratings wastes all 2-3 hours of effort and demotivates for further round. I think Codeforces should improve their plagiarism checker algorithm so that in future no false positives occur.

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

This must be really difficult to decide when thousands of solutions are nearly similar luckily my code is always so shitty that no other code is similar to it :P

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

MikeMirzayanov can you please update problem ratings of the last Edu and this Global Round? It's been 10 days.

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

MikeMirzayanov Hey, in the last global round , my solution for problem 1566C was flagged for plagiarism. I want to clarify that by no means I have written some one else's solution, and it was my own code that I wrote honestly. I don't even know the people who wrote codes similar to mine. The code is so small that similarities with others is possible. Kindly accept my solutions, as I have always been honest while giving the contests, and if such false flags are given against me, it will discourage me from being honest in future. I can literally see many other codes similar to me that were not reported. Kindly look into this. Hoping for the best. I have been constantly trying to talk to you, but I have received no response yet. I won't accept this injustice against me, I would not let my original codes be skipped due to false theories. The people who were flagged with me have got their ratings back, but not me. How is this fair?

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

    Just to let everyone know that I know this guy personally and that the issue he is addressing is 100% authentic. He gives contests honestly and I too feel that his submissions should not have been skipped. I understand that plagiarism check is a hard job. You can never know with certainty if someone has copied or not from someone else. So this small margin of error can happen. But I believe that if someone is constantly trying to reach out for clarification, he/she must be heard. I hope that MikeMirzayanov looks into this soon.

    → Reply
»
3 years ago, # |
  Vote: I like it +72 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 1566 1 Radewoosh
2 1566 2 tourist
3 1566 3 QAQAutoMaton
4 1566 4 jiangly
5 1566 5 ksun48
6 1566 6 Alice_foo_foo
7 1566 7 He_Ren
8 1566 8 Benq
9 1566 9 tatyam
10 1566 10 hitonanode
11 1566 11 hanbyeol_
12 1566 12 kotatsugame
13 1566 13 fivedemands
14 1566 14 sansen
15 1566 15 blackbori
16 1566 16 Ormlis
17 1566 17 maroonrk
18 1566 18 snuke
19 1566 19 duality
20 1566 20 mango_lassi
21 1566 21 aid
22 1566 22 Rewinding
23 1566 23 Argentina
24 1566 24 voidmax
25 1566 25 nick452
26 1566 26 cnoi
27 1566 27 dorijanlendvaj
28 1566 28 huhaoo
29 1566 29 Geothermal
30 1566 30 Maksim1744
40 1566 40 m_99
69 1566 69 alireza_kaviani
168 1566 168 Kite_kuma
195 1566 195 PubabaOnO
234 1566 234 Plasmatic
256 1566 256 Seyaua
291 1566 291 foolishgoat
315 1566 315 tobias.glimmerfors
335 1566 335 usuyus
345 1566 345 nok0
348 1566 347 _dg_
367 1566 366 ButterflyDew
383 1566 383 dimdum
405 1566 404 fishy15
420 1566 420 JeffreyLC
434 1566 434 faustaadp
447 1566 447 wh2005
448 1566 448 Jarif_Rahman
451 1566 451 suyiheng
483 1566 481 Aelhurn
→ Reply