Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

### Sereja's blog

By Sereja, 8 years ago, translation, ,

Hello everybody!

Welcome all to Codeforces Round #131, which will be held on Monday, 30th of July at 19:30 MSK. I am (Sergey Nagin) an author of the problems. This will be my First Codeforces round and I hope it won't be the last one :).

I would like to thank Mike Mirzayanov(MikeMirzayanov) who made this contest possible, Roman Furko(Furko) and Gerald Agapov(Gerald) for helping to prepare this round and Maria Belova(Delinur) for the translation of problem statements into English. I hope that problems will be interesting for you.

Good luck!

Problems’ point values in Division 1 are 1000-1000-1500-2000-2500. Problems’ point values in Division 2 are 500-1000-2000-2000-2500.

I strongly recommend you to read ALL the problems.

The contest is over! Congratulations' to winners!

First division:
1 place: Egor
2 place: Petr
3 place: tourist
Second division:
1 place: antimatter
2 place: c175353
3 place: l521530

I hope, that problems were interesting for you.

You can view tutorial.

Some personal information. This year I finished school and I will go to university. I study programming during almost five years. In addition to computer science, I like sports: powerlifting, arm wrestling and swimming.

• +220

 » 8 years ago, # |   +13 so, we are gonna have some sports flavored problems!!
•  » » 8 years ago, # ^ |   -7 And everyone is in the olympics mood too!!
 » 8 years ago, # |   +1 will the scoring be as usually or dynamic ?
•  » » 8 years ago, # ^ | ← Rev. 3 →   -15 Dynamic scoring is nearer and nearer to become 'usual & default' :)UPD: not this time :D
•  » » » 8 years ago, # ^ |   -11 Well usually when the contest only for DIV 2, it's using dynamic, and for both Division they usually use normal scorring IMO
•  » » » 8 years ago, # ^ | ← Rev. 2 →   +3 I disagree..If you browse thorough the contests after Round #113(after dynamic scoring was introduced) you will find that apart from rounds #115 and #126 and all rounds from the trio Nalp- Gerald-HolkinPV (which have dynamic scoring systems) ,,the scoring system has been traditional in other rounds. So I think they leave it on the authors to decide ..
 » 8 years ago, # |   -18 Good Luck And Have Fun! :)
 » 8 years ago, # | ← Rev. 8 →   -13 hacked by hackers
•  » » 8 years ago, # ^ |   -7 What said bad(he has -4)?
•  » » » 8 years ago, # ^ |   +36 Don't try to understand negative votes on codeforces.
•  » » » » 8 years ago, # ^ |   -13 if comments have negative votes it is bad but lashabuxo-s comment i think is not bad.
•  » » » » » 8 years ago, # ^ |   -7 If comment have negative votes — then somebody thinks it is bad.
 » 8 years ago, # |   0 How to run my program at local machine? Above is quickly enough?g++ xx -o exe exe < in.txt
•  » » 8 years ago, # ^ |   +3 g++ code.cpp -O2 -o exe
•  » » 8 years ago, # ^ |   +1 g++ name.cpp && a.exe
 » 8 years ago, # |   +4 Very interesting B question in Div-2..It made me so involved that I did'nt have the time to read C,D,E..But I am happy I managed to pass th pretest finally after 11 WA..
•  » » 8 years ago, # ^ | ← Rev. 3 →   0 Some test example from Hacker. Input: 3 0 0 0 Output: 000 Answer:0
 » 8 years ago, # |   +72 how can This Submission Pass the preetest but got compile error while Systest ?
•  » » 8 years ago, # ^ |   +27 Compilation Error на 10-м тесте facepalm
•  » » 8 years ago, # ^ |   +1 How is that even possible?
 » 8 years ago, # |   +4 Great contest, thanks to all of you.
 » 8 years ago, # |   +15 It seems java needs more space than C++. In div1-C I initialize a 3-D array and get MLE.
•  » » 8 years ago, # ^ |   +13 I did not look at your code but it may be the case of how you declared the array.Arrays are objects in Java, so a[1000][1000][2] creates one million objects and a[2][1000][1000] creates only 2000. There is an overhead for each object.If space is an issue, use a 1D array instead.
 » 8 years ago, # |   +3 In the contest, I got many wrong answer on pretest 1 of problem D,.. After the contest, I found out the mistake, only one mistake: 10.0 => 1.0. And I got AC after fixing it... So sad!! :(
 » 8 years ago, # |   0 For div2 B, can someone confirm test 13 is the same with test 14, i.e. the input is ten thousand 0s? My solution passed 13 but failed on 14, quite weird.
