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

Автор shishyando, 3 года назад, По-английски

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:

5007501000(750 + 1000)2000250030003750

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
  • Проголосовать: нравится
  • +692
  • Проголосовать: не нравится

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

As a coauthor I need contribution

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

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

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

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

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

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

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

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.net/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!

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

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
»
3 года назад, # |
  Проголосовать: нравится +79 Проголосовать: не нравится

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!

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

Again, where are my pants

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

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

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

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

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

Hope I can become GrandMaster after this Round.

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

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

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

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

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

I wanna get high rating!

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

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

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

Why is the contest always at Sunday but not Saturday?

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

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

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

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

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

    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?

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

      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.

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

    we dont care about you

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

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

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

        noob boob

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

        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.

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

          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

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

            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.

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

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

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

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

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

Is this round going to be rated for everyone?

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

Will this be rated for div3?

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

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

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

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

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

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

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

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

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

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

hope don't see "in queue" !

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

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

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

Bruh speedforces

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

who is sus

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

This (div1 + div2) = div3

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

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

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

Actually, it was a good round. :)

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

Greedyforces

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

Is this approach correct for E

I got a silly runtime error in last minute.

https://ideone.com/ngaPsL

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

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

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

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

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

How to solve F?

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

    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'
»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

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

    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.

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

    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)

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

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

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

How to solve E?

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

    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.

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

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.

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

    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.

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

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

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

      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.

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

        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.

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

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

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

            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.

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

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

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

      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

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

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

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

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

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

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

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

    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.

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

    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
»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

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

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

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

Can we just appreciate this?
werew

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

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

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

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

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

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

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

I think score for D2 should be at least 1250

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

    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.

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

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

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

Online judge is slow again today !!

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

Gread round solve 4 problems for the first tme ever

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

When is the rating coming out??

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

    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.

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

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

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

Codeforces server right now

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

Problem G systests o_0 image please load

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

A nice contest,i feel very good.

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

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

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

    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

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

      I think that's why system testing was so slow

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

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

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

        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.

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

          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.

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

            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.

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

            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.

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

              IIRC obfuscating solutions are against the Codeforces rules.

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

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

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

            This is so wrong.

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

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

            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.

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

          Both solutions hacked :|

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

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

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

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

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

    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

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

    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)

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

We are sorry for a slow system testing.

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

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

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

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

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

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

deleted

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

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
»
3 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

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

Congratulations to snuke for returning to LGM

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

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

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.

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

    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.

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

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
»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Good contest GG :>

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

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.

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

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.

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

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.

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

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.

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

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.

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

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.

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

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.

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

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

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

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

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

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?

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

    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.

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

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