### Sereja's blog

By Sereja, 6 years ago, translation, ,

Hello everyone!

Codeforces Round #204 will take place on Friday, October 4th at 19:30 MSK. This is my eights Codeforces round and I hope not the last.

I'd like to thank Gerald, yvasyliv, Cenadar and Zlobober 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.

Problem point values for the first division: 1000-1000-1500-2000-2000.
Problem point values for the second division: standart.

Gl & hf ! :)

• +237

 » 6 years ago, # |   +3 Maybe a bit weird my question, but anyway, which are the numbers of the other rounds you have prepared? I just want to see the style of your problems.Thanks.
•  » » 6 years ago, # ^ |   +31 You can easily figure that out by checking his blog entries.
•  » » » 6 years ago, # ^ |   0 You are absolutely right. Thanks a lot :D
 » 6 years ago, # |   +6 I think it is "Friday, October 4th".
•  » » 6 years ago, # ^ |   0 Fixed. Thanks :)
 » 6 years ago, # |   +10 Two matches in one week. I like it.
 » 6 years ago, # |   +23 I like Sereja's contests!!
•  » » 6 years ago, # ^ |   +72 Sereja's contests like you too!!
 » 6 years ago, # |   -8 i think you mean, Friday, October 4th at 19:30 MSK.
•  » » 6 years ago, # ^ |   0 Yes, thanks)
 » 6 years ago, # |   0 One of my friends (SeyedParsa) likes Sereja's contests because he improves his rate rapidly in Sereja's contests and I wish I can improve my rate in this contest too:))) Good luck everyone;)
•  » » 6 years ago, # ^ |   +3 And now I should say I like Sereja's contests too!!Because I improve my rate after a long time in this contest!!Thank you Sereja:)
 » 6 years ago, # |   -22 Static or Dynamic problem weights?
 » 6 years ago, # |   -8 Hope the problems would be fun!
 » 6 years ago, # | ← Rev. 2 →   -16 a question what is different of Div1 and Div2?(i am new here!) and how can i register for them?
•  » » 6 years ago, # ^ |   +1 Div1 is for high ratings and Div2 for others ! Problems in Div2 are easier than Div 1 !
•  » » 6 years ago, # ^ |   +16 http://codeforces.com/help I think you'll find your answer in point #15(What are the rating and the divisions?). You can check the rest of the answers for information since you're new here, you'll find it very interesting.
•  » » » 6 years ago, # ^ |   0 thanks, i will read.
 » 6 years ago, # |   -34 reading all problems strongly recommend :D
•  » » 6 years ago, # ^ |   +6 Thanks Captain.
•  » » 6 years ago, # ^ |   +2 Just out of curiosity... But why is this comment being down-voted so much?
•  » » » 6 years ago, # ^ |   +4 Maybe because the same is written in the blog post itself? That makes the post sort of a spam. At least I downvote exact cliches (those that don't have anything unique) unconditionally.Plus, the grammar's bad.
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   +16 I rather thought that these down-votes kind of ruin the harmony here at Codeforces... Most of the down-voted comments are posted by newcomers, they may simply want to express that they're here, that they want to be part of the Codeforces community... Maybe what they say contain nothing important but that's not a reason for down-votes... I would think that down-votes are for those who insult people or are impolite... Furthermore, about grammar... As there are people from all over the world, with most of them are from non-English-speaking countries, I think bad grammar is very understandable...
•  » » » » » 6 years ago, # ^ |   +9 I don't see many comments that are rude, but still not in the "should be deleted by admin" region. There are so few of those that if we really limited the reason for downvotes to be rudeness, the downvote button would just become a tool for trolls and it'd be better off removed. And that'd be weird.While I realize it's a bit cruel, writing can be good or bad, and I try to vote accordingly. It's also unfair if someone writes a good comment, and gets around as many votes as someone who copies a sentence from the text on top of the page.
•  » » » » » » 6 years ago, # ^ |   +9 You're totally right... I just find it quite uncomfortable to see a lot of comments getting down-voted for no obvious reason... I really hope everyone can think before they vote like you do...
 » 6 years ago, # |   -22 thx...I hope everyone will get high score;
 » 6 years ago, # |   +8 Best author's (in my opinion) contest exactly on my birthday, really awesome present :) GL &HF everybody )
 » 6 years ago, # |   +10 We have a national level university contest in Bangladesh tomorrow. Hope it would be a good warmup.
 » 6 years ago, # |   +12 Good Luck for all~..
 » 6 years ago, # |   +2 What about the score distribution? :)
 » 6 years ago, # |   0 seens to be a little bit hard? well, hope everyone can figure out all the problems && enjoy every contests:)
 » 6 years ago, # |   -14 first time writing div 1 round
 » 6 years ago, # |   +14 Wow... More than 4000 participants :D What is the record, by the way? :)
