Добрый день!
6 апреля, в 14:35 UTC+3 состоится Codeforces Global Round 2.
Это второй раунд из серии Codeforces Global Rounds, которая проводится при поддержке XTX Markets. В раундах могут участвовать все, рейтинг тоже будет пересчитан для всех.
Призы в этом раунде:
- 30 лучших участников получат футболки.
- 20 футболок будут разыграны случайным образом среди участников с 31-го по 500-е место.
Призы в серии из 6 раундов в 2019 году:
- За каждый раунд лучшим 100 участникам начисляются баллы согласно таблице.
- Итоговый результат участника равны сумме баллов для четырех лучших выступлений этого участника.
- Лучшие 20 участников по итоговым результатам получают толстовки и сертификаты с указанием места.
Задачи для этого раунда были разработаны целым коллективом авторов: 300iq, cyand1317, Aleks5d, RDDCCD, KAN, gen.
Спасибо KAN за помощь в координации раунда, а также isaf27, Lewin, ----------, Errichto, arsijo, cdkrot за тестирование!
Удачи!
Поздравляем победителей!
1) ecnerwala
2) tourist
3) Um_nik
4) Endagorion
5) Petr
Friendly time to Chinese!
Great!!!
+1
Yes, it would be better if future rounds will also hold at friendly time.
That means that, there will be people in some country that feel the contest time is bad.
I can sleep better today!! :)
Как так-то, а?
уже топ 8 по вкладу
Лол, Ильдар опять без нутеллы останется...
:(
:(
Hope that it won't happen again XD
ofc, will be worse...
Pretests for these rounds are extremely weak, that is why I won't participate in them anymore.
hope high rating!
hope the round will be rated.
it feels like we have been waiting for ages for this round
can you add the link Codeforces Global Round 1
Codeforces Global Round 1
How many of you feel that Codeforces is decreasing the frequency of contests?
Maybe because the best problem developers are busy with ICPC WF. XD Hope the Contests will be more soon.
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)
You can always participate virtually on some previous contest or on a one from the Gym.
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.
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?
Mb, "The prizes for this round:" means, that not all rounds will be with the same prizes?
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.
Maybe they are different T-shirts?
I'm sure it's ok if such person gets all 6 different ones haha
The more the better, I can give it to my mom, my girlfriend , my dad, etc...to advertise my cleverness.XD
wow!
so, it is not rated for normal contestants? Why !
so, it is not rated for normal contestants? Why !
So, it is rated for you
А почему первая буква красная?
Это цифра так-то
How many problems will be there and what's the score distribution?
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
Удачи! means Good Lucky!!
Удачи! means Good Lucky!!
Удачи
Expecting this round to be full of awesome questions with strong pretests ;)
Where is the number of problems and score distribution? :)
Same where the black number of 300iq
Is this the difference between a blue coder and red coder ? :P
When I get less upvotes for the same comment I did 17 hours ago :(
Удачи! -->> Good Luck !!!
I hope that my rating can be improved in this contest! Hope that all of us can have a good result!
vammadur now has positive rating :o
A fair and balanced problemset.
I don't agree. But I upvoted.
I didnt have any ideia to solve A, wtf
Cause he is red?
Cause I'm sarcastic?
No way
ikr
Imo, one of the most interesting contest I've ever participated.
What's the pretest 7 in E?
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.
How is answer 15 and not 14?
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)
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?
You're right. One correct solution is
3*(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).
I'm sorry. I revised the comment.
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.
maybe you should use "I64d" in C++ for the answer
I did
How to solve problem E ?
How to solve E?
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<y$$$. Now, you can do dp storing the number of triangles and number of sticks unused till i.
This dp is two-dimensional?
I still don't understand the DP; Can't the number of unused sticks be up to $$$10^9 \cdot n$$$ ?
When it gets to "3", you make a new triangle. So it's only 0/1/2
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.
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
I've been thinking on my way home and understood. Thanks a lot for teaching me anyway.
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.
Got it, thank you.
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
Did anyone solve E by dp, i dont know why I got WA 52411976
Counterexample
3
4 4 4
should output 4
Thanks i got it
Fails on this test : 3 1 1 4
Thanks i got
ignore this
Div.2 A~C & Div.1 E/F
What a big difficulty gap! (Well, not being able to solve E, I have no right to complain about it though:(
Seems F,G,H are prepared for LGMs
как решать E??
wow a speed contest.
Very unbalanced contest. D and E are too easy, F and G are too difficult :/
Were problems F, G, H given to solve just for fun?
Why the length of this contest is only 2h？
Almost all div.1 coders have same set of AC. I think this is bad choice (The problems are good, although).
How to solve C?
Hint : Number of non-matching squares in every column must be even, and you can reverse a[i][j] and a[i][1] together.
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
ifrom 1 to N and always changea[i]tob[i], flipping alsoa[n]. Then, when you reachi=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.I got it, thank you
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.
Check the xorsum of every row/column. You can transform into any matrix with the same xors.
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.
where you did study the group theory ?
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.
Problem C is a good problem out of the easy problem.
Greedy solution for E: https://codeforces.net/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.
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.
I think the length of this contest should be 02:30. :)
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)$$$:
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?
I think the length of this contest should be 02:30. :)
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!
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?
We 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.
Absolutely beautiful test cases! Especially for problem C. That's how you do it.
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.
Will the editoral be published?
Yep, just wait for the system testing to end.
vammadur makes the new record for highest rating change. Congrats!!
Damn! +1164
get out of here Mhammad1
Congrats xD
I want a T-shirt so bad, I would kill for one , the probability of me getting is 1/470 :)
I want a T-shirt so bad, I would kill for one , the probability of me getting it is 1/470 :)
*20/470
Yeah your right now that i think about i might have a chance
Actually thats wrong too the correct answer is c(19,469)/c(20,470)
That's same as 20/470 :`\
Can the problem C be solved using brute force ?
i'm getting TLE, just curios if anyone managed to solve it in such way !
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
I simulated the whole process using many speedup tricks. 52395830
No, you used the XOR invariant solution ( which still don't understand )
i literally simulated the process.
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.
I think A was really hard for A I think C was popular problem and i have seen it before
could you provide a link/s to the similar problems to the C ?
It was not a coding problem
There was a bit different problem not so long ago: https://codeforces.net/contest/1136/problem/C Solution's ideas a bit similar too ._.
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 52416473
My question is, why did the first one got RTE and why actually this modification made any difference?!!
It's not a correct comparator. a > a for any a. It's bad.
Comparator needs to be LESS function, not LESS_OR_EQUAL.
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.
realDonaldTrunp, are you a human? I wanna know why "BORDER wall" on the border.
"
It’s a witch-hunt Donald.
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.
He is not from Earth. He is tourist on our planet.
How to solve problem B,I am so sad.
Contest rank : 666 New rating : 1900 Ok, I'm cool.
You should have told yourself "hell yeah!".
My previous rating change: 0. My rating change from 3 rounds ago: 0.
Hell yeah!
When will you announce tshirt winners?
When will you distribute the t-shirts?
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).
And the t-shirt winners are:
Yay!!!
Wtf! My name got removed. fmllllllllllllll
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 ;_; ...
KAN My rank is also 288,how is the tie broken?
Rank, last submission time, handle. You can check the code for details.
Yay!
But how to get the T-shirt? Shall I write an address? (My English is not good please don't laugh at me)
Fill out your address in the settings and it's fine
Thanks
I should have understand A earlier... (I got 235th place.. 2 points off from 234th)
Got a notification that KAN mentioned me, and then I see the update. This is so sad.
300iq tasks difficulties have not been assigned yet. Could you please fix that?
Thanks, done.
Anyone with FFT idea in problem E? it is in the FFT category .. although i have the greedy solution