### HolkinPV's blog

By HolkinPV, 6 years ago, translation, ,

Hello everybody)

Today is coming regular Codeforces round #163 for Div.2 participants. Traditionally the others can take part out of the competition.

The problems were prepared by authors: Rakhov Artem (RAD), Kudryashov Igor (KudryashovIA), Pavel Kholkin (HolkinPV) and Gerald Agapov (Gerald). Traditionally thanks to Michael Mirzayanov (MikeMirzayanov) for Codeforces system and Mary Belova (Delinur) for translating the problems.

UPD: It is decided to use dynamic scoring system. The problems will be sorted from low difficulty to high by authors' opinion.

We wish everyone good luck and high rating)

UPD2: the contest is over, hope you enjoy it)

Congratulations to winners:

1) Aharon

4) Imsbuno

5) Conny

UPD3: the editorial can be found here)

• +143

 » 6 years ago, # | ← Rev. 2 →   -15 Im first, so i need most of neg votes.
•  » » 6 years ago, # ^ | ← Rev. 3 →   -8 ; ): )
 » 6 years ago, # |   -10 score distribution ? && negative votes please :P
 » 6 years ago, # |   0 last CF round of this month :(
•  » » 6 years ago, # ^ |   0 I wouldn't be so sure:)
•  » » » 6 years ago, # ^ |   +4 Considering Petrozavodsk training camp will start shortly — quite probable
•  » » 6 years ago, # ^ |   0 Check this : http://codeforces.com/blog/entry/6483
•  » » » 6 years ago, # ^ |   0 He said that CF round, rather than gym.
 » 6 years ago, # |   -11 I wish everyone good luck and high rating too! ;)
•  » » 6 years ago, # ^ |   -8 u will surely get some positive votes for this :P
 » 6 years ago, # | ← Rev. 3 →   -13 everyone's waiting for score distribution. wish well for all participants.
 » 6 years ago, # |   -10 what do you mean by dynamic scoring system??
•  » » 6 years ago, # ^ | ← Rev. 2 →   +9
•  » » » 6 years ago, # ^ |   -8 Its like asusual.. am right??
•  » » » » 6 years ago, # ^ |   0 No, usually max. problem scores is static.
•  » » 6 years ago, # ^ | ← Rev. 2 →   +3 Points depend on number of solvers.
 » 6 years ago, # |   0 good luck evryone! :)
 » 6 years ago, # |   -11 Ithink some of people from countries expect iran doesnt like iranian people:( becausa they give all iranian people negetive mark!
•  » » 6 years ago, # ^ |   0 Don'be so nationalistic-thinking! first of all, that's international community. Secondly, there's no flags around your ava — that's is not the main question! :)
 » 6 years ago, # |   0 almost 2800 Registered participants (including ones who are not in the competition). I think this round is the one having the highest number of participants (counting people registered before contests only). anyway good luck
•  » » 6 years ago, # ^ |   0 Does that include people who are from Division 1?
•  » » » 6 years ago, # ^ |   0 it is based on number of Registered participants, so including division 1 people (but they are out of competition)
•  » » 6 years ago, # ^ |   0 i just count for div 2 contests only, excluding rounds with div 1.
 » 6 years ago, # |   +7 it was a awful contest x(
•  » » 6 years ago, # ^ |   0 always pessimistic, aren't you? :)
 » 6 years ago, # | ← Rev. 3 →   -11 nic contest
 » 6 years ago, # |   -11 Worst contest ever,Top 30+ solved only A, Band guess what?! from top 30+ down to the last ranked contestant, all have solved A, B only!
•  » » 6 years ago, # ^ |   +1 i think problems are very interesting, but hard.
•  » » 6 years ago, # ^ |   +35 It is not the worst contest ever! It just too hard to Div2, but problems were realy interesing.
•  » » » 6 years ago, # ^ |   +4 So when the first two problems are fucking easy and the rest three focking hard is normal?:D
•  » » » 6 years ago, # ^ |   +2 I think too. Its not worst, but for most of Div 2 participants not interesting, because they compete only in speed of coding.
•  » » » 6 years ago, # ^ |   0 No it was too easy, but I agree with you, because it was very interesting
•  » » » 6 years ago, # ^ | ← Rev. 4 →   +3 It is not the worst contest ever! It just too hard`Looks like the very definition of the worst contest (ok, ok, not worst ever, just very bad)
 » 6 years ago, # |   0 Why am I unable to see the pretest values in which my submissions failed? Did i miss something in the newsfeed?
