### Sereja's blog

By Sereja, 6 years ago, translation, ,

Hello everyone!

Codeforces Round #182 will take place on Sunday, May 5th at 19:30 MSK. This is my sixth Codeforces round and I hope not the last.

I'd like to thank Gerald and sdya for helping me to prepare the round. Special thanks to Delinur for translation of all problem statements into English.

I strongly recommend you to read ALL the problems.

Gl & hf ! :)

Because of technical issue the start of the contest was unsuccessful. Sorry about it. The contest will be UNRATED.

Tutorial.

•
• +158
•

 » 6 years ago, # |   -109 求轻虐！！！！！！
•  » » 6 years ago, # ^ |   -43 什么宝宝？
•  » » » 6 years ago, # ^ |   -23 将加:)
 » 6 years ago, # |   -19 Any info. about the score calculating rules? As usual?
 » 6 years ago, # |   -17 I believe this will be a very level of the game!
 » 6 years ago, # |   -15 all your round announcement posts look like the same :D
•  » » 6 years ago, # ^ |   +3 but i think problems are different :)
 » 6 years ago, # |   -11 Can you tell me what about the score ? dynamic or 500-1500-1500-2000-2500 ?
 » 6 years ago, # |   0 Good look to everyone! :)
 » 6 years ago, # |   +33 hope my friends and i can reach blue= =
•  » » 6 years ago, # ^ |   0 yes sir in the next contest.
 » 6 years ago, # | ← Rev. 5 →   +10 It is easter in the ortodoxal world. I hope a wonder happen and everything with the contest will be OK.
 » 6 years ago, # |   0 looks like the contest is delayed 10 minutes
•  » » 6 years ago, # ^ |   0 May be system is experiencing some load. Request are getting timed out.
 » 6 years ago, # |   +27 hope today's sever will be stable
 » 6 years ago, # | ← Rev. 2 →   -7 Yestody, GCJ, Have your score arrived 22.
 » 6 years ago, # |   +6 Hope Codeforces can fixt it .. the server cant breathe right nw :O
 » 6 years ago, # |   +36 WTF IS THAT?!The contest opened while the server was down and some people managed to get the problem statements!THIS IS COMPLETELY UNFAIR!!
•  » » 6 years ago, # ^ |   0 How you know that ?
•  » » » 6 years ago, # ^ |   +25 One of my friends already sent me the statement for problem AProblem A. Eugeny and Array
•  » » » » 6 years ago, # ^ |   0 That's sad :-/
•  » » » 6 years ago, # ^ |   -13 , Problem A. Eugeny and Array Input le: stdin Output le: stdout Time limit: 2 seconds Memory limit: 256 megabytes Eugeny has array a = a1; a2; : : : ; an, consisting of n integers. Each integer ai equals to -1, or to 1. Also, he has m queries:
•  » » 6 years ago, # ^ |   +15 What the....If this is true, the contest need to be cancelled definitely. Please announce about the situation and stop wasting competitor's time.
•  » » » 6 years ago, # ^ | ← Rev. 2 →   0 ..
 » 6 years ago, # |   +37 Will the contest be rated? At some moment, contest once started.
 » 6 years ago, # |   +10 Are you sure, you want to continue this contest ?
•  » » 6 years ago, # ^ |   0 delay many times
 » 6 years ago, # |   +116 Sereja strongly recommends you to read ALL the problems. I strongly recommend you to open ALL the problems :))
 » 6 years ago, # |   0 its getting late 35 min wasted time yet.
 » 6 years ago, # |   0 No don't worry, take all the time you need. We have nothing else to do.
 » 6 years ago, # |   -9 it's really unbearable !!!!!!!1
•  » » 6 years ago, # ^ |   0 waste a lot of time
•  » » » 6 years ago, # ^ |   0 the contest is not started yet
 » 6 years ago, # |   +6 Contest gonna start today???
 » 6 years ago, # | ← Rev. 2 →   +4
 » 6 years ago, # | ← Rev. 2 →   +184
•  » » 6 years ago, # ^ |   +1 Now I have missed my lunch because of this....
 » 6 years ago, # |   +33 "Oops! This link appears to be broken""502 Bad Gateway""504 Gateway Time-out""Sorry, the server is too busy at the moment. Please try again later."For 15 minutes these were the only problems I could see!
 » 6 years ago, # |   0 Hope system can be fixed as soon as possible. It's hard to not get the request of "502 bad gateway"...
 » 6 years ago, # |   +28 If this round will be unrated, please tell us before the contest end.
 » 6 years ago, # |   0 **Server Problem !!!!** **Bad Gateway** Hope it'll be OK soon... :/
 » 6 years ago, # |   0 Already 00:05 ! (East Asia)
 » 6 years ago, # |   +39
 » 6 years ago, # |   +10 The server problems are getting really annoying!!! at least could someone explain why the server is down lately??
 » 6 years ago, # | ← Rev. 2 →   +46 LOL, they all had the problem statements and the code ready before the contest begins
