### HolkinPV's blog

By HolkinPV, 7 years ago, translation, ,

Welcome, friends)

We are glad to introduce you regular Codeforces round #123 for Div.2 participants. Everyone can traditionally participate in it.

Problems are prepared by command of authors: Ivan Fefer (Fefer_Ivan), Igor Kudryashov (KudryashovIA), Pavel Kholkin (HolkinPV) and Gerald Agapov (Gerald). Also thanks to Pavel Kunyavskiy (kuniavski) and Alexander Kouprin (Alex_KPR) for their help. And traditionally thanks to Michael Mirzayanov (MikeMirzayanov) for Codeforces system and Mary Belova (Delinur) for translating problems.

Score distribution is standard: 500, 1000, 1500, 2000, 2500.

We wish you success and high rating!

Congratulations to winners:

UPD: the tutorial is here

•
• +64
•

 » 7 years ago, # |   -56 I am students.
 » 7 years ago, # |   -6 Good luck to all. :-)
 » 7 years ago, # |   +5 I hate problem C.......
•  » » 7 years ago, # ^ |   +5 I hate string parsing. Problem C is just colateral damage :)
•  » » » 7 years ago, # ^ | ← Rev. 2 →   +1 Seen at the last moment that the string can have '\t' in, and no time for correct it... Those kind of problem is not bad, because it teachs you to prevent all possible cases, but it's often very frustrating...
•  » » » » 7 years ago, # ^ |   +1 really frustrating... i used regular expression. i knew little about it before
•  » » » » 7 years ago, # ^ | ← Rev. 2 →   +1 I used %[\n )] in scanf to match the keyword. Forget \t should be my error :(
•  » » » » » 7 years ago, # ^ | ← Rev. 2 →   0 %*[^A-Za-z]%[A-Za-z]%*[^"]"%[^"]%*[^\n]\n
•  » » » » 7 years ago, # ^ | ← Rev. 2 →   0 Test does not contain '\t' symbols as I know. Only ' '.
•  » » » » » 7 years ago, # ^ |   0 That frustating moment when you come back to the point where you dont know wtf is the error.
 » 7 years ago, # |   0 Will n log n time out in problem D? Mine nlog n timed out. Is there any o(n)?
•  » » 7 years ago, # ^ | ← Rev. 2 →   0 nevermind
•  » » » 7 years ago, # ^ |   0 It was nlog n for sorting and then o(n) for counting non zero diff slopes.
•  » » 7 years ago, # ^ |   -6 Yes, they was o(n), you should find all X where line intersect OX axis, number of unique point — it's a answer)
 » 7 years ago, # |   +10 Problem B. You should mention that if m is 6, for example, (m + 1) / 2 equals 3 or 3.5.
•  » » 7 years ago, # ^ |   0 3.5
•  » » 7 years ago, # ^ |   -6 children in first grade are told what symbols '/' means
•  » » » 7 years ago, # ^ |   0 It's ambiguous as to programming languages.
•  » » » » 7 years ago, # ^ |   +5 the problem statement was in English language, not a programming one
•  » » 7 years ago, # ^ | ← Rev. 7 →   +1 Couldn't you ask it?
•  » » 7 years ago, # ^ |   +2 Problems are written in English language, not C++ : )Usually, . But .
•  » » » 7 years ago, # ^ |   0 Well. I see. Thx ;)
•  » » 7 years ago, # ^ |   0 It doesn't really matter because even if you use integer division, you still take the basket with the lower number in case of a tie.
•  » » » 7 years ago, # ^ |   0 Counterexample: if M=4, mid=2.0, the order of baskets is: 2, 1, 3, 4 if M=4, mid=2.5, the order of baskets is: 2, 3, 1, 4
•  » » » » 7 years ago, # ^ |   0 Oops. You're right. Anyway, I used integer division, so I guess that was the intended meaning. Is there any other explanation why it worked? I can't find any.
•  » » » » » 7 years ago, # ^ |   0 You may have interpreted it as integer division, but your code skips the issue entirely by multiplying out both sides:abs((M + 1) - 2 * a.second)
•  » » » » » » 7 years ago, # ^ |   0 Oh yeah, I totally forgot. At first, I wrote it abs((M + 1) / 2 — a.second) and then changed it. I had a bug, but then I realized that it was something else. It turns out that I was pretty lucky because I just tried it with the division and it fails "2 6". So we have our answer :)
 » 7 years ago, # |   0 Problem B overcomplicated the problem a bit by defining the middle as the mathematical middle, rather than just the middle basket. It makes more sense that "Valeric" chose the basket the closest to the middle element, rather than the one closest to the "mathematical middle".
 » 7 years ago, # |   0 In problem C I used Scanner and it not even passed the first test case..Then I used BufferedReader and it got accepted..Could anyone explain why?? Scanner BufferedReader
