### Zlobober's blog

By Zlobober, 6 years ago, translation,

Hi everybody!

Today at 12:00 Moscow Time there will be Codeforces Round #279, dedicated for second division contestants. Round is based on the problems of the Saratov second round of All-Russian School Olympiad in Informatics 2014-2015 that is held at the same time in Saratov.

This round was brought to you by ikar, HolkinPV, IlyaLos, fcspartakm that are all members and ex-members of Saratov SU 2 team.

There will be 6 tasks for 2 hours 30 minutes. Scoring will be announced just before the round starts.

Round will be rated for second divison participants. First division contestants may participate out of competition.

UPD: Scoring: 500-1000-1500-2000-2000-2500.

Good luck!

• +149

 » 6 years ago, # |   +7 ranked!?
•  » » 6 years ago, # ^ |   +18 Don't you like ranked contests? Are you racist?
•  » » » 6 years ago, # ^ |   +8 I actually wanted it to be ranked. Some of them weren't in the recent past .
•  » » » » 6 years ago, # ^ |   +11 Oh, I'm sure your wishes will be taken into account.
 » 6 years ago, # |   +8 waiting! waiting!!! good luck to all participants!
 » 6 years ago, # |   +5 wish high rating
 » 6 years ago, # |   0 When you visit codeforces.comCan you look the message "connecting to fonts.googleapis.com ..." with 10 sec?
•  » » 6 years ago, # ^ |   0 Press X then it will load.
•  » » » 6 years ago, # ^ |   0 The page become blank after press X.
•  » » » » 6 years ago, # ^ |   +1 Try to clear your cookies.
 » 6 years ago, # |   -19 6 problems. Wow!!!!!!!!
 » 6 years ago, # |   -26 10 minuets to start. Why yet not scoring have been published? Waiting for it.
•  » » 6 years ago, # ^ |   -23 Scoring have been published. Best luck to all participants.
•  » » » 6 years ago, # ^ |   -19 For God's sake, why do you down vote? What's wrong with what he said?
•  » » » » 6 years ago, # ^ |   0 Cause he's spamming?
•  » » » » » 6 years ago, # ^ |   +4 I don't think that he's spamming.
 » 6 years ago, # |   +11 Delay? Again
•  » » 6 years ago, # ^ |   0 yep
•  » » 6 years ago, # ^ |   +1 When it was moved last time, servers were showing they are busy almost all the time, hopefully today it will be better...
•  » » » 6 years ago, # ^ |   0 hope that also last time I asked to be unrated because of the same reason but they told me they didn't face any problem during contest :D now it seems that it's not mine only :D
•  » » » » 6 years ago, # ^ |   0 There was a lot of contestants complaining, I didn't understand why it was rated, I left the contest earlier also...
 » 6 years ago, # |   -23 Scoring have been published. Best luck to all participants.
 » 6 years ago, # |   0 Contest not start
 » 6 years ago, # |   +4 Not again! It's becoming a tradition to delay the contest right before it starts!
•  » » 6 years ago, # ^ |   0 This time, I am glad the contest got delayed. Forgot to register earlier.
 » 6 years ago, # |   +1 again more 10 minutes waiting :D nice. P.S. good luck everybody
 » 6 years ago, # |   0 when will i be candidate master???
•  » » 6 years ago, # ^ | ← Rev. 4 →   0 same problem here :D
•  » » 6 years ago, # ^ |   0 Just when you will have the quality to acquire it. Best luck to you in this round. :D
 » 6 years ago, # |   0 Almost every contest gets delayed these days! Anyone knows what the problem is?
•  » » 6 years ago, # ^ | ← Rev. 4 →   -8 Because the contestants in codeforces are increasing exponentially.
 » 6 years ago, # | ← Rev. 2 →   +3 I wish will be candidate master today)