•  » » 6 years ago, # ^ |   +1 we will be having acm icpc regional qualifications this month hence the increased number of participants :)
•  » » 6 years ago, # ^ |   0 Hope that doesn't affect on stability of the contest :)
 » 6 years ago, # |   +4 Looks like no 500-points problem for Div 1 ... It may be thought round for me, first time participant @ Division 1 ... ;-)Hope better results 4 everyone!
 » 6 years ago, # |   0 The comment removed because of Codeforces rules violation
•  » » 6 years ago, # ^ |   0 Read the problem carefully.
 » 6 years ago, # |   +2 How solve problem C?
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 Initially round down all the numbers. Now, you have to round up 'n' numbers. Choose as many as you can so that difference becomes less. Next choose as many as you can so that this minimum difference remains (by choosing integers). If still you haven't chosen 'n' numbers, choose the rest. 4667241
•  » » 6 years ago, # ^ |   0 It can be solved by DP: DP[i][floor] : In the i-th number having floor numbers rounded down, what's the best answer? You should think how to calculate what's the best state as you just have two of them.
•  » » » 6 years ago, # ^ |   +1 I thought of this, but I thought that somehow the sign of the difference would matter. So I added another state and I calculated the maximum from the negative differences and the minimum from the positive differences. Can anyone explain why the sign doesn't matter? Especially when you can reach a state with both x and -x. Thanks!
•  » » » 6 years ago, # ^ |   +10 It can be solved linearly. Unless a_i=0 (discarding the integer part), it doesn't matter whether you round a number up or down. If you round up, you add 1-a_i to the difference. If you round down, you add -a_i. So you end up with the total difference being n-sum(a_i). Now, when a_i=0, rounding up gives 0, not 1. So you count the number of a_i=0 and count how many of those to round up. Subtract this number from n-sum(a_i) and you get the answer.
•  » » » » 6 years ago, # ^ | ← Rev. 4 →   0 Thank you for the answer! But it's still not clear for me: in the test case 0.000 0.500 0.750 1.000 2.000 3.000 the N - sumai becomes 1.750, which can't be transformed to the answer of 0.250 by substracting 1s...
•  » » » » » 6 years ago, # ^ | ← Rev. 2 →   +3 Sure it can. Note that at the end you have to take absolute value of the answer. As cfk said you need to count how many a_i=0 you round up. In this case 2, so |1.750—2|=0.250.
•  » » 6 years ago, # ^ |   +5 i solve it using greedy, sadly, after contest :)we just need calculate the elements that have same value, whether rounding up or down, as this number have same value, it doesnt matter we treat this numbers as round up operation or round down operation, let's call this total of elements 'sama'assume we have sum of all rounded down numbers, let's call this 'h', then, iterate from i = 0 to n, and take the minimum difference of original sum and (h+i) that satisfy i+sama >= nhttp://codeforces.com/contest/352/submission/4676368sry for my bad english, hope you can understand
 » 6 years ago, # | ← Rev. 2 →   +8 I guess many submissions (including mine) for Div1-A will fail because of small array size (2000+etc) :(Liked the problem set (y)
 » 6 years ago, # |   0 I'm ready !!
 » 6 years ago, # |   0 There are 644 contestant in Div. 1 and there are almost 200 contestant who have no point.
 » 6 years ago, # | ← Rev. 4 →   +1 My 2nd Div1, I am very happy with 57th. Thanks for the problems, I really liked them. If only I didn't do A so slowly!What I am wondering is how people hacked A. I noticed that many people got caught on system test for A, but when I was trying to hack I couldn't find anything! So does anyone know common mistakes in A?
 » 6 years ago, # |   0 The contest is over and I still can't understand the statement of problem B. An explanation for the second test (not for the one with a single number in the array) would have been great ... Could somedody explain it?
