### ouuan's blog

By ouuan, history, 12 days ago, ,

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, Sooke, QAQAutoMaton, ODT, ccz181078, rushcheyo and PinkRabbit.

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.

• +389

 » 12 days ago, # |   +141 Wish everyone have fun!
•  » » 9 days ago, # ^ |   +4 Orz lk
 » 12 days ago, # |   -32 hope short problems and high rating!
•  » » 11 days ago, # ^ |   -25 why !!!
•  » » » 10 days ago, # ^ |   0 you should have said short solutions and high ratings :P
•  » » » 10 days ago, # ^ |   +20 ratism
 » 12 days ago, # |   +85 Friendly time to Chinese！
•  » » 12 days ago, # ^ | ← Rev. 2 →   +92 It's Happy DuanWu Festival match
•  » » » 11 days ago, # ^ |   +19 happy DuanWu Festival to all the Chinese
•  » » 11 days ago, # ^ |   -47 But bad time for people
•  » » » 11 days ago, # ^ |   +30 I think it's good for Chinese people!(After 10 p.m. is too late
•  » » » 11 days ago, # ^ | ← Rev. 2 →   +12 I think this is really a good time for ChineseChinese needn't stay up until midnight QwQWe are able to have a good sleep after this contest qwq
•  » » » » 11 days ago, # ^ |   +19 Not, if you perform badly in this contest.
 » 12 days ago, # |   +5 Time :)
 » 12 days ago, # |   +108 Div1+Div2, Dragon Boat Festival, UTC+8 20:05, Chinese editorial. Si Bei Yi Man!!!
•  » » 10 days ago, # ^ |   +14 what does "Si Bei Yi Man" mean?
•  » » » 10 days ago, # ^ | ← Rev. 2 →   0 Chinese pinyin(phonetic transcription) for "四倍役满"（逃）
 » 12 days ago, # |   +33 Which problem will have two subtasks?
•  » » 11 days ago, # ^ |   -43 C1 and C2
 » 12 days ago, # |   -15 Hope my name to become orange again qwq.
 » 12 days ago, # |   +19
•  » » 12 days ago, # ^ |   +44 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.
•  » » » 11 days ago, # ^ |   +52 qwq
•  » » 11 days ago, # ^ |   -21 You can find this problem very difficult and give it up as soon as possible by the anime pictures.
 » 12 days ago, # |   +41 I hope this round will not be full of hardcore math problems :(
•  » » 12 days ago, # ^ |   +49 I think this round will be full of data stucture problems because of @ODT
•  » » » 11 days ago, # ^ |   +25 orz ynoi
•  » » » » 11 days ago, # ^ |   +12 Orz lxl
 » 12 days ago, # |   -7 Chinese Round! Happy Dragon Boat Festival!
 » 12 days ago, # |   -9 A task that has two versions counts as one task or two?
•  » » 12 days ago, # ^ |   -8 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?)
•  » » » 12 days ago, # ^ |   -8 let there be tasks A1 and A2, will it be like one task or two?
•  » » » » 11 days ago, # ^ | ← Rev. 2 →   -8 Two tasks. For example D1 (easier version) and D2 (harder version). They will be scored separately.
•  » » 12 days ago, # ^ |   +16
 » 12 days ago, # |   +209
•  » » 10 days ago, # ^ |   +23 Welcome back to div3
•  » » » 10 days ago, # ^ |   +9 Short journey in div2
 » 12 days ago, # |   -11 Chinese editorials? Cool!
•  » » 11 days ago, # ^ |   -7 Happy Dragon Boat Festival!
 » 11 days ago, # |   +76
•  » » 11 days ago, # ^ |   +8 it should be updated...
•  » » » 11 days ago, # ^ |   -8 whatever...i dont know much about ps
•  » » » 11 days ago, # ^ |   +5 not "Round 0x233" anymore qaq
•  » » 10 days ago, # ^ |   0 you are good at psing
 » 11 days ago, # |   +31 long live china , I love all Chinese
 » 11 days ago, # |   +23 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!
 » 11 days ago, # |   +9 This round is so friendly for Chinese QwQLet's have fun in this round QwQ
 » 11 days ago, # |   +157 I am ready to face data structure problem !
 » 11 days ago, # |   +13 Wow,that will be so cool to have a such great contest in Dragon Boat Festival! :)
 » 11 days ago, # |   0 Chinese round =earlier time
 » 11 days ago, # |   +4 i hope this contest will make me green and i will not be newbie anymore ... :/