•  » » 8 years ago, # ^ |   0 your solution didn't pass test 13. you got wrong answer on test 13.
•  » » » 8 years ago, # ^ | ← Rev. 2 →   0 The solution I meant is below, not the one during the contest.
•  » » » » 8 years ago, # ^ |   +8 test 13 and 14 are not identical. I suppose there is a difference between them and since we can't see the whole test case we can't see the difference.
•  » » 8 years ago, # ^ | ← Rev. 2 →   0 The wrong solution is here. Please give me some hints.
•  » » » 8 years ago, # ^ | ← Rev. 2 →   0 Input can be like this (100000) zero for test 13 (99999) zero + 1 for test 14 both of them have same answer but, because is too long, it will cut.
•  » » » 8 years ago, # ^ | ← Rev. 2 →   0 input 5 0 0 0 0 5 what answer?
•  » » » » 8 years ago, # ^ |   0 0
•  » » » 8 years ago, # ^ |   0 Thanks you guys who replied. I find the bug and get it fixed. This is the correct solution. It turns out case 13 and 14 are indeed different.
 » 8 years ago, # |   +6 very nice problem set!
 » 8 years ago, # |   +1 The problemsets are nice, thank you, Sereja.
 » 8 years ago, # |   0 Problem B was very confusing.. as in the problem statement, it was written: Each digit is allowed to occur in the number the same number of times it occurs in the set.Then how the ans for second test case is: 5554443330 since in input set 4 is occurring 4 times but in output integer it is occurring 3 times only.
•  » » 8 years ago, # ^ |   0 It is permitted to use not all digits from the set
•  » » 8 years ago, # ^ |   0 They said: " It is permitted to use not all digits from the set"
•  » » » 8 years ago, # ^ |   0 I took it as.. if i am not taking any digit then i am not supposed to use that digit in the output at all. Means that digit's count would be made 0. I tried other way also, but because of a very silly mistake my solution got hacked.
•  » » 8 years ago, # ^ |   +4 May be you missed this -> '**It is permitted to use not all digits from the set**'
 » 8 years ago, # |   +4 I Think It Would be better to increase Contest Time for some contests like this To let People have more Fun !
 » 8 years ago, # |   -21 The comment is hidden because of too negative feedback, click here to view it
•  » » 8 years ago, # ^ |   -9 It's interesting to see how many downvotes that comment will get, because it'll mean that some people actually care about comments that downvoted a lot.
•  » » 8 years ago, # ^ |   +15 One of the advantages of being Petr is that you can make such troll-jokes without throwing your reputation towards S = {x : x < 0} where x belongs to R.
•  » » 8 years ago, # ^ |   +7 When I try to click "here" the page scrolls to the top and the comment doesn't show up.
•  » » » 8 years ago, # ^ |   +1 I don't get how you don't get it. And I'm the "blue" one here.
 » 8 years ago, # |   +11 Does the intended solution for div1 E use hashes? I saw only hash solutions and wonder if they can be hacked using ideas from recent anti-hash articles.
•  » » 8 years ago, # ^ |   +13 I think that this is the reason why people submited this problem in last minutes of the competition — not to be hacked...
•  » » 8 years ago, # ^ | ← Rev. 3 →   +19 I'm quite sure it can be solved with something similar to KMP.Assume we can, after preprocessing, quickly compute functions prev(k, i) and next(k, i) for a permutation P, which give the first element j in [i, k — 1] preceding / succeeding k in P.Let suf[k] be the minimum j > 1 such that the part of A composed of elements [j, k] is (EDIT) the same permutation as the part of A composed of elements [1, k — j + 1]. We can compute suf[] using a linear number of calls to prev() and next() on A.Later we can use suf[] like a KMP table to compute all shifts that match with a linear number of calls to prev() and next() on A and B. :)
 » 8 years ago, # |   0 How can I know number of 1's in testcase number 12 in div2 problem B ?
