Hi!
We are glad to invite you to take part in Codeforces Round 564 (Div. 1) and Codeforces Round 564 (Div. 2), they will be held on Jun/07/2019 15:05 (Moscow time). The round will be rated for both divisions.
Participants in each division will be offered 6 problems and 2 hours to solve them, including 4 shared problems for both divisions, and one of them has two versions with the only difference in constraints.
The problems were written and prepared by me, Sulfox, QAQAutoMaton, ODT, ccz181078, rushcheyo and PinkRabbitAFO.
Great thanks to 300iq for coordinating and testing the round, we enjoyed the experience of preparing a round with him.
Thanks to Um_nik, KAN, isaf27, xht37, ButterflyDew and DKACVenus for testing the round, too.
Of course, thanks to MikeMirzayanov for amazing systems Codeforces and Polygon!
Last but not least, thanks to everyone who participates in this round, for making our efforts meaningful.
Both English and Chinese editorials will be available after the contest.
UPD 1: The scoring distribution will be:
Div.2: 500 — 1000 — 1500 — 1750 — (1250 + 1250) — 2750
Div.1: 500 — 750 — (750 + 750) — 1750 — 2500 — 2750
UPD 2: Congratulations to the winners!
Div.1:
Div.2:
UPD 3:
The English Editorial and the Chinese Editorial are published.
Wish everyone have fun!
Orz lk
hope short problems and high rating!
why !!!
you should have said short solutions and high ratings :P
ratism
Friendly time to Chinese！
It's Happy DuanWu Festival match
happy DuanWu Festival to all the Chinese
But bad time for people
I think it's good for Chinese people!
(After 10 p.m. is too late
I think this is really a good time for Chinese
Chinese needn't stay up until midnight QwQ
We are able to have a good sleep after this contest qwq
Not, if you perform badly in this contest.
Time :)
Div1+Div2, Dragon Boat Festival, UTC+8 20:05, Chinese editorial. Si Bei Yi Man!!!
what does "Si Bei Yi Man" mean?
Chinese pinyin(phonetic transcription) for "四倍役满"（逃）
Which problem will have two subtasks?
C1 and C2
Hope my name to become orange again qwq.
Could you promise no anime pictures in contest?
Yes, of course. Because ODT promised to write the statement in March, and finally said he wouldn't a week ago, so I wrote the statement.
qwq
You can find this problem very difficult and give it up as soon as possible by the anime pictures.
I hope this round will not be full of hardcore math problems :(
I think this round will be full of data stucture problems because of @ODT
orz ynoi
Orz lxl
A task that has two versions counts as one task or two?
For example, if a problem worth 2500 points, then maybe the easier version worth 1750 points and the harder version worth 750 points. (Maybe swapped in this contest because of ODT?)
let there be tasks A1 and A2, will it be like one task or two?
Two tasks. For example D1 (easier version) and D2 (harder version). They will be scored separately.
For example: 1163C1 - Power Transmission (Easy Edition) and 1163C2 - Power Transmission (Hard Edition).
Welcome back to div3
Short journey in div2
Chinese editorials? Cool!
Happy Dragon Boat Festival!
it should be updated...
whatever...i dont know much about ps
not "Round 0x233" anymore qaq
long live china , I love all Chinese
Could be my chance to get to purple.
All I have to do is +22 rating...
Seems easy enough (not)
Also. Wish everyone a happy Dragon Boat Festival!
This round is so friendly for Chinese QwQ
Let's have fun in this round QwQ
I am ready to face data structure problem !
Wow,that will be so cool to have a such great contest in Dragon Boat Festival! :)
Chinese round =earlier time
i hope this contest will make me green and i will not be newbie anymore ... :/
Good Luck and remember dont focus on ratings but on learning from the contests and your rating will automatically increase :)
Yes,it is a truth for every oier&acmer
Chinese editorials that cool,but why there is not Chinese problems?
Nice time for Chinese！I wish the problems' statements can be understood clearly.(maybe making the unuseful background into another paragraph is a good idea?)Hope for an excellent competition experience.
I need an anime-themed contest.
We need an anime themed contest.
totally agree with you :D
Probably a Catholly-themed contest because of ODT
Chinese round again...It's great, but I think maybe I should get ready to face hard data structure.
orz rqy, rqy tql ddw.
abc def, ghi jkl mno.
ABCDEFGKNMLGB
wo qi le , yi qiang miao le , you shen me hao shuo de
wdnmd??
What did you say?
Well sorry about orz qaq
Am I right that one of the problems has different constraints in different divisions?
Because if there are two similar problems with different constraints in one contest then there is a problem:
no, since it will only be possible to block both of these subtasks.
Fake accounts exist.
When a simple and difficult version of the problem is solved, then it will be possible to block the task.
thank you for the earlier time for me
maybe we can have zongzi as a snack when we are in the contest?
Wish everyone high rating!
repeat the math)
Could we view the problems in Chinese?
Orz Sooke, QAQAutoMaton, ODT, ccz181078, rushcheyo and PinkRabbit and wish everyone have fun!
Orz LJC00118, Sooke, PinkRabbit, for they AKed IOI! Good luck to everyone!
Well sorry about orz . But that's really a good DW contest .
I hate difficult data structure problems because I can't even write it out.
Can you tell me if a person with rating not less than 2100 can participate in Div2? I do not know because I am not used to codeforces.
If the round is divided into 2 divisions, then no (you have to either participate in Div1 or wait until it's over). Otherwise, if it's a Div.2-only, it's free to do so. ;)
Thank you very much!
Oh my, only a year and you've gone from a green to an orange problemsetter. ;)
Congrats for your (and also the other guys') first round! ;)
I always remember you since that comment :) Thank you for your encouragement!
Oh, I use the mirror by mistake again..
I am very confused whether to participate in contest or watch Federer vs Nadal.
It's time to take back what I've lost!!!!!!!!!!
Chinesse round!!!Yes!!!! but maybe there are many data stucture problems.(maybe there are full of data stucture problems) my rating will down.....
Why is that m1.codeforces.com, m2.codeforces.com and m3.codeforces.com not available these days?
I can enter m2.
For me its showing "Server not found" for all the three.
What's the score for each problem and what problem have to subtasks? QAQAutoMaton ODT ouuan
why not show us the scoring distribution?
I guess the 3 Minute Rule ;p
Bruh!
Where should I register? I haven't registered yet and so not able to submit.
Maybe u wont be able to submit till the end
Please, Stop this fucking repeated things
https://codeforces.me/blog/entry/66587?#comment-507367
https://codeforces.me/blog/entry/67340?#comment-515473
How to solve div 2 C?
For each element, find the required number of moves to put it in place. Then, for each element, find the required number of moves to put it in place after moving it the maximum required times from the previous iteration. Keep going until this maximum number doesn't change. That's the answer.
Binary search the number of zero moves required + number of elements to put in place?
I didn't use binary search. Thinking about it now, I'm not convinced my solution wouldn't be O(n^2) in worst case. It did pass system testing, though, so take that as you will.
I suppose if you use binary search in a clever way, you can guarantee a worst-case complexity of O(n log(n)), but I guess that wasn't necessary for this problem.
The idea is to play X blank cards, where X takes values from [0, N]. Then, you should check if you can play the cards 1, 2, 3, ... N in order. Check if you can do it with X == 0 first and then do a binary search. Only the binary check function remains, and there's many ways to do it with some data structures, I used a std::priority_queue to effectively sort the values of the cards in hand. It's O(n logn) and I hope it passes the tests after the hacks, too.
EDIT: I failed after second system testing :(
Thanks guys, got it.
/In worst case, we need to take all cards, then play all cards in order. How much can we shorten this?
Case 1: There is an sorted postfix in b. So we can simply play all cards in order. Then number of moves is n-(len_sorted_postfix). All numbers must be available. Just check if this is possible.
Else, we need to take (or have on hand) card 1, then card 2, then card 3...
So, min moves is max of: pos(card 1)+n, pos(card2)-1+n, pos(card3)-2+n, ...
You don't need binary search at all, you can separate it into 2 cases: 1. The first k numbers are already in the deck, and you will be able to place cards such that you finish in n-k turns. We can find k easily, then we make sure that it's possible by ensuring that for all cards in the deck besides the last k, we will get them in our hand soon enough to play them, that is, their index + 2 is at least their value — k. 2. You have to collect cards in your hand for a while, then you can place them all into the deck 1 at a time. In this case we just check for each card the time to get it into our hand and then back into the deck in the right position, and the answer is the max over all cards in the deck of their index + 2 + (n — their value).
Mathforces...
I dont understand why people complain about math? Most of programming reduces down to mathematics...
What, you wanted ScienceForces? I guess having maths problems is not a problem.
Well,I once saw a problem about balancing chemical equations,but that can be reduce down to Gaussian Elimination,so ScienceForces may become Mathforces in the end
I did not have 2 seconds to send the solution of the problem D, because my mouse lag (((((((((
UPD: if this solution will get AC, I`ll break my mouse.
UPD2: Accepted
UPD3: Mouse RIP
Same here for C, I fixed the last bug too late
SO, is the mouse broken?
Real Mathforces...though I expected some data structure
How to solve Div2 c ????
UPD : there is my submission https://codeforces.me/contest/1173/submission/55271422
Binary search the number of zero moves required + number of elements to put in place. https://ideone.com/WgHMmm
What do you mean by binary search number of zeros ?
from zeroes i mean number of empty moves you will perform before starting the sorted sequence. let me rephrase it as number of cards with value zero that you will play before playing other cards. Once we find this minimum number by binary search we can add n to it to get the answer.
Be sure to check value zero before hand (case where we don't need to make any zero move). have a look at my submission here https://codeforces.me/contest/1173/submission/55269800
Found out where i made a mistake on 2C in last 5 seconds
submit
"contest is over"
R.I.P rating
;(
I wasn't able to solve any problem in div1... is the color of my name wrong?
don't worry, just pretend you didn't participate, your rank will not drop anyway
but it was nice problem really close from solving it :(
same here.
Funny how they switched B with C this time.
I thought so too at first
But once I came back to solve B, god I felt so dumb to go after C first
How to solve div2D?
Passed pretest with this — Root the tree. Fix first position as root. Each subtree will occur consecutive in circle. Then rotate the circle.
$$$n \cdot \prod_{i=1}^n deg(i)!$$$
proof?
First observation is that the solution is valid if and only if each subtree is in consecutive points on the circle.
When given a subtree of root $$$i$$$ and a range of points of its size, how many ways to place it ? It has $$$deg(i)-1$$$ subtrees of its own that can be in any order which gives $$$(deg(i)-1)!$$$ and the root can be anywhere between them, $$$(deg(i)-1)+1=deg(i)$$$ possibilities which gives $$$deg(i)!$$$ and the same goes for each subtree independantly.
For the root it's almost the same, you have $$$n$$$ positions for the root on the circle and then $$$deg(root)!$$$ for placing the $$$deg(root)$$$ subtrees.
Could you please explain how this works?
We're so sorry. We tried to hack the $$$\mathcal O(n\sqrt{n\log n})$$$ solution for 1F, but hacked webmaster's treap solution unintentionally.
Writer's solution can pass in $$$1.5s$$$ in $$$\mathcal O(n\log n+m\log^2 n)$$$.
upd: It seemed that I'm wrong.. He said his solution is not in correct complexity..
Why sorry?
Because his solution is correct with big constant.
upd: It seemed that I'm wrong.. He said his solution is not in correct complexity..
The fact that if this round was combined it wouldn't make any difference XD
When will we see the problem rating? After the system test done?
In 1-2 days
When it takes you so long to debug C and understand D that you can't debug the indexes in your trivial code in time :/
Always possible. We will place a portal at first row and first column so that the y-coordinate that wants to get to y=1 gets there, and the x-coordinate that wants to get to x=1 gets there. This changes where some later indexes want to go, but we do not care about that. Then just recurse.
The indexing of the code might still be wrong, but I'm quite confident the idea works.
Edit: The indexing was wrong. Apparently in China x means the y-coordinate and vice versa (???). Accepted submission: 55268841
Nice job！The problems are so hard, and I just guess a conclusion when I solving the C2.(since if there is not a conclusion like that, I think I have no solution to run a code below the time limits).Wish to not fail in the system test.
dishonest guys:
div2C:
55261994 I_love_HellHoleStudios (link to reformatted code: link)
55261355 Zzzyt
Nice, neat and tidy problem set, although I will lose a lot of rating because I spent a lot of time debugging Div1.A and C1 and failed to rush C2.
Maybe it'd be better if the duration of contest is longer, e.g. 2.5h or 3h?
I felt the same. It would have been great if it was a 3-hour contest. Missed to submit my solution for Div2D by 2 minutes.
How to solve Div1C?
I tried iterating the steps; during one step...
$$$E(i) = \frac{w_i}{\Sigma w_i} \times (w_i + a_i) + (1 - \frac{w_i}{\Sigma w_i}) \times w_i$$$
... and then I use the expected values as the new weights, but this doesn't seem to work (fails on the 3rd example).
Can anyone explain why this doesn't work and what the proper solution is?
If I pass the system test, the most important observation is that everything is "similar" if you split a picture of weight $$$w$$$ to $$$w$$$ pictures of weight $$$1$$$, or merge two pictures of weight $$$a$$$ and $$$b$$$ to one of weight $$$a + b$$$. Then you may see that the expected weight of a picture is proportional to its initial weight (If you consider only liked or disliked pictures).
Now you should solve the problem where there is only one disliked and one liked picture (whose weight equal to the sum of weight of all pictures of its kind).
Why does this work — why is the "expected weight of a picture is proportional to its initial weight (If you consider only liked or disliked pictures)" but why does the solution described by mouse_wireless (which relies on proportionality in a different way) not work? I can't figure it out.
Think of a picture of weight $$$w$$$ as $$$w$$$ pictures of weight $$$1$$$.
Why does multiplying the expected total weight of liked pictures by w[i] / (initial total weight of liked pictures) (assuming ith picture is liked) give the expected weight of ith picture?
EDIT: Never mind, got it from the editorial.
mouse_wireless Did you figure what's wrong with your solution ?
Why can't we use expected weights of $$$m-1$$$ operations to compute new weights?
I felt q(D) easier than q(C) Div 2. Is there anyone else ?
What is the proof of D's solution
+1. Infact from last 3-4 contest I am finding B to be difficult than C and D that's why I started today with D.
Same here. I took around 1+ hour for solving+debugging div2c. When i saw div2D, I solved it in around 20-25 minutes, missed to submit the solution for just 2 minutes :/
I realize that giving a problem in two easy and hard versions in Codeforces is weird. In IOI-style contests, solving the whole problem gives you advantages over solving each subtask separately, as it saves lots of time to implement subtasks' solutions. However, in Codeforces, even if you can solve the harder one, you should solve and implement the easier version. In this contest, solving C1 quickly gives you lots of points in compare to submitting both C1 and C2 at the same time, when point has dropped dramatically.
On the other side difficulty/points in C2 is ridiculous. It is only more than 250 points compare with A.
Hmmm. It is not that ridiculous. You should consider the value of the problem C2 1500, not 750; as implementing the solution for problem C2 gives you both points of problem C1 and C2. This is the reason why in IOI-style contests, harder subtasks do not always worth more points than easier ones. But again, it supports my point that subtasks are only suitable for IOI-style contests, not Codeforces rounds.
C1 is easy. I don't consider C2 worths 1500. Assuming D is 1500 and have the same difficulty and you will solve only one of two. C1 + D > C1 + C2. Dividing subtasks decreases the price of the problem.
Just found this explanation "Nauuo is very naughty so she didn't give you any hint of the third example." ;)
can anybody explain Div2 B, pls
There are various answers possible. First, find $$$m=n/2+1$$$ (the order of the matrix). Then print the indices of the first row. Then print the indices of the last column (remember not to print the last element of the first row again).
So you can prove that if we sort n chess pieces based on their rows index, the chess piece i will occupies the diagonal from (1, i) — (i, 1). So there is 2*m-1 diagonals and n <= 2*m-1. Construct the answer is placing the chess piece accordingly in the each diagonal
thanks
I think I figured out the solution for D (though couldn't solve it during the contest). The answer is $$$n*$$$$$$(product$$$ $$$of$$$ $$$the$$$ $$$degree$$$ $$$of$$$ $$$all$$$ $$$nodes)$$$. But I can't prove it. Can someone please explain?
Read the comments above maybe?
You just forgot the factorial on each degree, but it's that. See my comment above for an explanation http://codeforces.me/blog/entry/67446?#comment-516861
Yes, I saw your comment. I should have waited a bit more for your comment. Thanks!
Wow!My solution ran 3884ms on the problem C2!And I have just passed it!It's so exciting for me to look at the status for 1h. It just reminds me to be careful next time when I notice my pretest using time nearly to the time limits.
Spent 40 minutes debugging div1A and got WA/RE for 3 times because of my stupidness, then found out that B and C1 were a piece of cake, and at that time their points had dropped quite a lot ...
R.I.P. my rating.
Maybe I should get my brain updated.
same here but in div2 I thought C won't be that hard spent 30 minutes thinking then I started to see there's a missing point in my solution then went to B but my brain got it slowly
I made really bad decisions I will take a break from contests until I finish exams
Is $$$O((n+m)\cdot \log^2 (n))$$$ time and $$$O(n \cdot \log (n))$$$ memory intended in E?
$$$O(n\log n)$$$ in time and $$$O(n)$$$ in memory. I thought you asked F, sorry for that.
Don’t you think that the limits are a little too big? I’ve implemented it and it’s get TLE (OK, it can be squeezed) and is close to MLE (which is worse). 55268190
another mathforces round
You wanna say structforces?
Now I know my brain is made of rubbish.
Your solution 55245407 for the problem 1173A significantly coincides with solutions Roniee1612/55245407, wjk00/55247411. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.me/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked.
I got this message from the system after the coding contest. I just want to make it clear that there may be some coincidence for this problem
can anyone plz explain how to solve c in simple words
For Div2 C:
For each element, find the required number of moves to put it in place. Then, for each element, find the required number of moves to put it in place after moving it the maximum required times from the previous iteration. Keep going until this maximum number doesn't change. That's the answer.
Can anyone share the solution of div2C?
I don't know if it is correct or not — Find time instant t[i] when card i can be available in hand. Now put 1 in pile at time max(t[i]-i+1) and continue putting consecutive numbers each after each.
http://codeforces.me/blog/entry/67446?#comment-516890
why this is getting TLE I can't understand
v.erase(v.begin()) is making the TLE ? removing first element in vector is O(1) right ?
Erasing from the end is constant time. Removing the first element is O(n). (Where n is the length of the vector)
In div2 C when will ans be 2*n. my test case 12 is showing runtime error and in test case 12 answer is coming 2*n
when $$$b_n=1$$$
can u give a short example of it?? as it is not always possible when bn=1.
ohh!! i got it thanx for the help man!!
Can anyone please explain Div2-B that why the number of columns is (n+2)/2 ??
Consider needing to place n pieces. This means that our board must be big enough to have a distance of n between the first and last piece. Looking at a board, this means (WLOG) the top left and bottom right corners must be n squares away. In a board of size m, the top left and bottom right corners are (m-1) + (m-1) = 2*m -2 away from each other (m-1 to get to top right, m-1 to get to bottom right). So, we need that 2*m -2 >= n, which means we need m >= (n+2)/2. Since C++ rounds down, we can just set m = (n+2)/2 to guarantee m >= (n+2)/2.
Great explanation
Thank you so much sir
For number B Div 2, the case when n is equal to 1, is it feasible from the statement that the position of the piece will be at (1,1)? Because, if we say |i-j| == 1, not considering the fact that there is only one piece, and then the left hand side of the equation in the statement becomes 1+1 = 2 which is not greater than or equal to 1. So why have this case? Why not set the constraints from 2?
When comparing the same piece to itself, both the left and right side of the equation would be 0.
So, it will be subtracting 1 from 1 and not nothing from 1? And any reason as to why it will be like that? When I solved it, I had just put in a statement like if n is equal to 1 then print 1, (1,1). It was sort of an intuition and I didn't get to this by reading the statement.
"for all pairs of pieces i and j" means the condition needs to be satisfied only if there exists a pair of pieces.
In Div2D / Div1B: What is the use of the arrangement being a circle when the positions are marked. I feel it's same as permuting 1 to n vertices over a straight line when edges can pass only above the line.
I came up with a unproven, long shot approach for C2. Basically, I calculated the expected value for $$$w_i$$$ after each step, and treated the result as the new initial weight. In other words I did the following $$$m$$$ times:
However, my maths aren't strong enough to understand why it doesn't work. I'm very curious though, because it sounds so intuitive. If someone could give me some clarity as to why it's wrong, I'd be grateful.