•  » » 6 years ago, # ^ |   0 best of luck to you :)
•  » » » 6 years ago, # ^ |   +1 thx!)
•  » » 6 years ago, # ^ |   +9 Wish granted ;)
 » 6 years ago, # |   +2 I arrived at home just now from school (it's 12:30 here)I'm so stressful now... :(Please pray a good contest for me... :(
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 lucky man. contest will start with delay.
 » 6 years ago, # |   0 It delays for 10 minutes! Am I right?
•  » » 6 years ago, # ^ |   0 Yes, I hope no more delays!!
•  » » 6 years ago, # ^ |   -6 hmm, you are right.
 » 6 years ago, # |   0 Good luck to all!
 » 6 years ago, # |   0 Good luck guys !
 » 6 years ago, # |   0 Its good that this contest has 6 problems. Better chance to improve ratings. Wishing high ratings to everyone :)
•  » » 6 years ago, # ^ |   0 Really? It depends on number of problems? I don't think so...
•  » » » 6 years ago, # ^ |   0 Its not always correct, but most of the times it is easier to solve 3 problems out of 6 than solving 3 out of 5. Of course, it includes the fact that you should solve the 3 problems fast.
 » 6 years ago, # | ← Rev. 2 →   +2 Is there any way to help Codeforces to strengthen its servers ? I think it worth to pay for having a faster and stronger programming contest platform.
 » 6 years ago, # |   +8 Can you unblock gym?
 » 6 years ago, # |   +1 Hello, why all problem pages are blocked? is this because contest is running?
 » 6 years ago, # |   0 Does the interface always inform about hacks with delay?I got a message about my stupid C solution being hacked only after about 20 minutes and hadn't enough time to correct it =(
 » 6 years ago, # | ← Rev. 2 →   +2 Why all wrote n^2 to C. I earned 5 hacks because of that. (actually n is the length of string)
•  » » 6 years ago, # ^ |   0 All my hacked solutions were exactly the same. My test was s = '9' 10^6 times, a = 9, b = 2
 » 6 years ago, # |   0 Awesome contest! Thanks for the problems. :)
 » 6 years ago, # |   0 Omg, after I locked my C I found it will fail with 1230 123 10 ...I'm so unhappy :-(BTW: where I can test hacking using generator? Because I wanted to try huge input for heu2013201410's solution in my room — 27...
•  » » 6 years ago, # ^ |   +1 The answer should be "No"? As your test doesn't differ from120 12 1
•  » » » 6 years ago, # ^ |   0 Answer is Yes I think — 123 0
•  » » » » 6 years ago, # ^ |   +19 I think it's "NO". Both parts should be positive integers that have no leading zeros.
•  » » » » 6 years ago, # ^ |   +1 Both the resulting numbers should be positive integers. So the numbers can not be 123 0.
•  » » » » » 6 years ago, # ^ |   0 Thats good message, thanks and now its clear, why my hacking failed. Stil better -100 then -1000...
•  » » » » 6 years ago, # ^ |   +1 Actually I think answer should be NO according to 3rd test ?!
•  » » 6 years ago, # ^ |   0 Wanted to hack solution C by TL with test. 1...1 (1 repeats 1e6 times) 5 1 But this test file has size (1e6 + 5) Bytes! And this is more then 256KB. Why does system not allow to upload big tests??? Lost my hack because of this.
•  » » » 6 years ago, # ^ |   +1 How about generator?
•  » » » 6 years ago, # ^ |   +1 You can create generator — program, that generates the input. I wanted to try it first time today also. Motivation is clear, if everyone uploads 1MB big file it is a lot of network traffic...
•  » » 6 years ago, # ^ |   0 A generator is a program which outputs the hack input in the correct format. I don't think that you can test it without a contest. Just write one and check if the generated input is ok.
•  » » 6 years ago, # ^ |   0 The two parts must be positive integers is zero considered to be a positive integer ?
•  » » » 6 years ago, # ^ |   0 No, if 0 would be considered into solution, the problem statement should say "non-negative integers"
•  » » » » 6 years ago, # ^ |   +3 I know I just reply to Betlista comment
 » 6 years ago, # | ← Rev. 2 →   0 Div.2 C. Couldn't understand why hack attempts were unsuccessful until realized that me forgot expand generated test changing magnitude(10^) from 1 to 6 :( .
 » 6 years ago, # |   -9 The problem statement of F today was so bad and unclear that I had to read the statement over and over again and rewrite my code about 4 times from scratch because of not understanding what was actually I needed to do. I had to code this problem mostly on assumption. Glad it was only a div-2 contest. I hope the authors will provide easily understandable statements from next time.
 » 6 years ago, # |   0 why b=1000000007 is invalid test for hacking of C?