•  » » 11 days ago, # ^ |   +4 Good Luck and remember dont focus on ratings but on learning from the contests and your rating will automatically increase :)
•  » » » 11 days ago, # ^ |   -8 Yes,it is a truth for every oier&acmer
 » 11 days ago, # |   -13 Chinese editorials that cool,but why there is not Chinese problems?
 » 11 days ago, # | ← Rev. 2 →   -14 DuanWu كل عام و انتم بخير بمناسبة حلول عيد الأعاده الله علينا بالبركات Trans :Happy DuanWu Festival
 » 11 days ago, # |   +8 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.
 » 11 days ago, # |   -23 I need an anime-themed contest.We need an anime themed contest.
•  » » 11 days ago, # ^ | ← Rev. 2 →   -25 totally agree with you :D
•  » » » 11 days ago, # ^ | ← Rev. 2 →   -15 Probably a Catholly-themed contest because of ODT
 » 11 days ago, # |   +154 Chinese round again...It's great, but I think maybe I should get ready to face hard data structure.
•  » » 11 days ago, # ^ |   -16 orz rqy, rqy tql ddw.
•  » » » 11 days ago, # ^ |   +76 abc def, ghi jkl mno.
•  » » » » 11 days ago, # ^ |   -24 ABCDEFGKNMLGB
•  » » » » » 11 days ago, # ^ |   -26 zyx wvu, tsr qpo nml
•  » » » » » 11 days ago, # ^ |   -36 wo qi le , yi qiang miao le , you shen me hao shuo de
•  » » » » » » 11 days ago, # ^ |   -6 wdnmd??
•  » » » » » » 10 days ago, # ^ |   0 What did you say?
•  » » 11 days ago, # ^ | ← Rev. 2 →   -26 Well sorry about orz qaq
 » 11 days ago, # |   +108 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: Solve v.1 of the problem Block it Watch other solutions Find solution of guy who have passed v.2 with the same solution in v.1 Copy his solution Send it to v.2
•  » » 11 days ago, # ^ |   +29 no, since it will only be possible to block both of these subtasks.
•  » » 11 days ago, # ^ | ← Rev. 2 →   +46 When a simple and difficult version of the problem is solved, then it will be possible to block the task.
 » 11 days ago, # | ← Rev. 2 →   +15 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!
 » 11 days ago, # |   +18 repeat the math)
 » 11 days ago, # |   0 Could we view the problems in Chinese?
 » 11 days ago, # |   -19 Orz Sooke, QAQAutoMaton, ODT, ccz181078, rushcheyo and PinkRabbit and wish everyone have fun!
 » 11 days ago, # |   -20 Orz LJC00118, Sooke, PinkRabbit, for they AKed IOI! Good luck to everyone!
 » 11 days ago, # | ← Rev. 3 →   0 Well sorry about orz . But that's really a good DW contest .
 » 11 days ago, # |   +8 I hate difficult data structure problems because I can't even write it out.
 » 11 days ago, # |   0 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.
•  » » 11 days ago, # ^ |   +19 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. ;)
•  » » » 11 days ago, # ^ |   +5 Thank you very much!
 » 11 days ago, # |   +31 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! ;)
•  » » 11 days ago, # ^ | ← Rev. 2 →   +22 I always remember you since that comment :) Thank you for your encouragement!
•  » » » 11 days ago, # ^ |   +14 Never thought my comment would leave such a deep impact. :P Too bad I couldn't participate, it's close to my dinner time and I'm shifting my focus to final exams :< but I would virtual soon. ;) Wow, first time I see a mirror of Codeforces. Well, the Great Firewall is strong. :D
•  » » » » 11 days ago, # ^ |   +16 Oh, I use the mirror by mistake again..
 » 11 days ago, # |   0 I am very confused whether to participate in contest or watch Federer vs Nadal.
 » 11 days ago, # |   0 It's time to take back what I've lost!!!!!!!!!!
 » 11 days ago, # |   -8 Chinesse round!!!Yes!!!! but maybe there are many data stucture problems.(maybe there are full of data stucture problems) my rating will down.....
 » 11 days ago, # |   +8 Why is that m1.codeforces.com, m2.codeforces.com and m3.codeforces.com not available these days?