•  » » 6 years ago, # ^ |   0 Because the contest is still running
•  » » » 6 years ago, # ^ |   +1 In the last contest I was in, I could see the test cases for which my code fails even while the contest was running.
•  » » » » 6 years ago, # ^ |   0 Maybe it was practice, not contest?
•  » » 6 years ago, # ^ |   0 Its only after contest ends!
•  » » 6 years ago, # ^ |   0 Previously, in each submission, I could see where my code failed and for what test values. That feature seems to be unavailable now. Am I correct?
•  » » » 6 years ago, # ^ |   0 no... you are allowded to see test values after the contest
•  » » 6 years ago, # ^ |   0 It is always unable to see pretest values except tests from the problem during the contest.
•  » » » 6 years ago, # ^ |   +1 Seems my memory has failed me. Thank you guys for clarifying.
 » 6 years ago, # |   0 2200 participants during the contest with 0 Successful hacking attempt,system testing will be so fast :)
•  » » 6 years ago, # ^ |   +4 I saw one around 5th page in standings (althrough that was from Div 1 coder)
 » 6 years ago, # |   +10 Congratulations for the contest, the difference between place 1300 and place 100 is less than a 100 points.
 » 6 years ago, # |   +10 A-B-E-E-E...
•  » » 6 years ago, # ^ |   +4 I think that hardest problem was div1 E level.
•  » » » 6 years ago, # ^ |   +15 Not really. Quite straightforward interval tree, but requires some coding. Good for Div 1 D
•  » » » » 6 years ago, # ^ |   +3 I don't know how can we multiplicate all numbers by (i-l+1)^k quickly. That numbers are distinct and they are not some good sequence, as for me.
•  » » » » » 6 years ago, # ^ | ← Rev. 3 →   +8 Actually if we calculate for all j up to k, we can then calculate required sum
•  » » » » » » 6 years ago, # ^ |   0 Would you please explain this problem in more detail?? Thanks!
•  » » » » » » » 6 years ago, # ^ | ← Rev. 2 →   +1 Let , and . Then (you can do calculations yourself)
•  » » » » » » » » 6 years ago, # ^ |   0 Thanks very much!
•  » » » 6 years ago, # ^ |   +14 I think C, D, E have the correct letters assigned, but for Div 1.
 » 6 years ago, # |   +2 Can anyone tell the algorithm for D? Be free to answer in English as well as in Russian
•  » » 6 years ago, # ^ |   0 Интересует тот же вопрос. Вначале я просчитывал путь от каждой вершины до каждой Флойдом, затем пытался расположить кафе на всех дорогах наилучшим способом. Сначала тернарником. Работал медленно + ВА10. Потом написал вычисления наилучшего способа вручную. ВА9
•  » » » 6 years ago, # ^ |   +10 Тернарник не работает, потому, что функция не выпукла. Там получается кусочно-линейная функция (зубчатая). Я думаю, что мое решение достаточно понятно для чтения
•  » » » » 6 years ago, # ^ |   +4 Ясно, спасибо
 » 6 years ago, # |   0 Traditionally authors wish Successful Hacks .. Is this the first round I am seeing with no successful hacks ??Hats off to the author for problem C. Looks so interesting and yet is so difficult to think.
 » 6 years ago, # | ← Rev. 2 →   0 The questions were excellent.At first I thought that problem D is easy but then saw the line "I can place anywhere on the road" which makes it tough. Anyways, How did you solve problem C and problem D in DIV2
 » 6 years ago, # |   0 Why so hard?
 » 6 years ago, # |   +5 Unexpected difficulty level was unexpected.
•  » » 6 years ago, # ^ |   +3 yeah! from rank 200 to 2000, all of them solved 2 problems and they have been sorted by their typing speed!
•  » » » 6 years ago, # ^ |   0 and reading speed!
 » 6 years ago, # |   0 actually in problem C we just need to sort all rows as increasing amount of 1's and sort the columns as increasing amount of 1's note that sorting columns won't change any thing in rows and vise versaso we don't need more than 2000 move
