PurpleCrayon's blog

Codeforces Global Round 18
By PurpleCrayon, history, 3 years ago, In English

Happy Holidays!

On Dec/24/2021 17:35 (Moscow time) we will host Codeforces Global Round 18.

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

The presents 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 presents 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 the hard-working elves Monogon, BledDest, and PurpleCrayon.

We would like to thank the everyone who made this round possible:

You will have 2.5 hours to solve 8 problems.

UPD: The scoring distribution: 250 — 1000 — 1750 — 2250 — 2750 — 3000 — 3750 — 4000

UPD: Editorial is out!

Good luck, have fun, and stay off the naughty list!

Announcement of Codeforces Global Round 18
  • Vote: I like it
  • +609
  • Vote: I do not like it

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

As a non-tester, I am surprised the testers have not asked for contribution yet!

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

For many of us it will be the first time being called nice.

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

What was anton's role in this round?



😱

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

As a red-nosed reindeer (aka clown), I wish everyone Merry CF Xmas :)

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

This round will be good beacuse it has the best tester (TadijaSebez).

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

My 1-gon contest history

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

Hi PC

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

PurpleCrayon orz

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

The best Christmas present ever!!!

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

    Wait until you actually see it

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

Merry Chrismas.

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

PurpleCrayon orz!

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

This will gonna be my first contest prepared by Monogon

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

    I'm only one of the authors.

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

      I know that, but i mean to say that i'm will also get the taste of your problems int the contest this time.

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

        Or maybe you can't even get the taste of his problems xD

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

Good luck to everyone :)

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

PurpleCrayon OTZ !

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

23 hours ago: The score distribution will be announced shortly.

Looks like it meant shortly before the round, nice

Edit: It's there now and is interesting.

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

So excited to participate in this round, wish everyone good luck)

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

Do I participate in the contest, or go spend the Christmas Eve with my family? Help

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

Great! The score distribution announced very early!

16 hour before the contest.

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

XD

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

As a person on the naughty list, will it be rated for me?

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

250 —> 1000 —> 1750 ? 750 points gap? Kinda weird O_o.

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

Hope to solve D……Dont even think about E

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

    Hope I can solve A and B by only one submisson...... Don't even think about D! C is also a little bit(very)hard......

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

    2:29:47 solved D... What did I say!

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

So do this kind of contests have hacking battle? Is it rated?

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

seeing scoring distribution solving C can give a +ve dleta.

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

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

Want to look insightful and smart under contest announcement? Write something like "hmm, based on the scoring distribution [insert specific prediction that couldn't possibly follow from something as vague as a scoring distribution]".

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

250 act as a bait.....

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

I hope I will become again master before Christmas!

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

May Santa bring positive delta to you all !

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

Whenever I try to submit my answer it says I need to register for the contest, but I can't find where or how to do so, can anyone tell me what to do?

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

    Time's finished for today's contest.Try for next one before it starts

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

Code through X-Mas? I just wanna say Merry Christmas and have a good rank!

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

The color rating of some of the users has changed : for example 1-gon, PurpleCrayon and other persons. Am I only the one to see that ?

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

I'm too dumb to solve quality problems like these

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

Nice problems!!! I hope pretests are strong.

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

Bit-forces

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

Bitforces round btw Merry Christmas to everyone. .

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

Others: change the color by Christmas magic :)

Me: color changed by Codeforces Global Round 18 :(

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

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

Binaryforces

→ Reply
»
3 years ago, # |
  Vote: I like it +13 Vote: I do not like it
Meme(Hindi)
→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Why my E does not work?

First, red wants to minimize blues nodes. So first color K leafs since that maximizes the number of subtrees blue cannot color.

DFS for the size of the subtree of each vertex. Then DFS the tree sorted by uncovered subtree size, down to K leafs. This creates the max possible not-blue coverage. Blue gets all uncovered tree nodes. Then add more red chips "up" in the tree. This creates more red nodes. That should allways be possible, so if all leafs are covered, then R has k nodes and B has none.

Note that red gets allways exactly K vertex (if it wants it).

How to optimze w*(r-b)? If r-b is positive, R wants to maximize w, else R wants to minimize w. By minimizing b R has used some r vertex, so w=n-b-r Now if R adds another one vertex, w gets one smaller, but r-b one bigger. So this optimizes until r-b==w.

Else if r-b is negative R cannot do anything about it, since it cannot color more vertex than K, and has minimzed b anyway.

Can it be better to give blue some leaf to maximize w? -> No. If R gives away a vertex, it gets colored blue, so w does not change.

140497882

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

    i think the greedy by subtree sizes is wrong you have to sort by the longest path into the subtree which ends in a leaf

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

    and also you want to maximize w * (r — b) but in some cases the optimal solution is to color rp < r nodes so the w increase. and also the second player can color some less nodes than he can instead of just painting all of it

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

      Thanks, I think thats the point I am missing, blue could color less vertex to optimize w :/

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

Some user hande color not showing correctly. some specialist have legendary grand master color, and otherway around Chrismast intentional bug?

see - ichigo_kurosaki_1226 - Monogon

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

I LOVE PROBLEM D SO MUCH SUCH A BEAUTIFUL CONSTRUCTIVE PROOF!!!

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

    I DID NOT FOUND ANY WAY TO UNDERSTAND D SO I FIDDLED LIKE TWO HOURS WITH E!!!

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

      I don't think there is any problem with D's statement, solving it is another issue though. Apparently it is a boring standard problem according to some red participants. We must live in a different world :))

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