•  » » 11 days ago, # ^ |   0 I can enter m2.
•  » » » 11 days ago, # ^ |   0 For me its showing "Server not found" for all the three.
 » 11 days ago, # | ← Rev. 3 →   0 What's the score for each problem and what problem have to subtasks? QAQautomaton ODT ouuan
 » 11 days ago, # |   +12 why not show us the scoring distribution?
•  » » 11 days ago, # ^ |   +9 I guess the 3 Minute Rule ;p
 » 10 days ago, # |   -11 How should I register? I haven't registered yet and so not able to submit.
 » 10 days ago, # | ← Rev. 2 →   -12 Bruh!
•  » » 10 days ago, # ^ |   -15 Where should I register? I haven't registered yet and so not able to submit.
•  » » » 10 days ago, # ^ |   -8 Maybe u wont be able to submit till the end
•  » » 10 days ago, # ^ |   +12 Please, Stop this fucking repeated thingshttps://codeforces.com/blog/entry/66587?#comment-507367https://codeforces.com/blog/entry/67340?#comment-515473
 » 10 days ago, # |   +15 How to solve div 2 C?
•  » » 10 days ago, # ^ |   +11 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.
•  » » » 10 days ago, # ^ |   0 Binary search the number of zero moves required + number of elements to put in place?
•  » » » » 10 days ago, # ^ |   0 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.
•  » » 10 days ago, # ^ | ← Rev. 6 →   0 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 :(
•  » » » 10 days ago, # ^ |   0 Thanks guys, got it.
•  » » 10 days ago, # ^ |   +15 /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, ...
•  » » 10 days ago, # ^ |   +17 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).
 » 10 days ago, # |   -9 Mathforces...
•  » » 10 days ago, # ^ |   0 I dont understand why people complain about math? Most of programming reduces down to mathematics...
•  » » 10 days ago, # ^ |   -6 What, you wanted ScienceForces? I guess having maths problems is not a problem.
•  » » » 10 days ago, # ^ |   +1 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
•  » » 9 days ago, # ^ |   0 ABC can be worked out on paper, just think about the problem and write it down and the rest is implementation.I complain about mathforces only when I have to use advanced math formulas and tricks that I would have knowledge of only if I was a math olympian or something like that.Some basic math involved into implementation is perfectly fine by me, in fact, it is necessary to produce fun problems.
 » 10 days ago, # | ← Rev. 4 →   +61 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, Ill break my mouse.UPD2: AcceptedUPD3: Mouse RIP
•  » » 10 days ago, # ^ |   +3 Same here for C, I fixed the last bug too late
•  » » 10 days ago, # ^ |   +11 SO, is the mouse broken?
 » 10 days ago, # |   +11 Real Mathforces...though I expected some data structure
 » 10 days ago, # | ← Rev. 2 →   +3 How to solve Div2 c ????UPD : there is my submission https://codeforces.com/contest/1173/submission/55271422
•  » » 10 days ago, # ^ |   +1 Binary search the number of zero moves required + number of elements to put in place. https://ideone.com/WgHMmm
•  » » » 10 days ago, # ^ |   0 What do you mean by binary search number of zeros ?
•  » » » » 10 days ago, # ^ |   +1 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.com/contest/1173/submission/55269800
•  » » » » » 10 days ago, # ^ |   0 Thanks
 » 10 days ago, # |   +14 Found out where i made a mistake on 2C in last 5 secondssubmit"contest is over"R.I.P rating;(
 » 10 days ago, # |   +31 I wasn't able to solve any problem in div1... is the color of my name wrong?
•  » » 10 days ago, # ^ |   +28 don't worry, just pretend you didn't participate, your rank will not drop anyway
 » 10 days ago, # |   +66 but it was nice problem really close from solving it :(