•  » » 6 years ago, # ^ |   +10 good that the contest is unrated.
 » 6 years ago, # |   -25 As this contest is unrated, I ain't interested anymore to write codes for this one :)
 » 6 years ago, # |   +6 thank you for letting us know that the contest will be unrated.
 » 6 years ago, # |   +9 waiting 35 minutes... and... unrated...
 » 6 years ago, # |   +119 Sorry about the contest start. It was my fault: the main reason is — it was a non-production copy of Codeforces deployed before the contest (some experimental code + experimantal JVM settings + enabled profiler). Somehow the production copy was unable to start because of many requests :( It was started after some time, but it was passed about 0.5 hour and it was a moment of contests was started (so some users were read the problems).The contest is unrated. I'm sorry about it. I hope you will like nice problems by Sereja.===Приношу свои извинения в связи со срывом старта контеста. Это по моей вине, основная причина — был запущен не-production вариант Codeforces (с некоторым экспериментальным кодом + с экспериментальными опциями в JVM + под профайлером). Почему-то production-сборка не смогла сразу запуститься под написком потока запросов :( Когда она была запущена (примерно через полчаса), был момент когда контест был доступен и некоторые из вас уже прочли задачи.Контест будет нерейтинговым. Еще раз приношу извинения. Я надеюсь, вам понравятся красивые задачи от Sereja и вы получите удовольствие от их решения.
•  » » 6 years ago, # ^ | ← Rev. 2 →   +73 ... The author is innocent ... We shouldn't blame on him. ... Sereja, Thanks for your work and problems.PS: I wonder on this particular issue, does Codeforces will pay for the problemset? Does the author will write the Editorial as well as it been rated?
•  » » » 6 years ago, # ^ |   +55 For sure we will pay to the writer.
•  » » » 6 years ago, # ^ |   +40
•  » » » » 6 years ago, # ^ |   -6 AC fun girl lol
 » 6 years ago, # |   0 Problem C, Do the n elements for which we can change the sign needs to be consecutive ?
•  » » 6 years ago, # ^ |   0 No. It's not necessary for n elements to be consecutive!
 » 6 years ago, # | ← Rev. 2 →   +2 Something is definitely wrong with new Python 3 interpreter. Sorry for spoiling before the end of the contest, but anyway it's unrated.So I feel I'm clever enough to make a solution for problem A, but it has TL on test 11. I do some stupid things sometimes so I checked here: http://codeforces.ru/contest/302/status and everyone fails on test #11 (no one solved it using python 3). The problem could be in reading input data, but it's not as big (10**5). Also after direct translating my code to python 2 it was accepted, so I think something has to be repaired here.
•  » » 6 years ago, # ^ |   +7 It is true (at least for me) that CPython 3 is sometimes slower than CPython 2.I wonder if Codeforces could implement support for PyPy?
•  » » » 6 years ago, # ^ |   +6 Python 3 can be slower, but if it fails on this example what will be on examples with bigger inputs? I waited py3 really for a long a time, but in my opinion it's better to disable it in this state.It would be good if admins add PyPy but the problem is that it's implemented, again, only for python 2
•  » » 6 years ago, # ^ |   0 I tried Div2 A and B with Go language but both solutions got TLE in pretests. (my solutions: 3675888, 3676731) I feel more optimization is needed for those new languages.
•  » » » 6 years ago, # ^ |   0 It's strange that solution both in python 3 and Go fail exactly on test #11. I hardly believe they are equally slow.
•  » » » 6 years ago, # ^ |   +9 I tried to run it localy. The result is "time consumed: 2.81 sec". Note, my laptop is much faster than judging machines. It seems IO in Go is a bottleneck.
•  » » » » 6 years ago, # ^ |   0 I also ran it locally and it took 8.1 seconds... looks like the judge was correct and I should use faster IO functions if any. Thank you for pointing it out.
•  » » 6 years ago, # ^ |   +17 Right, Python 3 is slower than Python 2 in many cases. For example, on my laptop (i7, much faster than judging machines) you solutions work (on the test 11): Python 2: 0.65s, Python 3: 2s, Also PyPy works not faster than Python 2: PyPy: 1s. "... so I think something has to be repaired here ..." I believe Python team should "repair" Python 3 to work faster. On the other hand you should know and understand pros and cons of the language.Another conclusion that PyPy is not a silver bullet, this problem shows again that it doesn't work faster than CPython 2.
 » 6 years ago, # |   +14 no need to complain about unrated contest, just practice in this contest, after all, this contest isn't offering any prizethe important thing is you doing well in that kind of contest, and this codeforces round is one thing to do to achieve that, higher rating doesnt mean always win
 » 6 years ago, # |   +8 Div 1 C / Div 2 E Yaroslav and Algorithm is very interesting! Anyway thanks for the great questions by the author!
 » 6 years ago, # | ← Rev. 2 →   +46 What a pity! It was a very interesting problem set. Thanks Sereja
 » 6 years ago, # | ← Rev. 2 →   +25 The problems are so good. Thanks Sereja, sdya and Gerald. What was the 3rd pretest of Problem C!!!???