•  » » 6 years ago, # ^ |   +1 You look for each number in which distance (according to indices) they occur. In the second test case, 1 is on the indices 0-2-4-6, means distance 2. 2 occurs on indices 1-5, means distance 4, and so on. If there would be a number that doesn't have a repeating distance (for example indices 1-3-6), then you shouldn't print it.
•  » » 6 years ago, # ^ |   0 you need to check all the indexes of all distinct numbers can represent an arithmetic progression 2nd sample indexes of (1) are 1 3 5 7 arithmetic progression with diff =2 indexes of (2) are 2 6 arithmetic progression with diff =4 all other numbers are unique so print them with 0 as the problem states
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 It means you should output like this:Whether the indexes of each number you choose in array meet arithmetic progression?Yes, output the common difference. (output 0 when the number appears only once)No, do not output this number.
•  » » 6 years ago, # ^ |   0 You have to output all the numbers x in the array such that their indices (the positions at which x are located) form an arithmetic progression. If x doesn't appear, then you discard it. If it appears once or twice, it's okay. If it appears more than once, you determine if the indices (say the 1st, 3rd, 5th elements are x) form an arithmetic progression. (To clarify, this is the criteria for if you output x, not how you actually solve it).For the second test case, only 1,2,3,5 appear so we only consider those. 1 appears at indices 0, 2, 4, 6 (0-based) and 2 appears at 1, 5. 3 and 5 appear only once. So all the numbers work. If 1 had also been at index 7, then it would not have been included as 0, 2, 4, 6, 7 is not an arithmetic progression.
 » 6 years ago, # |   0 Well, I really wonder can Problem C in Div.2 be solved by greedy algorithm?Why did my solution come out like this in Test #11?4671464
•  » » 6 years ago, # ^ |   +1 I am surprised your submission worked on the first 10 tests, but I guess they are pretty simple. Anyway, the problem states that half the numbers must be floored and half must be ceiling, but you do not take this into account. Also, I don't think a greedy idea like what you are attempting would work anyway.
•  » » » 6 years ago, # ^ |   0 Thanks for answering. My negligence.
 » 6 years ago, # |   +100 Why was E E?
•  » » 6 years ago, # ^ |   +6 I thought it was hard, but I was wrong :)
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 I guess they may have a O(n^2) and hard solution and didn't come up with the O(nlogn) and easy one.UPD. After reading rng_58's solution, I found what I said is wrong. The O(n^2) solution is much easier to implement :D.
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 Stupid question: why did all these solutions pass? It seems that for multiple equal elements we can take them with different signs, and this additional cost is not taken into account by straight-forward solutions. Is it possible to somehow exploit this effect and construct a challenge? Or maybe prove that this effect does not matter for some reason...Upd: in russian thread people say that it does not matter, since if we take some element with "+", it is impossible to take some next element equal to this one with "-". I wonder how many people actually thought about it during the contest...
•  » » » 6 years ago, # ^ |   +7 If we choose signs greedily, -x will never appear after x.
•  » » » 6 years ago, # ^ |   +5 Well, if you have multiple elements with same absolute value, in optimal solution they will have minus sign until some point and plus sign after that point. So there will be no inversions between them.
•  » » 6 years ago, # ^ |   +16 Well, another reason that this task is not good for E is that the following "stupid" solution passed: Initally make all x[i] >= 0. For i = 1 to n: if we change x[i] to -x[i] and the answer goes better then do it. It will WA on test 11. But if we do the step 2 twice, it can pass the system test: 4673192
•  » » » 6 years ago, # ^ |   0 Is it actually correct solution?
•  » » » 6 years ago, # ^ |   0 If in step 2 we take "answer does not goes worse" instead of "answer goes better" then we even don't need to repeat this step twice)
•  » » » 6 years ago, # ^ |   0 And why does it WA, when we do it just once?
•  » » » » 6 years ago, # ^ |   0 Because it's totally wrong. We could need to change several x[i], which would make the answer larger, and then change several other ones that would make it smaller. It just shows the weakness of tests.
•  » » » 6 years ago, # ^ |   0 Someone can prove, that if there are no i, such that if we change ("update") x[i] to -x[i] the answer goes better, then we could'n improve the answer.This is such a natural type of statement, but in this particular case it's hard to believe in it. Of course, there is no guaranty, that after step 2 in our solution there are no such x[i] that we can update.The idea of proof: Call the operation "inverse" of x[i] is multipling it by -1. Assume the contrary: there are no such i, that if we inverse x[i] the answer goes better, but we could improve the answer inversing number x[i] = a and x[j] = b to -a and -b (in a general case we have to inverse k numbers, but for more clearness we take k = 2). Let us consider numbers ka and kb. ka = (number of inversions in initial array — number of inversions after inversing a to -a). The definition of kb is analogous.By assuming ka >= 0 and kb >= 0. Put the number of inversions = inv Case 1: ka > 0. When we inverse a and b, inv_new = inv + ka+kb. But we don't take in account pair (a, b), that can be "bad" (i.e. this pair is inverse), but (-a, -b) is "good". Then the number of inv_new >= inv + ka + kb — 1. Hence inv_new >= inv. A contradiction Case 2: ka = kb = 0. Let inverse a and b not simultaneously, but one by one. Then we can choose the correct order of chain of inversions (we inverse a, and then b OR b and then a), so that inv_new >= inv (Note, that a > b (elsewhere we have a contradition the same way as in case 1). Assume, that -a < b. First inverse a. inv_new = inv + ka = inv. Then inverse b. Since the pair (-a, b) is already "good" (and (-a, -b) too) and kb = 0, we have inv_new = inv. Again a contradiction. If -a < b is false then we will first inverse b, and then a)
•  » » » 6 years ago, # ^ |   0 I did step 2 just once (with "answer gets better") and it passed. And I think that it is correct. Reason:We don't care about equal elements, as discussed here http://codeforces.com/blog/entry/9056#comment-147490 .If we have Pa, Pb;|Pa| > |Pb|, then |Pa| > |Pb| ≥  - |Pb| >  - |Pa|, so if we change Pb to  - Pb, the "inversness" (whether they made inversion, or not) of these two numbers doesn't change. Thus inversness of two numbers can only be changed by inverting greater of them. That means that effects of inverting numbers on total number of inversions are totally independent. So we can do it greedily.
 » 6 years ago, # |   +4 while(true){ System.out.println("THANKS SEREJA"); } contest very-very good.
 » 6 years ago, # |   0 A question: when i run problem A(in Div2) in custom test, it works fine without error but when i submit it, it shows runtime error! what is wrong?