•  » » 10 days ago, # ^ |   0 same here.
•  » » 10 days ago, # ^ |   0 Funny how they switched B with C this time.
•  » » » 10 days ago, # ^ |   0 I thought so too at first But once I came back to solve B, god I felt so dumb to go after C first
 » 10 days ago, # |   +11 How to solve div2D?
•  » » 10 days ago, # ^ |   0 Passed pretest with this — Root the tree. Fix first position as root. Each subtree will occur consecutive in circle. Then rotate the circle.
•  » » 10 days ago, # ^ |   +21 $n \cdot \prod_{i=1}^n deg(i)!$
•  » » » 10 days ago, # ^ |   +3 proof?
•  » » » » 10 days ago, # ^ | ← Rev. 3 →   +28 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.
•  » » » 10 days ago, # ^ |   +3 Could you please explain how this works?
 » 10 days ago, # | ← Rev. 3 →   +28 We're so sorry. We tried to hack the $\mathcal O(n\sqrt{n\log n})$ solution for 1F, but hacked stO'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..
•  » » 10 days ago, # ^ |   +24 Why sorry?
•  » » » 10 days ago, # ^ | ← Rev. 2 →   +21 Because his solution is correct with big constant.upd: It seemed that I'm wrong.. He said his solution is not in correct complexity..
 » 10 days ago, # |   +9 The fact that if this round was combined it wouldn't make any difference XD
 » 10 days ago, # |   +3 When will we see the problem rating? After the system test done?
•  » » 10 days ago, # ^ |   +6 In 1-2 days
 » 10 days ago, # | ← Rev. 2 →   +19 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 :/ solution to DAlways 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 #include #include #include using namespace std; using ll = long long; const ll MOD = 1e9 + 7; int main() { ios_base::sync_with_stdio(false); cin.tie(0); int n; cin >> n; vector le(n); for (int i = 0; i < n; ++i) cin >> le[i]; vector up(n); for (int i = 0; i < n; ++i) cin >> up[i]; vector> res; for (int j = 0; j < n; ++j) { int a = j; int b = j; for (; a < n; ++a) { if (le[a] == j+1) break; } for (; b < n; ++b) { if (up[b] == j+1) break; } if (a != j || b != j) { res.push_back({a+1, j+1, j+1, b+1}); swap(le[a], le[j]); swap(up[b], up[j]); } } cout << res.size() << '\n'; for (int i = 0; i < res.size(); ++i) { int x1, y1, x2, y2; tie(x1, y1, x2, y2) = res[i]; cout << x1 << ' ' << y1 << ' ' << x2 << ' ' << y2 << '\n'; } } `
 » 10 days ago, # |   0 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.
 » 10 days ago, # |   +18 dishonest guys:div2C:55261994 I_love_HellHoleStudios (link to reformatted code: link)
•  » » 10 days ago, # ^ |   0 kak ty ih vychislil?
 » 10 days ago, # |   +13 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?
•  » » 10 days ago, # ^ |   0 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.
 » 10 days ago, # | ← Rev. 3 →   +37 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?
•  » » 10 days ago, # ^ |   +81 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).
•  » » » 10 days ago, # ^ | ← Rev. 2 →   +5 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.
•  » » » » 10 days ago, # ^ |   +23 Think of a picture of weight $w$ as $w$ pictures of weight $1$.
•  » » » 10 days ago, # ^ | ← Rev. 2 →   0 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.
 » 10 days ago, # |   +10 I felt q(D) easier than q(C) Div 2. Is there anyone else ?
•  » » 10 days ago, # ^ |   +6 What is the proof of D's solution
•  » » 10 days ago, # ^ | ← Rev. 2 →   +11 +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.
•  » » 10 days ago, # ^ |   +3 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 :/
 » 10 days ago, # |   +75 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.
•  » » 10 days ago, # ^ |   +23 On the other side difficulty/points in C2 is ridiculous. It is only more than 250 points compare with A.
•  » » » 10 days ago, # ^ |   +18 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.
•  » » » 10 days ago, # ^ |   +25 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.
 » 10 days ago, # |   -8 I think i am out of competition.o(╥﹏╥)o
 » 10 days ago, # |   0 Just found this explanation "Nauuo is very naughty so she didn't give you any hint of the third example." ;)
 » 10 days ago, # |   0 can anybody explain Div2 B, pls