•  » » 6 years ago, # ^ |   0 I think you understood the task of problem incorrect, read again, sorry for poor English.
•  » » 6 years ago, # ^ | ← Rev. 3 →   +5 comment deleted
•  » » » 6 years ago, # ^ |   +3 2 ≤ n ≤ 100 ;)
•  » » 6 years ago, # ^ |   0 input:31 2 2 2 2output:7
•  » » 6 years ago, # ^ |   0 Did you figure out how the problem works? I'm interpreting the problem as in a single operation you MUST change the sign of n numbers. In pretest 3, however, the solution would require changing the sign of four numbers while n=3, which I thought would be impossible...
•  » » » 6 years ago, # ^ | ← Rev. 2 →   0 It is possible using two operations: -959 -542 -669 -513 160 -959 -542 669 513 -160 959 542 669 513 160 
•  » » » » 6 years ago, # ^ |   0 Oh wow, thanks. Wasn't thinking like that for some reason.
 » 6 years ago, # | ← Rev. 4 →   +2 O(m*n) solutions accepted in problem B Div2. Edit My apologies, i misread the solutions. Is O(n+m) complexity, because they keep the last position found.
•  » » 6 years ago, # ^ |   0 really? if so, not happy about this, as n*m should go up to 10^10 which should make O(m*n) solutions time out by a large margin. O(m*logn) is the way to go
•  » » 6 years ago, # ^ |   0 read the constraints again(It is guaranteed that vi < vi + 1)solutions are O(n+m)
•  » » » 6 years ago, # ^ | ← Rev. 4 →   0 The worst test case is: n = 10^5 m = 10^5 ci = ti = 1 for 1 <= i <= n vi = i for 1 <= i <= m Ops! you are right, i misread solutions... they keep the last position found.
•  » » 6 years ago, # ^ |   0 you might be dont know two pointers :)
•  » » » 6 years ago, # ^ | ← Rev. 2 →   0 Ops! you are right, i misread solutions... they keep the last position found.
 » 6 years ago, # |   0 Thanks for brilliant contest. It could be a great rated contest if CF didn't crash, but as an unrated contest it was outstanding. GL & HF!
 » 6 years ago, # |   0 too slow system test :/I'm waiting to add problems to practice.
 » 6 years ago, # |   +8 Very nice problems!Especially problem C in div1!Thanks to sereja!
 » 6 years ago, # | ← Rev. 4 →   0 Weak test cases for problem B in DIV2O(m*n) solutions pass the system test! m,n <= 10^5 !! Okay I was wrong (It is guaranteed that vi < vi + 1) solutions are O(n+m)
•  » » 6 years ago, # ^ |   +1 show me the code. i think it's O(m+n) solution, not O(m*n), because variable j can not decrease:)
 » 6 years ago, # |   -14
 » 6 years ago, # |   0 trying to figure out div1 problem D. i believe the number of divisors of a number n is no greater than 2*sqrt(n), is there a tighter bound?
•  » » 6 years ago, # ^ |   +15 Look at it as the number of multiples in the range [1,n]. Then you get:n/1 + n/2 + n/3 + ... + n/n
•  » » 6 years ago, # ^ |   +15 Sum of numbers of divisors for numbers not exceeding N is .Also, number of divisors of N is o(Nε) for every ε > 0.
 » 6 years ago, # | ← Rev. 2 →   0
•  » » 6 years ago, # ^ |   0 Absolutely! except for the last thing :D
•  » » » 6 years ago, # ^ |   0 :D I tried to post a picture, but it won't show.
 » 6 years ago, # |   0 Hi there, a quick question.In Div2 D/Div1 B, what should the output of the following test case be? 3 1000 2000 0 0 0 1 0 2 Should it be 1000? Because my program outputs 0 and passed system test. Thanks! :)