•  » » 8 years ago, # ^ |   +8 There is no way to do this.But... You can count them, and guess counter by binary search. (For example, if cnt < 4000 then cause TLE, otherwise get WA)
•  » » » 8 years ago, # ^ |   +8 I found a better way compared to this. print out number of 1's for this particular case . number of 1's are 49898 . :D anyway thanks for your help.
 » 8 years ago, # | ← Rev. 2 →   +16 One Does Not Simply Update the rating quickly
 » 8 years ago, # |   +4 i am new on codeforces.com and how add friend???
•  » » 8 years ago, # ^ | ← Rev. 8 →   +1 hacked by hackers
•  » » 8 years ago, # ^ |   0 lashabuxo tell me why you made multiple accounts? http://codeforces.com/blog/entry/4924#comment-100414
•  » » » 8 years ago, # ^ |   0 i believe it's a way to get upvotes on his comments
•  » » » » 8 years ago, # ^ |   0 Is there any rational reason to do this? :P
•  » » » » » 8 years ago, # ^ |   0 don't ask me :)
•  » » 8 years ago, # ^ |   +5 open someone's page and click the star on the right of the name
 » 8 years ago, # |   -6 tourist lost his Codeforces Red Target :(
 » 8 years ago, # |   +1 When will the editorials be available for this contest's problemset? Thanks in advance
•  » » 8 years ago, # ^ |   -20 As soon as it gets posted.
 » 8 years ago, # |   -6 Wrong answer on test 65 on problem B, div 2. Don't you know what it is?
•  » » 8 years ago, # ^ |   +2 div 2,problem B: your submissions status and test 65:
 » 8 years ago, # |   0 when the Problem's Analysis will be placed ?
•  » » 8 years ago, # ^ |   0 Problem's Analysis already placed, but not at english language,link here
 » 8 years ago, # |   0 Although I liked the problems, I think problem C was a bit of a fiasco. On one hand the exact same problem has been given before in TopCoder, SPOJ, one Bulgarian competition (okay, no way to know that) and God knows where else. Thus many people had the chance to solve it in several minutes (I for one needed 9 minutes, and other people even less). Anyway, this happens (I know from bitter experience).I also was happy to see the negative numbers (which means negative results are possible). This is another TopCoder trick I've felt for before — if you use memoization and you initialize your array with -1 (which is valid number in this case) you have a correct, but possibly too slow solution. For those of you who don't know it — if the answer to the problem is -1, then some of the states will be calculated over and over again and it can turn really slow. So I was looking for such solutions in my room, however most were using standard iterative dp (which is okay with that) and didn't have the chance to challenge anyone.However, such a test was not present in the system tests, so some (possibly plenty) of wrong solutions passed.The test is rather simple to create: int n = 300; fprintf(stdout, "%d\n", n); for (int i = 0; i < n; i++) for (int c = 0; c < n; c++) fprintf(stdout, "%d%c", ((i + c == 580) ? -1 : 0), c + 1 == n ? '\n' : ' '); 
•  » » 8 years ago, # ^ |   +1 But, is there a way to use a smaller state (not 598x300x300) so that you don't get memory limit exceeded? Because if that can't be done then I guess that could justify the absence of such cases
•  » » » 8 years ago, # ^ |   +5 Yes, sure. See my solution, it uses twice smaller state (if I initialize my dyn[][][] array with -INF instead of using additional array).
 » 8 years ago, # |   -13 Alrededor de mierda triste.
 » 8 years ago, # |   0 When I click the tutorial link, I can see a tutorial, but not in English. Why? The English tutorial has been released, I think.
•  » » 8 years ago, # ^ |   0 You may change '.ru' to '.com' in link. http://codeforces.com/blog/entry/4982
 » 8 years ago, # |   0 Hello! I don't know where to post my problem so i'll post it here. I apologize if posting this here is wrong.Well i have tried the problem Numbers(D div2, B div1) and i finally solved it. The source code is here http://codeforces.ru/contest/214/submission/1974583I get WA on test 10 (100 0 0 0 0 0 0 0 0 0 0). The strange thing is that when i run the code it prints the right answer on my computer. Here when i submit it, the answer on the same test is different and i don't get it why it does that.Please help me to see what is wrong :(
•  » » 8 years ago, # ^ |   0 In your code, len can be 0, so in Comb[len - 1][j] index goes -1 and so you get weird numbers from uninitialized memory, instead of expected 0 value.
•  » » » 8 years ago, # ^ |   0 Thank you very much :) I finally got AC. I guess i missed that -1 index.