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:
- The fabulous reindeer awoo, QBaraki, manish.17, Lyde, penguinhacker, Maksim1744, BucketPotato, magnus.hegdahl, ecnerwala, ItayOtto, ijxjdjd, actinium16, gamegame, kpw29, Um_nik, TadijaSebez, and AliShahali1382 for testing the round and providing valuable feedback to the problems!
- antontrygubO_o, the most famous reindeer of all!
- adedalic, for excellent coordination of the round!
- Saint Micholas Mirzayaclaus, MikeMirzayanov, for the amazing Codeforces and Polygon platforms!
- All the nice boys and girls who participate!
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!
As a non-tester, I am surprised the testers have not asked for contribution yet!
I'm also surprised our reindeer aren't begging for pixie dust yet
All hail the top reindeer OTZ
deleted
Chill, its not that deep
As a tester, I did like job and didn't even write this comment
As a non-tester you got too much contribution
Possibly true. Though the main reason for this comment is to point out that you have a good taste in profile pictures :)
Any one please discuss about the solution of C problem.
was excited when saw monogon on the authors list, but ...;(
For many of us it will be the first time being called nice.
What was anton's role in this round?
😱
Team spirit
Thank god
As a red-nosed reindeer (aka clown), I wish everyone Merry CF Xmas :)
You are a yellow-nosed reindeer
This round will be good beacuse it has the best tester (TadijaSebez).
My 1-gon contest history
Global Round 12
Round 712
Hoping to successfully pass system test on Problem A 🥵 this time
GL & HF
Hi PC
PurpleCrayon orz
orz
The best Christmas present ever!!!
Wait until you actually see it
Merry Chrismas.
PurpleCrayon orz!
This will gonna be my first contest prepared by Monogon
I'm only one of the authors.
I know that, but i mean to say that i'm will also get the taste of your problems int the contest this time.
Or maybe you can't even get the taste of his problems xD
Good luck to everyone :)
PurpleCrayon OTZ !
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.
So excited to participate in this round, wish everyone good luck)
Do I participate in the contest, or go spend the Christmas Eve with my family? Help
Tell your family to participate as well and upsolve as a group activity.
Great! The score distribution announced very early!
16 hour before the contest.
XD
As a person on the naughty list, will it be rated for me?
250 —> 1000 —> 1750 ? 750 points gap? Kinda weird O_o.
Hope to solve D……Dont even think about E
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......
2:29:47 solved D... What did I say!
So do this kind of contests have hacking battle? Is it rated?
seeing scoring distribution solving C can give a +ve dleta.
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]".
hmmm, based on the scoring distribution, you always feel the need to put your unsolicited opinion on virtually every blog post.
lmao
will take care next time.
250 act as a bait.....
I hope I will become again master before Christmas!
Ez Pz. Just wait for Santa.
Hey aryanc403, Looks like You won't need to wait for Santa after today to become RED.
Congratulations in advance GM.
Santa MikeMirzayanov please do some magic and change that +115/+120 to +122.
You can with Magic!
May Santa bring positive delta to you all !
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?
Time's finished for today's contest.Try for next one before it starts
Code through X-Mas? I just wanna say Merry Christmas and have a good rank!
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 ?
It must be a weird bug.
Too weird that it happens every year :)
I'm too dumb to solve quality problems like these
Nice problems!!! I hope pretests are strong.
Bit-forces
Bitforces round btw Merry Christmas to everyone. .
Others: change the color by Christmas magic :)
Me: color changed by Codeforces Global Round 18 :(
Binaryforces
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
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
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
Thanks, I think thats the point I am missing, blue could color less vertex to optimize w :/
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
Its a great bug bro i am loving it ;-)
https://mirror.codeforces.com/blog/entry/98262
I LOVE PROBLEM D SO MUCH SUCH A BEAUTIFUL CONSTRUCTIVE PROOF!!!
I DID NOT FOUND ANY WAY TO UNDERSTAND D SO I FIDDLED LIKE TWO HOURS WITH E!!!
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 :))
1.5 hours: giving contest
Remaining 1 hour: looking at standings and stalking people.
H: https://mirror.codeforces.com/blog/entry/54020?#comment-380689?
It seems no one should try setting flow problems anymore because everything's been done already.
Instead you can copy flow problems from good old days of topcoder so great problems can be relevant again
Pity I saw at the last and Topcoder is very slow :(.
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 nodesis 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.
You can also do E with the Aliens trick, the code is very easy to write too.
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?
Does D involve HLD? Or something else?
https://www.codechef.com/problems/PARITREE
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.
Can you please explain a bit more about this approach. Also are there any resources for why this approach of flipping odd cell works ?
idk atcoder just abused this stuff several times
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).
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
I did meant problem F, sorry
Finding $$$f(k)$$$ in problem E is a subtask of RMI 2021 — Paths.
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!
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
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!
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).
Sometimes people are so smart I wonder if I'm even living in the same universe as theirs.
Don't worry, Little_Bunny is 420x smarter than me
Great contest! I love problem A,B,C,D,E !!! I can't solve E but I completely love it!!
can anyone explain what is the solution for problem C i got stuck at c during whole contest.
There is a nice observation for c : that after every two consecutive operations , u can swap two bits at different positions in the string
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 :).
Great contest! Merry Christmas to everyone.
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.
Codeforces Bitwise Round 18
Solved A, B and C after 44 mins
Then sitted for nearly 2 hrs unable to solve D.
Felt so tired at midnight.
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??
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
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.
!(Pupil Friendly Contest)
Good thing that you're LGM then.
When you're so clown you submit BFS to problem C :D
https://mirror.codeforces.com/contest/1615/submission/140484891
I use the same way. But why is this true？
Pretty hard even for a LGM
Legendary Green Master
that C was scary bruh
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.
I think H is too classical and many participants found that it's a template isotonic regression task in contest.
It seems ksun48's solution runs in subquadratic time, so maybe it could be more interesting problem if n, m were about $$$10^5$$$.
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://mirror.codeforces.com/contest/1615/submission/140492198) Thank you
Mary Christmas everyone. Now don't think about the problems you couldn't did, go and enjoy.
Santa is making too many LGMs this night.
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.
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.
Waiting for SecondThread's screencast to see his reaction on losing red :p
Afraid he will make a video telling everyone to downvote me for taking his red away
Omg hi! It's the OG handle too!
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...
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.
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 :(
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 :)
rated?
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 :
#include "testlib.h" #include <iostream> using namespace std; int main(int argc, char *argv[]) { if (argc < 4) { cout << "Command line arguments are: seed length prefix nwinners" << endl; return 1; } int seed = atoi(argv[1]); int len = atoi(argv[2]); int prefix = atoi(argv[3]); int nwinners = atoi(argv[4]); rnd.setSeed(seed); set<int> winners; while ((int)winners.size() < nwinners) winners.insert(rnd.next(prefix + 1, len)); for (int i = 1; i <= prefix; ++i) winners.insert(i); for (auto winner: winners) cout << winner << " "; cout << endl; return 0; }3) Run the Python script winners.py, replacing the number in
contest = []with the ID of the contest in question (in this case,1615):import requests contests = [1615] # Replace this with the ID of the contest in question # [1, rank_start) get tshirts with no random # [rank_start, rand_end] get random tshirts rank_start = 31 rank_end = 500 n_random_tshirts = 20 def is_eligible(contest, party_name, rank, points, problems, last_submission_time): return (rank <= rank_end) def get_party_name(party): if 'teamName' in party: return party['teamName'] else: return party['members'][0]['handle'] class Party: def __init__(self, contest, name, rank, points, last_submission_time): self.contest = contest self.name = name self.rank = rank self.points = points self.last_submission_time = last_submission_time def __lt__(self, other): if self.contest != other.contest: return self.contest < other.contest if self.rank != other.rank: return self.rank < other.rank if self.last_submission_time != other.last_submission_time: return self.last_submission_time < other.last_submission_time if self.name != other.name: return self.name < other.name return False eligible = [] for contest in contests: rows_to_fetch = 20000 r = requests.get('https://mirror.codeforces.com/api/contest.standings?contestId=%d&from=1&count=%d&showUnofficial=false' % (contest, rows_to_fetch)) if r.status_code != 200 or r.json()['status'] != 'OK': print('Error: failed to fetch results of contest %d.' % contest) exit() results = r.json()['result']['rows'] if len(results) == rows_to_fetch: print('Error: results are too long in contest %d, increase limit.' % contest) exit() for row in results: party_name = get_party_name(row['party']) rank = row['rank'] points = row['points'] problems = 0 last_submission_time = 0 for problem in row['problemResults']: if problem['points'] > 0: problems += 1 last_submission_time = max(last_submission_time, problem['bestSubmissionTimeSeconds']) if is_eligible(contest, party_name, rank, points, problems, last_submission_time): eligible.append(Party(contest, party_name, rank, points, last_submission_time)) eligible = sorted(eligible) for i in range(1, len(eligible)): if not eligible[i - 1] < eligible[i]: print('Error: unable to sort eligible at positions {} {}.'.format(i, i, i + 1)) exit() print('Eligible for tshirts are:') for idx, party in enumerate(eligible): print('{} {} {} {} {}'.format(idx + 1, party.contest, party.rank, party.name, party.last_submission_time)) seed = eligible[0].points print('Total %d eligible, seed is %d.' % (len(eligible), seed)) import subprocess testlib_rand = subprocess.run(['./randgen', str(seed), str(len(eligible)), str(rank_start - 1), str(n_random_tshirts)], stdout=subprocess.PIPE) winners = list(map(int, testlib_rand.stdout.split())) print() print('Winners are:') for place in winners: print('{} {} {} {}'.format(place, eligible[place - 1].contest, eligible[place - 1].rank, eligible[place - 1].name)) print() print('| List place | Contest | Rank | Name |') print('|--|--|--|--|') for place in winners: print('| {} | {} | {} | [user:{}] |'.format(place, eligible[place - 1].contest, eligible[place - 1].rank, eligible[place - 1].name))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:
It seems that there has been some changes in the ranklist and the winners are completely different from this
Thanks for letting me know, I will update the list as soon as possible.
I wonder that when will the rating change, I can't wait!
Me too! You are not the only one.
why rating is not updated yet?
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.
@MikeMirzayanov
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://mirror.codeforces.com/contest/1615/submission/140578120
'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).
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.
can I get the T-shirt?qwq
I really want get one>_<
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.