•  » » 6 years ago, # ^ |   0 The number is too large, look at constraints. Has to be less than 10^8.
•  » » » 6 years ago, # ^ |   0 oh :| I think it was 10^18 :|||
•  » » 6 years ago, # ^ |   0 Because b ≤ 108
•  » » 6 years ago, # ^ |   0 Because b must be in range [1..10^8] It clearly said in problem statement
 » 6 years ago, # |   0 this code is still wrong, but for this tc, it gives right answer and yet it got WA http://codeforces.com/contest/490/submission/8820977
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 you have extra 9 at the begin of second number
•  » » » 6 years ago, # ^ |   0 my bad, thx for your info
 » 6 years ago, # |   0 New contest new color...
 » 6 years ago, # |   0 Can anyone tell me why am I getting a wrong answer on pretest 4 ? I'm new here! http://codeforces.com/contest/490/submission/8821196 (Ignore the biginteger part,coding begins at the function compute() ) thanks!
•  » » 6 years ago, # ^ |   0 Is it wrong because I messed up the concept of leading zeros / trailing zeros?! wrong condition?
•  » » 6 years ago, # ^ |   0 Because there is the answer for string "604": "60 4" where both of numbers are divisible by 6 and 4 respectively
•  » » » 6 years ago, # ^ |   0 What should be the condition to check if there aren't any leading 0s? Is my implementation wrong?
 » 6 years ago, # | ← Rev. 2 →   0 Why can't I see the wrong test case when submitting problem E in practice?Edit: It's fixed now
 » 6 years ago, # | ← Rev. 2 →   +5 Surprisingly fast system test. I thought problem C can be solved using O(n2) algorithm. Too bad I didn't check the constraint for n. Anyway, thanks for the contest!
 » 6 years ago, # |   0 I think that codeforces should check the IP when a new user registers because i can bet that there are lots of div1 members who make clone accounts in order to participate in div2 rounds with rating and because of that our chances for a lower rating grow. Or we get a lower improvement than we should. Just my opinion.
•  » » 6 years ago, # ^ |   +6 Some nations do not have static IP.
•  » » » 6 years ago, # ^ |   0 I know that it cant be that accurate, but at least.. you block few users. With a bit luck, more users :D
•  » » 6 years ago, # ^ |   0 IP based check is bad idea. But I have same feelings... Mbaybe solution could be that when there is no Div 1 competition, they will have same problems in and they can compete in speed typing... Or separate ranking can be created for such contests...
 » 6 years ago, # |   +7 When will ratings be updated ???
 » 6 years ago, # |   0 Anyone on how to approach Problem C. I thought about writing own function to check if the two numbers formed are divisible by the given number : eg. 64010 64 10 check for each value of i 6|4010, 64|010, 640|10 ... for divisibility Will this approach run in time?
•  » » 6 years ago, # ^ |   +1 try to check forward and backward (will be almost the same like forward )
•  » » » 6 years ago, # ^ |   0 Yeah I got it. Have to use exponentiation as well.Thanks
•  » » 6 years ago, # ^ |   0 This is my code..have a look..just used the wrong condition to implement trailing 0s condition. Any feedbacks are welcome. http://codeforces.com/contest/490/submission/8821196
•  » » 6 years ago, # ^ |   +1 the idea starts from the observation:lets say you have the number 7854178541%x = ( (7*10^4)%x + (8*10^3)%x + (5*10^2)%x + (4*10^1)%x + (1*10^0)%x )%xif you dont get the further idea for the solution i will add the next part :D
•  » » » 6 years ago, # ^ |   0 thanks... i got the idea. Couldn't expand the number during the contest, but I got the answer now. Thanks.
•  » » » 6 years ago, # ^ |   0 cool, thanks!
 » 6 years ago, # |   -8 For B I allocated int[] map = new int[1000000] instead of int[] map = new int[1000001] and I got a WA on Test 55 because of that. Cruel!