•  » » 6 years ago, # ^ |   0 a_i<=1000
•  » » » 6 years ago, # ^ |   0 oh, I missed that one. Thanks, Sereja! I really enjoyed your problems :)
 » 6 years ago, # |   +2 Would you mind returning pagination on the 'Contests' page to its normal state (slightly more than 4 contests per page)?
•  » » 6 years ago, # ^ |   +16 Already
 » 6 years ago, # |   0 So sorry to hear that...:(
 » 6 years ago, # |   0 The third topic what is thinking？
•  » » 6 years ago, # ^ |   0 div2
 » 6 years ago, # |   +5 In the problem "Yaroslav and Time", I define INF as 20000005, and get "pretest passed". However, "wrong answer on case 51" in rejudging. So Sad that INF shall be 2*20000005 or bigger. PS: If dijkstra algorithm is used in this problem, it's okay. But if dp is used, this test case should be concered: 5 1000 1000 1000 1000 0 0 0 1 1 1 2 1 2 0 What I mean is that we shouldn't just apply dp in just (sx,sy) to (ex, ey), but the whole (-100,-100) to (100,100).
 » 6 years ago, # |   0 Can someone tell me solution of problem C div 2
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 The problem tag is dp and math. However, I solve it in a more complicated way — bfs and greedy. First, I use bfs to get all the possible number of multiplying -1. For example, for n = 2, all the possible number are {0,2}. That's to say, I can multiply zero or two numbers in the array by -1. Then, sort the sequence and apply greedy algorithm. If I can make all the numbers positive, then do it. Else I make as more as I can. Be careful of occurrences of 0.
•  » » 6 years ago, # ^ |   +1 Here's another solution:If there are any zeros inside the array, then you can ALWAYS make them all positive.If you have n is an odd number, then you can ALWAYS make them all positive.If you have n is an even number and there is an even number of negatives, then you can ALWAYS make them all positive. Else, you can ALWAYS make all but one of them positive.
•  » » » 6 years ago, # ^ | ← Rev. 2 →   +4 Here is a rigorous proof of the "always"es frznlich said.First, note that if n is odd, we can change any single number. To see this, take the number x that we want to change, and n more numbers a1, a2, ..., an. We do an operation to each of these: (x, a2, a3, ..., an), (x, a1, a3, a4, ..., an), ..., (x, a1, a2, ..., an - 1) -- basically every combination possible that takes x and n - 1 of the ai's. We can see that x belongs to n (an odd number) operations and hence changes sign, while every ai belongs to n - 1 (an even number) operations so doesn't change sign.If n is even, we cannot change a single number: The number of numbers we change is even (some number times n which is even), and two changes equal null, so the parity of number of numbers we change is an invariant. So it will stay even. However, we can change two numbers. If we want to change x, y, take numbers a1, a2, ..., an - 1 and perform the operations (x, a1, a2, ..., an - 1), (y, a1, a2, ..., an - 1).This means we can change all negative numbers to positive except probably one, and this "probably one" only occurs when n is even and there are an odd number of negative numbers.So what we should do is to determine whether the above condition occurs. Besides, we will also find out the sum of the absolute values of the numbers and to figure out the number with the least absolute value, which we will "sacrifice" as the single negative number if there is any.So our approach is this:Loop over all numbers. Compute the number of negative numbers in the input and call it neg, the sum of the absolute values of all numbers sum, and the minimum absolute value of all numbers min. If n is even and neg is odd, output sum - 2min, otherwise output sum.EDIT: Removed double post (phone acts up at times), useless statement to find the largest number, and useless assumption that zero is negative.
•  » » 6 years ago, # ^ |   +8 A solution more suitable to a contest, however, is: notice the bound N <= 100 and do BFS on how many negative numbers there could be, since if you change x negative numbers and N-x positive ones in one step, then there will be N-2x more negative numbers (special case: if there's a zero, it's clear that they can all be made non-negative). You don't need to think about all possible cases, just use a simple algorithm to do that for you.
 » 6 years ago, # |   0 Can someone tell me solution of problem C div 1？ thanks！