1.5 hours: giving contest

Remaining 1 hour: looking at standings and stalking people.

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

H: https://codeforces.net/blog/entry/54020?#comment-380689?

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

    It seems no one should try setting flow problems anymore because everything's been done already.

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

      Instead you can copy flow problems from good old days of topcoder so great problems can be relevant again

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

    Pity I saw at the last and Topcoder is very slow :(.

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

Here is some feedback:

A: Nice easy problem.

B: Very standard easy problem.

C: Wonderful not-so-easy problem. I was lucky and solved it fast, but I can see myself getting stuck on this one with high probability. The observation that "two moves" = "swap a 0 and a 1" was unexpected.

D: Boring standard problem. Using integer weights instead of $$$0$$$, $$$1$$$ is nonsensical. The only point that I see is that with $$$0$$$,$$$1$$$ weights the problem becomes even more standard, but using generic weights makes it only uglier, not less standard. Also the format of the output was unnecessarily complicated (why asking to print also the extreme points of the edges?).

E: The statement is nice, the solution also. I used the fact that $$$f(h) =$$$max number of blue nodes if there are at most h red nodes is a concave function, then standard methods (Minkowski sum and small-child trick) are sufficient to solve the problem. Given the amount of people who solved it, I might have overcomplicated it.

F: Nice clean dp problem.

Overall it was a nice contest, thanks to the authors.

p.s. While trying to hack someone (unsuccesfully) I found a cheater in my room.

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

    You can also do E with the Aliens trick, the code is very easy to write too.

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

      I solved it by cutting the tree up with a couple of DFS and height counters, what is small child trick and Aliens trick though?

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

    Does D involve HLD? Or something else?

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

    F is actually quite standard. If somebody is doing weird operation, and the underlying structure seems to be bipartite: Flip the odd cells. Anyway I also really liked the problemset as well.

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

      Can you please explain a bit more about this approach. Also are there any resources for why this approach of flipping odd cell works ?

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

        idk atcoder just abused this stuff several times

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

      Are you talking about C or F? I have not used the "flip odd cells" in neither of the two problems, but in the editorial of F they mention this idea, so maybe you wrote the wrong letter (and I don't see how to use the "flip odd cells" in C at all).

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

        I think he meant, for problem C: given a sequence of strings that result from doing the operation, flip the bits of the strings in odd positions.

        In sample 4 the original sequence is 100010111, 011101100, 110010011, 101101100; after flipping it's 100010111, 100010011, 110010011, 010010011

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

        I did meant problem F, sorry

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

    Finding $$$f(k)$$$ in problem E is a subtask of RMI 2021 — Paths.

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

    Could you elaborate more or direct me to some resources on why the Minkowski trick works? I think I've seen it before, but I've never fully understood it. Thanks!

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

      Consider two vectors $$$a, b$$$ with size $$$n, m$$$ and assume that both vectors are convex. Let $$$c$$$ be the vector of size $$$n+m-1$$$ given by

      $$$ c[k] = \max\limits_{i+j=k} a[i]+b[j].$$$

      This operation is very common when performing dp on subtrees.

      Let $$$\delta a[i] = a[i+1]-a[i]$$$ (notice that this is nondecreasing because $$$a$$$ is convex), and define analogously $$$\delta b$$$ and $$$\delta c$$$. Then one can prove that $$$\delta c$$$ (as a multiset) coincides with $$$\delta a\cup \delta b$$$ (proving it is not hard, try!), and moreover $$$c$$$ is convex (thus, $$$\delta c$$$ is nondecreasing). Hence, while performing a dp on subtrees it is often convenient to keep the discrete differences (in a multiset structure) instead of the values themselves.

      This procedure is known as Minkowski sum (at least to me) because it is very similar to the way one can compute the Minkowski sum of two convex polygons (recall that $$$A+B:=\{a+b: a\in A, b\in B\}$$$). Indeed, if $$$A$$$ and $$$B$$$ are two convex polygons, then the edges of $$$A+B$$$ are exactly the edges the $$$A$$$ and the edges of $$$B$$$ (suitably translated and sorted). Notice how the edges play the same role played by the discrete differences in the previous setting.

      p.s. Merry Christmas!

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

H is L1 isotonic regression in partial order. You can check SRM 720 discussion for two possible solution strategy (divide and conquer, LP duality). Both will work in O(mn log n).

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

    L1 isotonic regression in partial order

    Sometimes people are so smart I wonder if I'm even living in the same universe as theirs.

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

Great contest! I love problem A,B,C,D,E !!! I can't solve E but I completely love it!!

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

can anyone explain what is the solution for problem C i got stuck at c during whole contest.

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

    There is a nice observation for c : that after every two consecutive operations , u can swap two bits at different positions in the string

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

      I feel literally dumb now such a simple observation doesn't come to my mind.I made too much complicated observations and missed the basic one :(.

      But Thanks for your reply :).

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

Great contest! Merry Christmas to everyone.

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

Was E some hld-esque kind of construction where you want to break it up into maximal chains? If so, by what metric do you define heavy and light paths, since size and max depth didnt seem to work for me.

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

Codeforces Bitwise Round 18

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

Solved A, B and C after 44 mins

Then sitted for nearly 2 hrs unable to solve D.

Felt so tired at midnight.

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

In G, the reduction to general matching is easy, but it is extremely obnoxious to produce the string from the results. Why did you require outputting the string, not the maximum number of values??

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

    I don’t agree about your ‘extremely’. Whereas I agree with you that it does not have much sense, it didn't take more than 5 minutes for me

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

      Did you have $$$N$$$ vertices or $$$600$$$? Apparently $$$N$$$ vertices also passes, and then you easily get the construction. I was doing max general matching in a graph of 600 vertices, and to get to that point had to do some reductions, all of which you'd have to undo.

      If requiring to output the construction penalises you for not reducing to the smaller graph, the problem is even dumber than I thought.

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

When you're so clown you submit BFS to problem C :D

https://codeforces.net/contest/1615/submission/140484891

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

Pretty hard even for a LGM

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

that C was scary bruh

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

G is an easy exercise of max-matching with tedious implementation. I tried hard to reduce the number of vertices of the graph to 600, but it seems like $$$O(N)$$$ vertices is just OK.

H is a blatant application of the minimum cost circulation problem. I suppose it's not an intended solution, but you should have tried to kill such solutions.

I believe these two should not be the hardest tasks in GCR's.

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

    I think H is too classical and many participants found that it's a template isotonic regression task in contest.

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

    It seems ksun48's solution runs in subquadratic time, so maybe it could be more interesting problem if n, m were about $$$10^5$$$.

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

Hi guys! In tutorial sayd that B can be solved in range (1<=l<r<=1e9). But I think I solved this problem for this diapozone. Can anyone check my submission and tell me if this is indeed the case This is my submission](https://codeforces.net/contest/1615/submission/140492198) Thank you

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

Mary Christmas everyone. Now don't think about the problems you couldn't did, go and enjoy.

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

Santa is making too many LGMs this night.

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

The round's Problem C,D to me:
*A few shots*
Merry Christmas, you filthy animal, and a Happy New Year.
*Another shot*

I think that the solution to E is much more obvious than CD(
But personally I think the round is pretty okay.

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

G: I like the idea of this problem, reduction to general matching & to reduce # of vertices into 600. But the implementation amount of 2 solutions(O(600) vertices / O(N) vertices) is quite different, and my solution just use (practically fast) O(EV log V) matching with O(N) vertices. Personally I wish N <= 600 or print only the answer instead of array construction.

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

Waiting for SecondThread's screencast to see his reaction on losing red :p

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

    Afraid he will make a video telling everyone to downvote me for taking his red away

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

    Dude I'm so sad, not about losing red, but about the screencast being broken...

    I'm at my parent's house in Wisconsin, and I competed on my laptop instead of my usual computer, and OBS like ran out of memory or crashed or something and now there's just no recorded file.

    It would have been so fun to look back at and see all the things I did wrong too...

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

      Not sure if you already do this, but if you record to some formats (I think .mkv, not .mp4), it'll terminate recording gracefully, so you won't lose everything.

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

        Usually I do, but I was on my laptop that I almost never use, so the settings were different from what I usually do this time :(

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

      It is unfortunate that you had a bad contest. But hey on a flip side, it means you'll be very likely to have some big positive delta in the future contests :)

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

rated?

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

Unofficial T-shirt winners list

Important: The winners list has been updated due to changes in the scoreboard.

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

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

winners.py

Both of these scripts are taken from the official winners announcements in previous Global Rounds, but if you have any doubts on their legitimacy 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 1615 1 dengyaotriangle
2 1615 2 yosupo
3 1615 3 Rewinding
4 1615 4 QuietBeautifulThoughts
5 1615 5 inaFSTream
6 1615 6 maroonrk
7 1615 7 SSRS_
8 1615 8 tourist
9 1615 9 hos.lyric
10 1615 10 HIR180
11 1615 11 Radewoosh
12 1615 12 MyBotDear
13 1615 13 ksun48
14 1615 14 qazswedx2
15 1615 15 Benq
16 1615 16 Konijntje
17 1615 17 zh0ukangyang
18 1615 18 ugly2333
19 1615 19 Karry5307_AK_NOI2024
20 1615 20 risujiroh
21 1615 21 Froggay
22 1615 22 tatyam
23 1615 23 Alan233
24 1615 24 Rainbow_qwq
25 1615 25 wasa855
26 1615 26 TLE
27 1615 27 PetelgeuseRomaneeconti
28 1615 28 Golovanov399
29 1615 29 dorijanlendvaj
30 1615 30 Y25t
45 1615 45 lumibons
132 1615 132 kektus
161 1615 161 Shameimaru_Aya
199 1615 199 kizen
224 1615 224 Swadia
246 1615 246 ChenKaifeng
268 1615 268 RoundRoundUP
295 1615 295 retah
334 1615 334 Acranker
342 1615 342 Neal_lee
365 1615 365 Forza_Ferrari
381 1615 380 Bakry
392 1615 391 Xellos
400 1615 400 HeartBreakKid
401 1615 401 loan
403 1615 403 TsukikoTsutsukakushi
434 1615 434 popescuadrian
437 1615 435 SampsonYW
439 1615 439 FelixMP
489 1615 489 nanatoday
→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    It seems that there has been some changes in the ranklist and the winners are completely different from this

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

      Thanks for letting me know, I will update the list as soon as possible.

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

I wonder that when will the rating change, I can't wait!

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

why rating is not updated yet?

→ Reply
»
3 years ago, # |
  Vote: I like it -8 Vote: I do not like it
Hindi meme (English: where is my rating)
→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +34 Vote: I do not like it

In this contest, H is a template isotonic regression task. I copy the code in this editorial for another task which was posted on 2020-06-22. It could passed with changing the cost value and deleting the liner-base part. I think that it's OK according to the rule.

upd: KAAM also said that H is well-known and his/her code also marked the solution.

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

Hello, Can someone please help me in finding out why my solution TLEs for C? As far as I can tell the time complexity should be O(n) and I can't seem to figure out how to speed things up, or maybe I'm missing something? Thanks https://codeforces.net/contest/1615/submission/140578120

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

    'cause u use a bitset with 100000 elements. it results in a O(T * 100000) complexity. in worst case, it would be O(10000 * 100000) = O(1000000000).

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

Today I recieved a mail from codeforces, that my code is similar to few people from my latest contest solution submission (Global Round 18). PurpleCrayon please go through from my submission once 140506276 its just a simple if-else or nothing that's why I think my submission is similar to others. If you can do something it's great for me.

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

can I get the T-shirt?qwq

→ Reply
»
3 years ago, # |
  Vote: I like it +53 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 1615 1 dengyaotriangle
2 1615 2 yosupo
3 1615 3 Rewinding
4 1615 4 QuietBeautifulThoughts
5 1615 5 inaFSTream
6 1615 6 maroonrk
7 1615 7 SSRS_
8 1615 8 tourist
9 1615 9 hos.lyric
10 1615 10 HIR180
11 1615 11 Radewoosh
12 1615 12 MyBotDear
13 1615 13 ksun48
14 1615 14 qazswedx2
15 1615 15 Benq
16 1615 16 Konijntje
17 1615 17 zh0ukangyang
18 1615 18 ugly2333
19 1615 19 Karry5307_AK_NOI2024
20 1615 20 risujiroh
21 1615 21 Froggay
22 1615 22 tatyam
23 1615 23 Alan233
24 1615 24 Rainbow_qwq
25 1615 25 wasa855
26 1615 26 TLE
27 1615 27 PetelgeuseRomaneeconti
28 1615 28 Golovanov399
29 1615 29 dorijanlendvaj
30 1615 30 Y25t
45 1615 45 lumibons
132 1615 132 kektus
161 1615 161 Shameimaru_Aya
199 1615 199 kizen
224 1615 224 Swadia
246 1615 246 ChenKaifeng
268 1615 268 RoundRoundUP
295 1615 295 retah
334 1615 334 Acranker
342 1615 342 Neal_lee
365 1615 365 Forza_Ferrari
381 1615 380 Bakry
392 1615 391 Xellos
400 1615 400 HeartBreakKid
401 1615 401 loan
403 1615 403 TsukikoTsutsukakushi
434 1615 434 popescuadrian
437 1615 435 SampsonYW
439 1615 439 FelixMP
489 1615 489 nanatoday
→ Reply