### 300iq's blog

By 300iq, 7 months ago, translation, ,

Hi!

At Apr/06/2019 14:35 (Moscow time) we will host Codeforces Global Round 2.

It is the second round of a new series of Codeforces Global Rounds supported by XTX Markets. The rounds are open for everybody, the rating will be updated 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 2019:

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

The problems of this round were developed by a team of authors: 300iq, cyand1317, Aleks5d, RDDCCD, KAN, gen.

Thanks KAN for his help in the round's coordination, and also isaf27, lewin, osaaateiasavtnl., Errichto, arsijo, _kun_ for testing the round!

Удачи!

Congratulations the winners!

2) tourist

3) Um_nik

5) Petr

Editorial.

Announcement of Codeforces Global Round 2
Announcement of Codeforces Global Round 2

• +341

 » 7 months ago, # |   +52 Friendly time to Chinese!
•  » » 7 months ago, # ^ |   0 Great!!!
•  » » 7 months ago, # ^ |   0 +1
•  » » 7 months ago, # ^ |   0 Yes, it would be better if future rounds will also hold at friendly time.
•  » » 7 months ago, # ^ |   +38 That means that, there will be people in some country that feel the contest time is bad.
•  » » 7 months ago, # ^ |   +2 I can sleep better today!! :)
 » 7 months ago, # |   +46 Hope that it won't happen again XD
•  » » 7 months ago, # ^ |   +76 ofc, will be worse...
•  » » 7 months ago, # ^ |   -36 Pretests for these rounds are extremely weak, that is why I won't participate in them anymore.
 » 7 months ago, # |   +19 it feels like we have been waiting for ages for this round
 » 7 months ago, # | ← Rev. 2 →   -28 It is nice initiative of doing such contests
 » 7 months ago, # |   +1 can you add the link Codeforces Global Round 1
•  » » 7 months ago, # ^ |   +11
 » 7 months ago, # |   +110 How many of you feel that Codeforces is decreasing the frequency of contests?
•  » » 7 months ago, # ^ |   +63 Maybe because the best problem developers are busy with ICPC WF. XD Hope the Contests will be more soon.
•  » » 7 months ago, # ^ | ← Rev. 2 →   0 I actually think these days the quality of the problems is increasing. So it's reasonable that there are less contests. (Well, didn't mean that other problems are poor in quality)
•  » » 7 months ago, # ^ |   +18 You can always participate virtually on some previous contest or on a one from the Gym.
•  » » 7 months ago, # ^ |   +34 If you compare with the situation 2 months ago, well — this is true. But what about the frequency that was 2 years ago? Currently, codeforces is the most active and popular platform for competitive programming (IMHO). I think that we should be grateful for this to Mike, KAN, and other contest makers and problem setters, for the opportunity to write contests at least once a week.
 » 7 months ago, # |   +124 Wait, what happens if someone gets in top 30 in all 6 rounds? That person gets 6 t-shirts? Wouldn't it be better to stop at some point (e.g. 2 or 3 t-shirts) and distribute the rest in some other way?
•  » » 7 months ago, # ^ |   +5 Mb, "The prizes for this round:" means, that not all rounds will be with the same prizes?
•  » » » 7 months ago, # ^ |   -8 That would be even more unfair and no, I'm pretty sure that's not the case. Check the initial announcement of the Global Rounds.
•  » » 7 months ago, # ^ |   +30 Maybe they are different T-shirts? I'm sure it's ok if such person gets all 6 different ones haha
•  » » 7 months ago, # ^ |   +4 The more the better, I can give it to my mom, my girlfriend , my dad, etc...to advertise my cleverness.XD
 » 7 months ago, # |   -30 so, it is not rated for normal contestants? Why !
•  » » 7 months ago, # ^ |   +31 so, it is not rated for normal contestants? Why !So, it is rated for you
 » 7 months ago, # |   +46 How many problems will be there and what's the score distribution?
 » 7 months ago, # | ← Rev. 2 →   -6 i hope after this round my rating will be purple rather than stil blue.i still remember that in global contest 1,the difficulty between problems was not very proper.so i hope this round will be(and can be)better
 » 7 months ago, # |   +4 Удачи! means Good Lucky!!
 » 7 months ago, # |   0 Удачи
 » 7 months ago, # |   +8 Expecting this round to be full of awesome questions with strong pretests ;)
 » 7 months ago, # |   +81 Where is the number of problems and score distribution? :)