•  » » 6 years ago, # ^ |   +4 Do people like downvoting stuff just for fun? This community should be a little more mature.
 » 6 years ago, # | ← Rev. 2 →   0 I got TLE in 'C' with O(n) solution. :/
•  » » 6 years ago, # ^ |   +9 don't use strlen(s), it has O(n) complexity, where n is length of s.
•  » » » 6 years ago, # ^ | ← Rev. 2 →   0 Wasn't knowing that :(
•  » » 6 years ago, # ^ |   +8 strlen() has a complexity of O(n), not O(1).So your overall complexity is O(n^2).
•  » » 6 years ago, # ^ |   0 you repeatedly called strlen, which has n complexity;
 » 6 years ago, # | ← Rev. 2 →   -11 OK
•  » » 6 years ago, # ^ |   +11 just use c/c++
•  » » 6 years ago, # ^ |   0 It depends, what is the solution, for example this ona — http://codeforces.com/contest/490/submission/8818849 have to end with TLE and problem is not in python...
•  » » » 6 years ago, # ^ |   0 yes, but almost python's solution is correct!
•  » » » 6 years ago, # ^ |   0 such as this one: http://codeforces.com/contest/490/submission/8818227
•  » » » » 6 years ago, # ^ |   0 I do not know python well, this: mods_p = [] mods_p.append(mod_p) is list? Try to use array, should be quicker...
 » 6 years ago, # |   0 How I can solve problem C?
•  » » 6 years ago, # ^ | ← Rev. 10 →   0 Traverse a string in both directions and keep two arrays ad, bd.For ad[i] we traverse the string from the left to the right and find the reminder s[1: i]%a. There is a formula for this: ad[i] = (ad[i - 1] * 10 + s[i] - '0')%a.For the bd[i] we traverse string from the right to the left and find the reminder s[i + 1: n]%b. Also we keep the variable bteni which is equal to 10i %b. So there is a formula for bd: bd[i] = (bd[i + 1] + (s[i] - '0') * bteni)%b.Finally we traverse the arrays ad, bd and search for such index i, that ad[i] = bd[i + 1] = 0.
•  » » » 6 years ago, # ^ |   0 thanks~
•  » » » 6 years ago, # ^ |   0 Could you explain why these formulas work? Or point to a source where this theorems are explained? Thanks
 » 6 years ago, # |   +12 Rating....so late.
 » 6 years ago, # |   0 Can someone Please explain the idea behind problem C ? in detail preferably. Thank You. :)