•  » » 6 years ago, # ^ |   0 I missed a really important constraint no of cells having ones are no more than n — 1. :(
•  » » 6 years ago, # ^ |   0 Sigh, I missed the second part...
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 Actually you can not sort in O(n) time , you have to also tell the positions which were swapped. For the second part , you can sort by any trivial algorithm for sorting in O(n*n). Note that I was missing one important thing , No of ones in columns won't change if I swap the rows. So I can just count no of ones in columns also and do the same thing as done to rows.
•  » » 6 years ago, # ^ |   +1 i think we don't need more than n-1 moves.
•  » » » 6 years ago, # ^ |   0 do not be so accurate!I only wanted to show that sorting won't exceed the limit 10^5
•  » » 6 years ago, # ^ | ← Rev. 3 →   0 00000 00010 00100 01000 10000 it has been sorted, but it's not a correct answer.
•  » » » 6 years ago, # ^ |   +3 You have to take care of equal case , If equal then do the sort lexicographically decreasing.
 » 6 years ago, # |   +7 Why ternary search is incorrect in D?
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 Read above Egor's comment
•  » » 6 years ago, # ^ |   +5 Because function within edge is not convex. It is segment-linear, with segments alternating y = x + b and y = -x + b
•  » » » 6 years ago, # ^ |   0 Please explain the second part y = x + b and y = -x + b ??
•  » » » » 6 years ago, # ^ |   +11 Function for each edge is segment-linear (i. e. edge can be divided into segments, and on each segment function would be linear). Generally linear function is y = kx + b, but in this case k is always either 1 or -1, and this values alternate throught edge
 » 6 years ago, # |   +25 I think these div2-only contests are not really for div2 participants, only. I mean, they're more likely generic ICPC contests, with very easy problems and very hard problems. The final scoreboard today clearly shows that problems C,D and E are not equivalent to div1-A,B and C, as they usually are in regular, div1&2, 7-problems contest. For instance, problem D, that should be equivalent to a div1-B, was solved by 8 coders only — 6 of them were div1, out-of-competition ones. Although we know most div1 coders don't register for div2-only contests, we won't see only 6 coders solving problem B in a regular contest. So I think these div2-only contests are not really equivalent to div2 regular contests. Should they be?
 » 6 years ago, # | ← Rev. 3 →   +1 edited
•  » » 6 years ago, # ^ |   0 Yupp exactly same :P
 » 6 years ago, # |   +3
•  » » 6 years ago, # ^ | ← Rev. 3 →   0 Indentation spaces are not same :P
•  » » 6 years ago, # ^ | ← Rev. 2 →   +5 Nop, there is not the same count of '\t' on the two codes ;) Edit: too late :/
•  » » 6 years ago, # ^ |   0 Anyway they are both submitted 'out of competition' :)
 » 6 years ago, # |   +3 请使用英语。
•  » » 6 years ago, # ^ |   +6 He just asks to use english! Why so many negative??? Whats wrong with you, guys??
•  » » » 6 years ago, # ^ |   +7 ^ ^ Thx.I just comment for fun.
•  » » » » 6 years ago, # ^ |   +21 ჰე ჰეი მეც მიყვარს ეგეთები :დ
•  » » » » » 6 years ago, # ^ |   +9 не надо ничего взрывать
•  » » » » » » 6 years ago, # ^ |   0 Эта шутка совсем не смешна.
•  » » » » » » 6 years ago, # ^ |   +7 No, you are not allowed to drink vodka here!
•  » » » » » » » 6 years ago, # ^ |   +13 Нет, здесь нефти нет.
•  » » 6 years ago, # ^ |   0
 » 6 years ago, # | ← Rev. 2 →   +1 How long does it usually take for ratings to update?It's a matter of high blood sugar, or rather it's gonna be.
 » 6 years ago, # |   +7 I think this contest is really a coding speed test for div 2 participants. I finished the first two problems less than 10 minutes. After that, I read the description of problem E. At the first glance, I thought it had something to do with segment tree. However, right after looking at the sigma notation, I just gave up. I played 2 games of League of Legends. And surprisingly my rating still increased after the contest.
•  » » 6 years ago, # ^ |   +12 And i played 2 games of Dota :D
 » 6 years ago, # |   0 Could anyone tells me, why dis the problem D can not use Ternary Search Algorithm ? I alawys get wrong answer on test 36 ! Many thanks ! this is my
•  » » 6 years ago, # ^ |   0 my code links : http://codeforces.com/contest/266/submission/2993280
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 You should read egor's comment.
•  » » » 6 years ago, # ^ | ← Rev. 6 →   0 One question: when is the overall complexity of the solution ( enough to pass )?
•  » » 6 years ago, # ^ |   +3 You should divide each edge into several segments, and use ternary search on every segment. Just like what Egor have mentioned above. And you can also see more details in my submission. 2995464
•  » » » 6 years ago, # ^ |   +8 No need for ternary search, actually
•  » » » » 6 years ago, # ^ |   +3 Yes, you are right. I found the function within each segment is unimodal, so I used ternary search to find extreme points, but I did not realize that it is possible to get extreme values by direct calculation. Thank you so much. I will correct my solution.
 » 6 years ago, # |   0 There is a grammar mistake in problem C. Some cells (n - 1 cells in total) of the the matrix are filled with ones, the remaining cells are filled with zeros. We can apply the following operations to the matrix:
 » 6 years ago, # |   0 please give me some hint about problem D ?
 » 13 months ago, # |   0 In problem statement B: Queue at the School, can anyone tell the constraint of 'n'
•  » » 13 months ago, # ^ |   0 Not required anymore :P