•  » » 7 months ago, # ^ | ← Rev. 2 →   0 Same where the black number of 300iq
•  » » 7 months ago, # ^ |   +9 Is this the difference between a blue coder and red coder ? :PWhen I get less upvotes for the same comment I did 17 hours ago :(
 » 7 months ago, # | ← Rev. 2 →   +9 I hope that my rating can be improved in this contest! Hope that all of us can have a good result!
 » 7 months ago, # |   +5 vammadur now has positive rating :o
 » 7 months ago, # |   +233 A fair and balanced problemset.
•  » » 7 months ago, # ^ |   +7 I don't agree. But I upvoted.
•  » » » 7 months ago, # ^ |   0 I didnt have any ideia to solve A, wtf
•  » » » » 6 weeks ago, # ^ |   0 Two pointers
•  » » » 7 months ago, # ^ |   -10 Cause he is red?
•  » » » » 7 months ago, # ^ |   +60 Cause I'm sarcastic?
•  » » » » » 7 months ago, # ^ |   +5 No way
•  » » » » » » 7 months ago, # ^ |   +5 ikr
 » 7 months ago, # |   +5 Imo, one of the most interesting contest I've ever participated.
 » 7 months ago, # |   +5 What's the pretest 7 in E?
•  » » 7 months ago, # ^ |   0 My guess is something like that: 5 — 11 7 5 13 9. Answer is 15 but my answer is 14. Only noticed it at last minute.
•  » » » 7 months ago, # ^ |   0 How is answer 15 and not 14?
•  » » » » 7 months ago, # ^ |   0 Add 2 a[0] to a[3], 1 a[0] to a[2] and 2 a[0] to a[1]. Now there is 13 triangles and 6 a[0].
•  » » » » 7 months ago, # ^ | ← Rev. 2 →   0 It is possible. One example is that:1 1 1 (1) 1 2 2 (2) 1 3 3 (3) 1 4 4 (4) 1 4 4 (5) 1 4 4 (6) 1 4 4 (7) 1 4 4 (8) 1 5 5 (9) 2 2 2 (10) 2 3 3 (11) 2 4 4 (12) 3 5 5 (13) 4 5 5 (14) 5 5 5 (15)
•  » » » » » 7 months ago, # ^ |   0 But.. how can you make triangle from 2 sticks of length 2^x and one with length 2^(x+1)? Sum of every 2 sides needs to be greater than 3rd side. What am I missing?
•  » » » » » » 7 months ago, # ^ |   +1 You're right. One correct solution is3*(1,1,1), 2*(1,2,2), 1*(2,2,2), 1*(3,3,3), 2*(3,4,4), 3*(4,4,4), 3*(5,5,5).
•  » » » » » » 7 months ago, # ^ |   0 I'm sorry. I revised the comment.
•  » » » 7 months ago, # ^ |   0 But I got TLE on the pretest 7 once, and after removing time-consuming loop, I passed that pretest(though I couldn't pass the pretest 11). So the possibility, that the pretest 7 is that in which n is large, also exists.
•  » » 7 months ago, # ^ |   0 maybe you should use "I64d" in C++ for the answer
•  » » » 7 months ago, # ^ |   0 I did
 » 7 months ago, # |   +5 How to solve problem E ?
 » 7 months ago, # |   +8 How to solve E?