•  » » 6 years ago, # ^ |   +1
•  » » 6 years ago, # ^ | ← Rev. 4 →   +6 If we divide the sequnence into two parts: 1, 2, ..., i and i + 1, ..., n, then we need to check s(1, i) % a and s(i + 1, n) % b. Since s(1, i) % a = (s(1, i — 1) * 10 + s[i]) % a, s(i, n) % b = (s(i + 1, n) + 10^(n — i) * s[i]) % b, we can compute every s(1, i) and s(i, n) within O(n) time firstly. Now, we can check s(1, i) % a and s(i + 1, n) % b within O(1) time.
•  » » 6 years ago, # ^ | ← Rev. 3 →   +5 I Will explain it using an example:consider the number 116401024(call it N)we can split it as (1*10^8)+(1*10^7)+(6*10^6)+(4*10^5)+(0*10^4)+(1*10^3)+(0*10^2)+(2*10^1)+(4*10^0) a8 a7 a6 a5 a4 a3 a2 a1 a0 If this number is divisible by a number M then the modulus must be 0(i.e. N%M==0), to check this we can do: rem = 0; rep i from 0 to 8: rem = ( rem%M + ai%M )%M; if(rem == 0) the number is divisible by M Coming to the actual problemThe possible ways we can split the number into two parts are : 1 16401024 11 6401024 116 401024 1164 01024 11640 1024 116401 024 1164010 24 11640102 4 now for each of this splits we want to check if the first part is divisible by "a" and second part is divisible by "b".Now we can modify the above for loop by storing for each index i, whether the part of the number from 0 to i is divisible by a, like this: n = Number of digits in N; rem = N[0]%a; rep i from 1 to n-1: --------------------------------> O(N) rem = ((rem*10)%a + (N[i]%a))%a if(rem == 0) divisible_by_a[i] = true; else divisible_by_a[i] = false; Similarly, we can do for b starting from least significant digit of the number.and once we have divisible_by_a and divisible_by_b, we can easily check if we can divide the number into two parts for each index i by the logic: (divisible_by_a[i] == true) && (divisible_by_b[i+1] == true) && (N[i+1] != 0) -------> O(1) 
•  » » » 6 years ago, # ^ |   0 Thank You :)
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 Call the large number s and let n be its length. For every prefix, compute x[i] = s[0..i] % a. For every suffix, compute y[i] = s[i..n-1] % b. Now scan s from left to right and check if x[i] == 0 and y[i+1] == 0 and s[i + 1] != '0'. If this condition holds, we have an answer.
 » 6 years ago, # |   +23 Country wise rankings updated.
 » 6 years ago, # | ← Rev. 2 →   0 Can anyone please tell me, why my solution of C always takes 0 or 15 ms and suddenly on test 36 i got TIME_LIMIT_EXCEEDED? There are no cycles or anything and I'm getting really clueless... http://codeforces.com/contest/490/submission/8823963
•  » » 6 years ago, # ^ |   0 There's also the weird thing, that it shows my output (which I think isn't supposed to be there, because I shouldn't have time to it), but there is no Answer...
•  » » 6 years ago, # ^ |   0 Don't use ansistring. Try to use array of char instead.
 » 6 years ago, # |   0 where is the editorial?
 » 6 years ago, # |   0 Can someone explain to me their approach for problem E? I got it accepted in practice but barely under the time limit so I guess there are faster approaches.
 » 6 years ago, # |   0 What's wrong with checker of problem D ? Test #12 2160 3240 7200 384 Вывод 5 1280 1080 3600 384 Ответ 5 640 2160 3600 384 Протокол тестирования wrong answer reported answer can be reached in minimum 1000000002 operations, but given result is 5 operations Seems like my solution gave a valid answer, but checker haven't noticed that!
•  » » 6 years ago, # ^ |   0 1280 can not be reached
•  » » 6 years ago, # ^ |   0 Because you cant get 1280 from 2160
 » 6 years ago, # |   0 What is the approach for Problem B?
•  » » 6 years ago, # ^ |   +1 My approach: If we determine the first two elements, we can determine the rest uniquely. -> Make an array X such that X[A[i]]=B[i] for every i. Then answer[i+2]=X[answer[i]] for any i. The student ID of the second person is X[0]. The first person in the line has a = 0, b = (second person's ID). The student ID of the first person is A[i] which does not appear in array B. Let id = the first person's ID. There's no student such that b_i = id, because there's no one in front of him! And conversely, the first person is the only student with such property. We can uniquely determine the first two persons, which determine the rest uniquely.The total run time is O(n).My submission
•  » » » 6 years ago, # ^ |   0 thanks a lot..
 » 6 years ago, # |   0 please provide the editorial section ..please ASAP
 » 6 years ago, # |   0 Can someone please explain their approach for problem E? I got it accepted in practice but barely under the time limit so I guess there are faster approaches.