•  » » 6 years ago, # ^ |   0 One approach is this (works for any number): Place ? after the first occurrence of the smallest digit in the number. Move ? to the end of the number. If the last digit of the number is 0..8, increase it, remove ? and stop. Otherwise replace ? with ??. So long as the digit before ?? is 9, replace it with 0 and move ?? one step left. If there is another digit before ??, increase it, remove ?? and stop. If there is no digit before ??, replace it with 1 and stop. For example, the number 6299:6299, 62?99, 629?9, 6299?, 6299??, 629??0, 62??00, 6300
•  » » » 6 years ago, # ^ |   0 very tanks!
•  » » 6 years ago, # ^ |   +6 Just output the following: ??0>>0?? ??1>>1?? ??2>>2?? ??3>>3?? ??4>>4?? ??5>>5?? ??6>>6?? ??7>>7?? ??8>>8?? ??9>>9?? ??>>? 0?<>1 1?<>2 2?<>3 3?<>4 4?<>5 5?<>6 6?<>7 7?<>8 8?<>9 9?>>?0 ?<>1 0>>??0 1>>??1 2>>??2 3>>??3 4>>??4 5>>??5 6>>??6 7>>??7 8>>??8 9>>??9 The above is composed of five parts: End marker movers of 10 commands, end marker converter of 1 command, converter processes of 10 commands, converter finalization of 1 command, and end marker initializations of 10 commands.At first, the string doesn't contain any question mark, so some of the end marker initialization commands (d>>??d) is encountered. There will be some double question mark, called end marker, inserted in the string.Now, some of the end marker mover commands (??d>>d??) will be encountered. This basically moves the end marker one step to the right. As long as this end marker isn't at the end yet, the end marker will be constantly moved, so the end marker will eventually reach the end of the string. At the worst case, the end marker begins in the front of a 25-digit string, taking 25 iterations.Next, the end marker converter (??>>?) is found, and the end marker becomes a converter sign (?). This converter sign's job is to add the digit exactly before it.Next, some of the converter process commands (d?<>d) will be encountered, which changes the digit in front of the converter sign. If it's not 9, the addition will not cause any carry, so we're done. Otherwise, the special 9?>>?0 command is encountered, which marks that we need to carry and so we need to add 1 to the previous (more significant) digit. At the worst case, the converter processes need to go all the way to the front with the number 1025 - 1 = 9999999999999999999999999, which takes 25 iterations.Finally, in the case the converter sign reaches the front of the string, we assume that there is an extra 0 in front of the string, and add 1 to it, hence the special (?<>1) converter finalization command.This takes 32 commands and at most 53 iterations at the worst case, no matter what the actual numbers are. To arrive at this solution, first you need to realize that 100 numbers is too much to handle by investigating the numbers; there must be some testcase that causes any submission based on handling numbers to fail. Too many numbers for too few commands. So there should be some easy solution independent of the numbers.Next you need to figure out that you need to find some way to mark the end of the string (so you can start adding), you need to handle all digits, you need to handle 9s added, and you need to handle 999...9s.The above is mostly trial-and-error after the above realizations.
•  » » » 6 years ago, # ^ |   +9 Instead of last 10 lines you can output ">>??" :)
•  » » » 6 years ago, # ^ |   0 very tanks!
 » 6 years ago, # |   0 Because the contest was unrated, There wouldn't be any editorial for it?
•  » » 6 years ago, # ^ |   +6 There is an editorian on the Russian.
•  » » » 6 years ago, # ^ |   +1 What about English version?
•  » » » 6 years ago, # ^ |   +1 link of that one?
•  » » » 6 years ago, # ^ |   0 Can you paste the link to the editorial?
•  » » » » 6 years ago, # ^ |   0
 » 6 years ago, # | ← Rev. 6 →   0 In problem B div 1, I failed at system test 52. There is some thing special in this testcase I couldn't find out . Can anyone help me? I think every station passed have to be inside the rectangle of point 1 and point n because when going out of the rectangle and returning, it will cost at least 2*d which is larger than any a[i]. However, it is inaccurate in test case 52 when the best route pass through outside points and then come to point n. For some more detailsTest 52: 12 1211 1 5 7 1000 1000 1000 1000 1000 1000 1000 1 1 5 5 3 4 4 3 0 1 0 2 0 5 0 7 1 0 3 0 8 0 10 10 The best way: (1,1) -> (0,1) -> (0,2) -> (0,5) -> (0,7) -> (10,10)
•  » » 6 years ago, # ^ |   -12
•  » » 6 years ago, # ^ |   0 back to 1 (1,1)->(0,1), but get 4 additional bonus (0,1),(0,2),(0,5),(0,7)
•  » » 6 years ago, # ^ | ← Rev. 3 →   +16 I got caught in thinking that too, but it's not true. Consider the following situation: 98 .7 .6 .5 .4 .3 12 where d=1000 and all ai=1000. You should pay 2000 to get out of the rectangle containing 1 and 9, because the gain is 7000.
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 As a rule of thumb, I would stick to not optimizing anything that doesn't need to be optimized during programming contest. You can improve algorithm after contest.