•  » » 7 months ago, # ^ |   +3 Observe that there are only two possible type of triangles, ($2^{x}, 2^{x}, 2^{x}$) or ($2^{x}, 2^{y}, 2^{y}$) where $x •  » » » 7 months ago, # ^ | 0 This dp is two-dimensional? •  » » » 7 months ago, # ^ | +3 I still don't understand the DP; Can't the number of unused sticks be up to$10^9 \cdot n$? •  » » » » 7 months ago, # ^ | 0 When it gets to "3", you make a new triangle. So it's only 0/1/2 •  » » » » » 7 months ago, # ^ | 0 Well, I'm not sure I've understood your solution; but how about the case something like {10, 2, 2, 2, 2} ? In my opinion you have to store the state where there are 10 unused sticks when looking at the second element of the array. •  » » » » » » 7 months ago, # ^ | +5 No. Let dp[i] store number of maximum triangles you can make till i and f[i] store number of unused sticks till i. Then, recurrence relation is first pair sticks of length$2^{i}$with f[i-1] as much as you can and then make triangles using remaining sticks of$2^{i}$length.So, when we look at second element, there is only 1 unused stick and 3 triangles made •  » » » » » » » 7 months ago, # ^ | +3 I've been thinking on my way home and understood. Thanks a lot for teaching me anyway. •  » » 7 months ago, # ^ | ← Rev. 3 → +28 The triangle either has to have three sides of of the same length, or two of the same length and one shorter. Iterate through the lengths from smallest to largest. Keep the number of leftover sticks. In every step, make as many triangles from two sticks of the length you are at, plus one leftover stick. Then, make as many triangles from 3 of the current length. If any sticks of the current length remain, add them to leftovers.This works because the sticks of the current length are "rarer" than the leftover ones, because they turn into leftovers at the end of the step. Thus, you want to use the "rarer" type less and the "less rare" type more. •  » » » 7 months ago, # ^ | 0 Got it, thank you.  » 7 months ago, # | +18 oh god if there are people talking it's so hard to think my mind exploded thinking in A only ... I will never participate without having quite place again  » 7 months ago, # | 0 Did anyone solve E by dp, i dont know why I got WA 52411976 •  » » 7 months ago, # ^ | 0 Counterexample34 4 4should output 4 •  » » » 7 months ago, # ^ | 0 Thanks i got it •  » » 7 months ago, # ^ | 0 Fails on this test : 3 1 1 4 •  » » » 7 months ago, # ^ | 0 Thanks i got •  » » 7 months ago, # ^ | ← Rev. 2 → 0 ignore this  » 7 months ago, # | +119 Div.2 A~C & Div.1 E/F  » 7 months ago, # | +74 What a big difficulty gap! (Well, not being able to solve E, I have no right to complain about it though:( •  » » 7 months ago, # ^ | +14 Seems F,G,H are prepared for LGMs  » 7 months ago, # | +70 Very unbalanced contest. D and E are too easy, F and G are too difficult :/  » 7 months ago, # | +97 Were problems F, G, H given to solve just for fun?  » 7 months ago, # | ← Rev. 2 → +64 Why the length of this contest is only 2h？  » 7 months ago, # | +97 Almost all div.1 coders have same set of AC. I think this is bad choice (The problems are good, although).  » 7 months ago, # | 0 How to solve C? •  » » 7 months ago, # ^ | 0 Hint : Number of non-matching squares in every column must be even, and you can reverse a[i][j] and a[i][1] together. •  » » 7 months ago, # ^ | ← Rev. 7 → +14 For the answer to be "Yes", a necessary condition is that the XOR of each row must be the same in A and B, because the operation cannot change it; the sum in each row can only decrease by 2, stay the same or increase by 2, thus the XOR stays the same. Similarly for columns.And it turns out that this is sufficient as well. Think of the 1D case, where you have 1 row and you must always flip two elements. Iterate i from 1 to N and always change a[i] to b[i], flipping also a[n]. Then, when you reach i=n, a[i]=b[i] by the XOR invariant. For the 2D case, you can fix rows in this way and then solve for a smaller matrix. Once you reach a state where you have only 2 rows, observe that fixing one row must fix the other, also by the XOR invariant. •  » » » 7 months ago, # ^ | 0 I got it, thank you •  » » 7 months ago, # ^ | 0 You iterator through all position if that position in A different with B you can find any rectangle with top-right and bottom-left is needed to change. Repeat until you cant find such rectangle or all position has been processed. •  » » 7 months ago, # ^ | 0 Check the xorsum of every row/column. You can transform into any matrix with the same xors. •  » » 7 months ago, # ^ | ← Rev. 2 → +43 Here's a different way to do it that is also really simple to implement:Notice that all operations can be done as multiple operations of 2x2 submatrices. Then, notice that this operator is commutative and associative (since xor is commutative and associative) and you would never do the same operation twice.Thus, iterate from i=1..n-1 and j=1..m-1 and if a[i][j] is different from b[i][j], then apply the operation to the submatrix of (i,j) and (i+1, j+1). It suffices to check at the end whether the last column and row of a and b are the same.If you know some group theory, then in general, there is a type of question that appears that can be boiled down to "Here's a group action and a set. Given two objects, are they in the same orbit?" Often times these problems can be solved by finding a small list of generators and simply brute force testing whether it's possible. Other times it is solved with invariants, as other people noted. •  » » » 7 months ago, # ^ | 0 where you did study the group theory ? •  » » » » 7 months ago, # ^ | +3 At university. However, brilliant.org has good stuff on this. Check out the background knowledge section of https://brilliant.org/wiki/burnsides-lemma/ for info on groups and group actions/orbits.  » 7 months ago, # | +8 Problem C is a good problem out of the easy problem.  » 7 months ago, # | +21 Greedy solution for E: https://codeforces.com/contest/1119/submission/52403202 Go from right to left and greedily make as many triangles of this type as you can. A triangle of type i is made of (i,i,j), where j <= i. There's a O(1) formula instead of my binary search, I'm 99% sure. •  » » 7 months ago, # ^ | +4 Yes, you can just keep track of the max number of triangles created at each step. Then, calculate the number of unused legs. It's optimal to use as many of these as possible, and the most you will be able to use is min(a[i]/2, unused). Then use as many triangles from the leftover a[i] as possible.  » 7 months ago, # | +35 I don't think that F is conceptually that hard, but it's a lot of work.Excerpt from my code: calculate degrees of vertices, and then sort the adjacency list by the degree, so that I can do edge removals in$O(1)\$: for (int i = 0; i < N; ++i) { D[i] = E[i].size(); sort(E[i].begin(),E[i].end(), [&](pii&a, pii&b) { return D[a.x] > D[b.x]; }); } Such a thing is hard to find if you get WA on pretests two minutes before the end. Where can I apply for mental disability pension?
 » 7 months ago, # |   +1 I think the length of this contest should be 02:30. :)
 » 7 months ago, # |   +86 A-E are solved by 1000+ users while FGH are solved no more than 8 users each.Amazing gap! So I think it's not a balanced problemset at all. A-E is too easy for candidate masters and masters. But even most grandmasters can't solve one of FGH. When I noticed that it took tourist 1h to solve F, I understood that I have no chance to solve it during contest.Congratulations to those who solved 6 problems, real legand!
 » 7 months ago, # |   +60 Another case of the classic "Let's make a div1 round by appending some insanely hard problems to a div3 one" :(Does the following work for F? solution? to FWe calculate DP[i][x] and DP_NOP[i][x], where DP[i][x] is the cost of fixing i's subtree, such that we have removed all edges that are not adjacent to a node with degree at least x. We do not calculate DP[i][x] or DP_NOP[i][x] if node i has degree less than x.To calculate these values, do DFS, and at every node i, after solving its children, sort the children by their degrees, and then calculate DP[i][x] and DP_NOP[i][x] in order of increasing x. Whenever one of i's children has its degree fall below x, we push the weight of the edge to it into some sort of a sorted datastructure with prefix sum queries.At every x, we then go through all of the connections with large enough degree, pushing DP_NOP[t][x] — DP[t][x] into a vector, and adding DP[t][x] to the cost we have to pay no matter what.Now to calculate DP_NOP[i][x], we want to pay the deg — x — 1 smallest costs among the datastructure and the vector. To do this, we just loop the vector, and compare the costs.To calculate DP[i][x], we do the same, but now only want to find the deg — x smallest costs.At every node, we loop to the degree of the node, and for every degree, we loop over all neighbors with degree at least that value, and at every such loop, we do a bunch of log(n) stuff. For every edge in the graph, we do O(d log(n)) work, where d is the minimum of the degrees of the nodes on the ends of the edge. But the sum of d is now O(n). Hence, the total time complexity is O(N log N)The sum of d is O(n) since we can change the tree such that we get a tree where the child always has smaller or equal degree while not decreasing sum of d's. But in such a tree, the sum of d's is 2n, since every edge is counted twice: Once for itself and once to increase how many times the edge to the parent from node the edge is from is counted.
 » 7 months ago, # |   +8 Absolutely beautiful test cases! Especially for problem C. That's how you do it.
 » 7 months ago, # | ← Rev. 2 →   +11 The problem difficulty gap should be taken care of, else it is speed which differentiates everyone which is really unfair on some masters and above who know much more.
 » 7 months ago, # |   0 Will the editoral be published?