•  » » 6 years ago, # ^ |   0 In these line  String line=sc.next(); You only read one char and set it to the line string ...So the length of line string is 1 ...Run-time Error occur when you try to divide a number by zero or accessing a index less than zero or more than the size of array ...Here when index goes more than the 0 Run-time error occurs ...  for(int i=0;i
•  » » » 6 years ago, # ^ |   0 it works fine on netbeans, next() read a string. i will try to find why index goes less than zero or more than length,thanks,
•  » » » » 6 years ago, # ^ |   0 It reads one string but until the space .The numbers are separated by space so it reads only one number.You can easily check it by printing.Anyway you need better debugging , Asking such questions may consider as spamming here.
 » 6 years ago, # |   0 Can somebody hint towards the solution for Div 2 C?
•  » » 6 years ago, # ^ |   0 Hint: Round down all elements and then see how many you need to round up.
•  » » 6 years ago, # ^ |   0
 » 6 years ago, # |   0 Can anyone help me on Div2 B Why my code outputs negative numbers in Test#11 4670950
•  » » 6 years ago, # ^ | ← Rev. 3 →   0 I think sorting is not stable. bool f(pii i, pii j) { return (i.first
 » 6 years ago, # |   0 A friend of mine made a correct submission for Div2 B during the contest but he found out it was "Skipped". What's wrong? This is quite unfair.Here's the link: http://codeforces.com/contest/352/submission/4665780
•  » » 6 years ago, # ^ | ← Rev. 2 →   +1 He made another submission on the same problem afterwards. For every problem, only the last submission is counted, and every submission before it (that doesn't get compilation error or WA on sample tests) gets -50 pts.
•  » » » 6 years ago, # ^ |   +5 He did make a submission later but it was post-contest. During the contest that was his only submission. You can clearly see that here: http://codeforces.com/submissions/mahmouder
•  » » » » 6 years ago, # ^ |   0 Oh, right. Sorry, I didn't notice. I have no idea why, then.
 » 6 years ago, # |   +23 Why do contest writers offen misspell "standard"? I'm not blaming anyone, I'm just curious.
•  » » 6 years ago, # ^ |   +18 Because of Russian word "стандарт" which means the same.and "т"is usually transliterated as "t"
•  » » » 6 years ago, # ^ |   +23 Oh, I understand. Thanks.
 » 6 years ago, # |   0 When will the rank be updated ?
•  » » 6 years ago, # ^ |   +1 its updated 10 minutes back :)
 » 6 years ago, # | ← Rev. 2 →   0 hey, can anybody tell me why my submission 4674576 for Div-1 A is giving wrong answer? thanks in advance.
•  » » 6 years ago, # ^ |   0 What is your algorithm? It would be easier to identify the source of the error then.
•  » » 6 years ago, # ^ |   0 got my mistake, thanks!
 » 6 years ago, # |   0 I wonder why this input (n = 2000 and 4000 zeros) was unsuccessful in hacking this code : 4663057, because the size of array in this code is 2010!
•  » » 6 years ago, # ^ |   +5 Array overflow doesn't necessary mean wrong answer or runtime error. It means undefined behaviour.
•  » » 6 years ago, # ^ |   0 But in my case , it correctly gave a runtime error : 4662420
•  » » » 6 years ago, # ^ |   0 Exactly. It "doesn't necessarily mean WA or runtime error". It's undefined behaviour.
 » 6 years ago, # |   +16