•  » » 7 years ago, # ^ |   0 I could be wrong, but you should use nextLine() for entire lines.
•  » » » 7 years ago, # ^ | ← Rev. 3 →   0 But I changed the Delimiter to "\n" ..So it is the same I guess..
•  » » » » 7 years ago, # ^ | ← Rev. 2 →   0 nextLine() reads characters until the end of a line, so after reading the first integer in the first line, you should put an extra nextLine(). Then a "carret" will be moved to the next line and you can read an input as expected. Otherwise the last line will be skipped. Here is the corrected solution that passes: 1781961
•  » » » » » 7 years ago, # ^ |   0 Can u please make it more clear for a dumb head like me.. I made a similar mistake on 1 more problem and I want to rectify it now ..plz..
 » 7 years ago, # |   0 Problem E,I can't understand "angle"...what is that?It means parallel to the X axis ?
•  » » 7 years ago, # ^ |   0 Angles are places where polyline has fracture.
•  » » » 7 years ago, # ^ |   0 But the fracture maybe discontinuous?
•  » » » 7 years ago, # ^ |   0 Oh! I get it,It must be continuous,thank you very much~~
 » 7 years ago, # |   0 In problem C:The program may have spaces at the beginning of a line, at the end of a line, before and after a bracket, a comma or a quote mark. But I got stuck in cin.getline(s,55,'\n'). I don't know why it reads more lines than you data gives.
•  » » 7 years ago, # ^ | ← Rev. 4 →   0 The second t.cha[len] = '\0'; should be t.msg[len] = '\0'; Oh, and maybe you should consider putting a cin.getline(s,55,'\n'); instead of getchar() after reading n too just to be safe.
 » 7 years ago, # |   0 For problem A, I was looking at bmerry's solution but I don't understand why the formula he used is: down_time = (c*a + b - 1) / bA lot of solutions I studied use this formula or some variation. I was trying to solve the problem using some kind of simulation but was unable to, but everybody's I've looked at uses some kind of formula.The other thing he does is subtract c from downTime, and the answer is max of 0 or that difference.Can someone explain how to come up with this formula? Thank you.
•  » » 7 years ago, # ^ |   0 I simulated problem A. You can take a look at my code here
•  » » 7 years ago, # ^ |   0 brute force solution here
•  » » 7 years ago, # ^ | ← Rev. 7 →   +5 What I'll tell is effectively the same solution.If b ≥ a, then we can wait 0 seconds and still there will be no delays in the streaming.Suppose that b < a. Consider the moment when the streaming has finished. By problem statement we must have (t + c)b ≥ ca (the amount of data received in t + c seconds is not less that the amount of data in c seconds of the video).Lemma: If (t + c)b = tb + cb ≥ ca, then also for any 0 ≤ t0 < c it holds that tb + t0b ≥ t0a (the amount of data received in t + t0 seconds is enough to play t0 seconds of the video).Proof: tb + cb ≥ ca tb ≥ ca - cb tb ≥ c(a - b) ≥ t0(a - b) tb + t0b ≥ t0a, because $0 \geq t_{0} < c$ and b < a.Consequently, we only need to find such t that tb + cb ≥ ca is true, and the rest will follow. The smallest integer t that satisfies this inequality is Finally, for integer division that is equal to You can also take $c$ out of the numerator, which gives you bmerry's
 » 7 years ago, # |   +1 Will there be an editorial ?