•  » » 7 months ago, # ^ |   +5 Yep, just wait for the system testing to end.
•  » » » 7 months ago, # ^ |   0 thanks!)
 » 7 months ago, # |   +18 vammadur makes the new record for highest rating change. Congrats!!
•  » » 7 months ago, # ^ |   +1 Damn! +1164
•  » » 7 months ago, # ^ |   +20 get out of here Mhammad1
•  » » » 6 months ago, # ^ |   0 Congrats xD
 » 7 months ago, # |   +7 I want a T-shirt so bad, I would kill for one , the probability of me getting it is 1/470 :)
•  » » 7 months ago, # ^ |   +11 *20/470
•  » » » 7 months ago, # ^ |   +21 Yeah your right now that i think about i might have a chance
•  » » » » 7 months ago, # ^ | ← Rev. 3 →   -22 Actually thats wrong too the correct answer is c(19,469)/c(20,470)
•  » » » » » 7 months ago, # ^ |   +5 That's same as 20/470 :`\
 » 7 months ago, # |   0 Can the problem C be solved using brute force ?i'm getting TLE, just curios if anyone managed to solve it in such way !
•  » » 7 months ago, # ^ |   +1 I don't think that it's possible with your bruteforce. Imagine 500*500 matrix with all zeros and you need to transsform it into all ones. It would need 500*125 inversions and it's quite long
•  » » 7 months ago, # ^ |   0 I simulated the whole process using many speedup tricks. 52395830
•  » » » 7 months ago, # ^ |   0 No, you used the XOR invariant solution ( which still don't understand )i literally simulated the process.
•  » » » » 7 months ago, # ^ |   0 What my code does is the same with your code, just without "Counter" variable and one observation that if there is just single 1 in any row or column, then it's No.
 » 7 months ago, # |   0 I think A was really hard for A I think C was popular problem and i have seen it before