•  » » 6 years ago, # ^ |   +4 Just find the smallest feasible number every time. I'm not sure what is the best algorithm to find this, but my solution is: First, compare the length of the string with the one of last string, and there are three cases: 1. s[i].size()s[i-1].size(): set all '?' to 0 (If it's the first number, set it to '1') 3. s[i].size()==s[i-1].size(): Find the first digit j where s[i] and s[i-1] is different. There are two cases: 1. j==s[i].size(Can't find) or s[i][j]s[i-1][j]: Similar to the case 1, but don't need to do the first step because this digit is already larger.
•  » » » 6 years ago, # ^ |   0 Thank you very much. It's very similar to my solution but I used a recursive approach and I guess that's what's taking my algorithm longer.
•  » » 6 years ago, # ^ |   +3 I used binary search to solve E.Here is my submission.
•  » » » 6 years ago, # ^ |   0 Could you please explain how you used binary search? I didn't understand very well by reading the code.
 » 6 years ago, # |   0 When I was trying to hack a solution by the output generator, I got a message "FAIL Line [name=public_key] equals to "#include
 » 6 years ago, # |   0 Do you guys know when the editorial will be published? I am really interested what is the idea for D and how one can figure it out.
•  » » 6 years ago, # ^ |   0 Every time Polycapus eats the chocolate, he set one of the number to 2/3 or 1/2. So what you should consider is, whether these two products is the same after dividing all 2 and 3. If it is, you can set the power of 3 to the same number by performing several 2/3 cuts to the one which has more 3, and then set the power of 2 to the same number by 1/2 cuts.
•  » » » 6 years ago, # ^ |   0 Thank you very much!
 » 6 years ago, # |   0 My C problem reached TL on test 42. How to solve this problem correctly?
•  » » 6 years ago, # ^ |   0 you are using substr and strlen functions and they both have o(n) so your code complexity have o(n^2) runtime. find a way to get ride of them both.
•  » » 6 years ago, # ^ |   +5 Use bigmod. I think your solution is N^2
 » 6 years ago, # |   +21 The contest is useless. I don't gain any thing throng the contest. The problems are so silly!!!
•  » » 6 years ago, # ^ |   0 throng -> through
•  » » » 6 years ago, # ^ |   0 btw: you can edit the post...
•  » » 6 years ago, # ^ |   +5 That's really offensive thing to say. They spent a lot of time to write/test problems and put them together.
•  » » » 6 years ago, # ^ | ← Rev. 2 →   +1 Sorry for my rude talk.Forgive me please.But I do think the problems need to be considered.....
•  » » 6 years ago, # ^ |   +3 Can you be more specific? Can you describe what was silly for each problem?
•  » » » 6 years ago, # ^ | ← Rev. 3 →   +3 Eh.. All the problem just add some details on the common problems. Or just problems for details.
•  » » » » 6 years ago, # ^ |   +3 Well, I guess I agree with you....
 » 6 years ago, # |   0 How to solve B?
 » 6 years ago, # |   0 Is there any tutorial?
 » 6 years ago, # |   +3 The B has a error in your problem description.To give an example, how do you solve in this data? 4 0 2 1 3 3 5 4 0It's easy to infer that the correct answer is 1 2 3 4 5.. but many programe are not give me this answer but also accept it! please view.
•  » » 6 years ago, # ^ |   0 In your example you have n=4, but 5 different ids in the list. Change n to 5 and add a line with "2 4" — then you will get 1 2 3 4 5.
•  » » » 6 years ago, # ^ |   0 Must change to 5? Oh.. Maybe i have not read this problem carefully..
•  » » 6 years ago, # ^ |   +8 Your test is wrong not enough information while n == 4 if n == 4 you test data be like this 4 0 2 1 3 2 4 3 0 if n == 5 4 0 2 1 3 2 4 3 5 4 0 try again
 » 6 years ago, # |   +6 In case anyone is looking for the Editorial as I was, it has been posted here.
 » 6 years ago, # |   0 Hello, When the next contest will be hold?
 » 6 years ago, # |   0 could you help me please to figure out why WA on test 20 ? http://ideone.com/0AzRks
 » 6 years ago, # |   0 After reading the tutorial, I realized how unnecessary this solution by me is: http://codeforces.com/contest/490/submission/8829276