•  » » 10 days ago, # ^ |   0 After observing some test case, you can find that for say ith chess at coordinate (xi,yi) we can put it in (xi+1,yi) or (xi,yi+1) and it will satisfy the distance condition for all it's previous chess pieces, now following this you can construct the answer. :-)
•  » » 10 days ago, # ^ |   0 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).
•  » » 10 days ago, # ^ | ← Rev. 3 →   +3 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
•  » » 10 days ago, # ^ |   0 thanks
 » 10 days ago, # |   0 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?
•  » » 10 days ago, # ^ |   0 Read the comments above maybe?
•  » » 10 days ago, # ^ |   +1 You just forgot the factorial on each degree, but it's that. See my comment above for an explanation http://codeforces.com/blog/entry/67446?#comment-516861
•  » » » 10 days ago, # ^ |   0 Yes, I saw your comment. I should have waited a bit more for your comment. Thanks!
 » 10 days ago, # |   +3 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.
 » 10 days ago, # |   0 This was a really good one. Appreciate the writers. For a beginner like me, those problems gave me a lot of insight. :)
 » 10 days ago, # |   +15 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.
•  » » 10 days ago, # ^ |   +3 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
 » 10 days ago, # |   -8 Is $O((n+m)\cdot \log^2 (n))$ time and $O(n \cdot \log (n))$ memory intended in E?
•  » » 10 days ago, # ^ | ← Rev. 2 →   +8 $O(n\log n)$ in time and $O(n)$ in memory. I thought you asked F, sorry for that.
•  » » » 10 days ago, # ^ | ← Rev. 2 →   0 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
 » 10 days ago, # |   -34 another mathforces round
•  » » 10 days ago, # ^ |   +31 You wanna say structforces?
 » 10 days ago, # |   +8 Now I know my brain is made of rubbish.
 » 10 days ago, # |   +9 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.com/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
 » 10 days ago, # |   0 When will the editorials be released?
 » 10 days ago, # |   0 can anyone plz explain how to solve c in simple words
•  » » 10 days ago, # ^ |   0 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.
 » 10 days ago, # |   0 Can anyone share the solution of div2C?
•  » » 10 days ago, # ^ | ← Rev. 3 →   0 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.
•  » » 10 days ago, # ^ |   0
 » 10 days ago, # |   0 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 ?
•  » » 10 days ago, # ^ |   0 Erasing from the end is constant time. Removing the first element is O(n). (Where n is the length of the vector)
 » 10 days ago, # |   0 thanks for the super speedy tutorial !!
 » 10 days ago, # |   0 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
•  » » 10 days ago, # ^ | ← Rev. 2 →   0 when $b_n=1$
•  » » » 10 days ago, # ^ |   0 can u give a short example of it?? as it is not always possible when bn=1.
•  » » » » 10 days ago, # ^ |   0 ohh!! i got it thanx for the help man!!
 » 10 days ago, # |   0 Can anyone please explain Div2-B that why the number of columns is (n+2)/2 ??
•  » » 10 days ago, # ^ | ← Rev. 2 →   0 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.
•  » » » 10 days ago, # ^ |   +7 Great explanationThank you so much sir
 » 10 days ago, # |   0 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?
•  » » 10 days ago, # ^ |   0 When comparing the same piece to itself, both the left and right side of the equation would be 0.
•  » » » 10 days ago, # ^ |   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.
•  » » » » 10 days ago, # ^ |   0 "for all pairs of pieces i and j" means the condition needs to be satisfied only if there exists a pair of pieces.
•  » » » » » 9 days ago, # ^ |   0 Okay, Thanks!
 » 10 days ago, # | ← Rev. 2 →   0 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.
 » 10 days ago, # |   -13 I think the div1E is difficult to write in two hours(Especially for me）Even the standard code is so long……
 » 8 days ago, # |   0 Hey guys, I have made a new app Coding List which keeps you updated with all live, upcoming programming competitions from hackerearth, kaggle, codechef, codeforces, topcoder, aigaming, hackster, codinggame, hackerrank, projecteuler, atcoder and many more.A must have app for programmers. Please rate and review it. Try it here https://play.google.com/store/apps/details?id=io.github.vikasgola.coding_list