•  » » 7 months ago, # ^ |   0 could you provide a link/s to the similar problems to the C ?
•  » » » 7 months ago, # ^ |   0 It was not a coding problem
•  » » 7 months ago, # ^ |   0 There was a bit different problem not so long ago: https://codeforces.com/contest/1136/problem/C Solution's ideas a bit similar too ._.
•  » » » 7 months ago, # ^ |   0 Yes ! not so long, this kind of problems can cause a matrici-phobia T_T
 » 7 months ago, # |   0 I submitted this solution 52405088 for problem D during the contest but I got RTE in the system test, then I only modified something after the contest and got AC 52416473My question is, why did the first one got RTE and why actually this modification made any difference?!!
•  » » 7 months ago, # ^ |   +3 It's not a correct comparator. a > a for any a. It's bad.
•  » » 7 months ago, # ^ |   +3 Comparator needs to be LESS function, not LESS_OR_EQUAL.
 » 7 months ago, # | ← Rev. 2 →   +73 Who on earth could solve the first 5 problems within 12 minutes in the contest... tourist, are you a human? I wanna know how "TOO obvious" for you on these problems.
•  » » 7 months ago, # ^ |   0 realDonaldTrunp, are you a human? I wanna know why "BORDER wall" on the border.
•  » » » 7 months ago, # ^ | ← Rev. 2 →   0 "
•  » » 7 months ago, # ^ |   +15 It’s a witch-hunt Donald.
•  » » 7 months ago, # ^ | ← Rev. 2 →   +8 Who on earth could say these words after the contest... realDonaldTrunp, are you a human? I wanna know how "REAL donaldtrunp" for you to have an ID like this.
•  » » 7 months ago, # ^ |   +20 He is not from Earth. He is tourist on our planet.
 » 7 months ago, # |   0 How to solve problem B,I am so sad.
 » 7 months ago, # |   +6 Contest rank : 666 New rating : 1900 Ok, I'm cool.
•  » » 7 months ago, # ^ |   +25 You should have told yourself "hell yeah!".My previous rating change: 0. My rating change from 3 rounds ago: 0.
•  » » » 7 months ago, # ^ |   +12 Hell yeah!
 » 7 months ago, # |   +11 When will you announce tshirt winners?
 » 7 months ago, # |   0 When will you distribute the t-shirts?
»
7 months ago, # |
Rev. 2   +75

UPD: I accidentally computed 80 winners instead of 50 in the first edition, now the list is fixed.

T-shirt winners!

As always, we used the following two files and the seed equal to the score of the winner (this time it is 9848).

randgen.cpp
get_ranklist.py

And the t-shirt winners are:

List place Contest Rank Name
1 1119 1 ecnerwala
2 1119 2 tourist
3 1119 3 Um_nik
4 1119 4 Endagorion
5 1119 5 Petr
6 1119 6 mnbvmar
7 1119 7 sunset
8 1119 8 CauchySheep
9 1119 9 yokozuna57
10 1119 10 realDonaldTrunp
11 1119 11 krijgertje
12 1119 12 yhx-12243
13 1119 13 lumibons
14 1119 14 leaf1415
15 1119 15 Arterm
16 1119 16 Isaf27_loves_me
17 1119 17 jonathanirvings
18 1119 18 lych_cys
19 1119 19 fateice
21 1119 21 ksun48
22 1119 21 MofK
23 1119 23 stO
24 1119 24 Kostroma
25 1119 25 hos.lyric
26 1119 26 neal
27 1119 27 Alex_2oo8
28 1119 28 tlwpdus
29 1119 29 I_love_Tanya_Romanova
30 1119 30 E869120
37 1119 36 edisonhello
40 1119 40 Rzepa
47 1119 47 Itst
153 1119 152 UnstoppableSolveMachine
184 1119 184 beet
208 1119 208 LzyRapx
210 1119 210 sas4eka
234 1119 234 Atreus
257 1119 254 cuiaoxiang
266 1119 265 altunyanv
268 1119 268 Trisolaris
284 1119 284 t90tank
288 1119 288 wxjor
335 1119 335 trabbbart
392 1119 392 zaki_joho
398 1119 397 StevenZhu
431 1119 429 DQS
434 1119 434 Filyan
446 1119 445 bknshn
463 1119 462 Jungarr1k
•  » » 7 months ago, # ^ |   +3 Yay!!!
•  » » » 7 months ago, # ^ |   +101 Wtf! My name got removed. fmllllllllllllll
•  » » 7 months ago, # ^ |   +11 Wow, the contest couldn't have gone worse than this for me. I was selected in the previous list, but unfortunately, today was not my day! Guess I'll never get a cf t-shirt ;_; ...
•  » » 7 months ago, # ^ |   0 KAN My rank is also 288,how is the tie broken?
•  » » » 7 months ago, # ^ |   +12 Rank, last submission time, handle. You can check the code for details.
•  » » 7 months ago, # ^ |   +6 Yay!But how to get the T-shirt? Shall I write an address? (My English is not good please don't laugh at me)
•  » » » 7 months ago, # ^ |   0 Fill out your address in the settings and it's fine
•  » » » » 7 months ago, # ^ |   0 Thanks
•  » » 6 months ago, # ^ |   -8 I should have understand A earlier... (I got 235th place.. 2 points off from 234th)
 » 7 months ago, # |   +33 Got a notification that KAN mentioned me, and then I see the update. This is so sad.
 » 6 months ago, # |   0 Good chance for Newbie pepole
 » 6 months ago, # |   0 300iq tasks difficulties have not been assigned yet. Could you please fix that?
•  » » 6 months ago, # ^ |   0 Thanks, done.
 » 2 months ago, # |   0 Anyone with FFT idea in problem E? it is in the FFT category .. although i have the greedy solution