### Sereja's blog

By Sereja, 7 years ago, translation, ,

Hello everyone!

Codeforces Round #179 will take place on Thursday, April 11th at 19:30 MSK. This is my fifth Codeforces round and I hope not the last.

I'd like to thank Gerald 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.

Problems point values for 1 division will be standart. For the 2 division it will be: 500-1500-1500-2000-2500.

Gl & hf ! :)

Contest is over. I hope that problems vere interesting for you.

Division 1 winners:
1). marcina007
2). yeputons
3). gawry
4). KADR
5). enot.1.10

Division 2 winners:
1). goie
2). Koblyk
3). Beriand

• +232

 » 7 years ago, # |   -22 I can't wait to participate in the contest！！！！ I love codeforces!!!!
 » 7 years ago, # |   -46 Good luck everyone
 » 7 years ago, # |   -27 unfortunately I cant participate in this round but seems a great contest like all contest that sereja have prepared.
 » 7 years ago, # |   -36 good luck & good rating changes .
 » 7 years ago, # |   +21 than contests author is Sereja my rating decreases, I hope that today this tradition will be destroyed;))))
 » 7 years ago, # | ← Rev. 2 →   -51 Ignore this please. It wronged my meaning. . .
 » 7 years ago, # |   -13 Where is score distribution?
•  » » 7 years ago, # ^ |   +2 If there is any change in score distribution it will be mentioned before the contest. If not then the score distribution will be traditional.
•  » » » 7 years ago, # ^ |   +3 Thank you. :)
•  » » 7 years ago, # ^ |   -8 here.
 » 7 years ago, # |   +2 "I strongly recommend you to read ALL the problems" — it does remind me of problems with close difficulty :P
•  » » 7 years ago, # ^ |   +11 sereja tells this before every contest written by him.
•  » » 7 years ago, # ^ |   +4 Its hard to form problems with 7 different difficulty levels, where the only assessing tool for difficulty level is experience!
 » 7 years ago, # |   +8 Great contest. Good Luck
 » 7 years ago, # |   +20 very good system test speed thank you codeforces
 » 7 years ago, # |   0 Thanks for ultra-fast system testing :)
 » 7 years ago, # |   +8 Very nice and balanced problem set...One of the best contest I have ever participated in...Thanks
 » 7 years ago, # |   +8 good problems.thanks.
 » 7 years ago, # |   0 Hello, during contest I had trouble with C and got TLE status...I tried to use a map to group the number of times each query needed to be used and did a double for loop to update answer...I also think that some sort of Range Query algorithm would help, but I can't yet implement one. Can someone help me and describe a possible solution for C Div2? Thanks in advance,Bruno
•  » » 7 years ago, # ^ | ← Rev. 2 →   -12 Use Binary Index Tree or Segment Tree.
•  » » » 7 years ago, # ^ | ← Rev. 3 →   0 I used delta encoding twice, less code + better complexity.one on the number of times that each operation executed, and the other to compute the new array
•  » » 7 years ago, # ^ | ← Rev. 2 →   0 Or you can just use idea described in this editorial (problem C, two last paragraphs). That problem also was about intersection the segments.
•  » » 7 years ago, # ^ |   0 My submission id is:3509624and this user's submission seems very alike with mine, can you please state what changes did he used and why he got AC?3511139Thanks :)
•  » » 7 years ago, # ^ | ← Rev. 3 →   0 There exist O(N) solutions.Considering each operator (Li,Ri,Di),we add a[Li] with Di and minus a[Ri+1] with Di,then the sum of a[1] to a[i] is the change of ith number.We can count the times of each operator in the same way.
•  » » » 7 years ago, # ^ |   0 So considering 1st example of the statement, how can we apply that approach? If we add + d to left element and subtract d from right element, how can we find the updated array?3 3 3 1 2 3 1 2 1 1 3 2 2 3 4 1 2 1 3 2 3Array is 1 2 3...1st query is 1 2 1, so array stays now 2 1 3 (?) and so on? :/
•  » » » » 7 years ago, # ^ |   +5 We should calculate the times of each operators first. For each [xi,yi],add 1 to b[xi] and -1 to b[yi+1] The sum of b[1] to b[i] represents the times of ith operator. Multiply each times to corresponding Di and then apply the method above.
 » 7 years ago, # |   -22 Thanks a lot for this hard contest. Both of my codes for problem A and C got "Pretest Past" but now both of the are Red! Also Thanks for this fast system test.Now I get that an unrated user won the contest again!
•  » » 7 years ago, # ^ | ← Rev. 2 →   +5 what's your problem with them? I can't understand your wondering.
 » 7 years ago, # |   -15 Great contest!Thanks to Sereja and Gerald!
 » 7 years ago, # |   +2 Nice problems overall, I really like the idea behind the solution of problem D, very clean, although it was an odd round for me I solved A, C and E.
 » 7 years ago, # | ← Rev. 3 →   0 I failed problem C (div 2) and I cannot find where my solution went wrong. (I'm using segment tree). May someone help me ? Submission.
•  » » 7 years ago, # ^ |   +1 I didnt really read your code but when i too got WA11 i had an error in vector/array's ranges. Do you use N and M sizes correctly?
•  » » » 7 years ago, # ^ |   0 Thanks a lot Dixtosa :-) What a silly mistake :-(
 » 7 years ago, # |   0 My solution for problem A gets WA on the codeforces server but on my PC it's giving correct output for that case. Why is this happening? Could someone please help. Here's the code: http://www.codeforces.com/contest/296/submission/3511959
•  » » 7 years ago, # ^ | ← Rev. 3 →   0 In my blog you can find more about it. I faced this problem a few times. Here is a conversation about how to avoid this problems.HF & GL!
•  » » 7 years ago, # ^ | ← Rev. 2 →   +1 int main() { cin>>n;rep(i,1,n) { int x; cin>>x; num[x]++;}rep(i,0,1010)//1010 is larger than your array's size, I change it to 1000 and your program output "NO" in "Custom Test"{ D.x=i; D.n=num[i]; if(D.n) v.pb(D);}
•  » » 7 years ago, # ^ |   +6 rep(i,0,1010), but #define MX ( 1000 +3 ). I think this is the reason.
•  » » » 7 years ago, # ^ |   0 Thanks a lot guys. Really silly mistake, should've been more careful :(
 » 7 years ago, # |   +1 I tried to hack a code in problem C, which was plain brute force. I wrote a hack gen here but i got the error "FAIL Input can't start with empty line, but the first line is empty [validator wfval.exe returns exit code 3]" Can any one tell the mistake so that I wont repeat it.
•  » » 7 years ago, # ^ |   0 Are you sure you've uploaded in source file field and not in input file field? I've got such error because of this previously and i see your source code starts with an empty line.
 » 7 years ago, # |   0 Tried to solve Div2 with DP lol. So much wasted time in debugging, and then saw the simple way :(. But this is one of those bad solutions that I am proud of http://codeforces.com/contest/296/submission/3514056
 » 7 years ago, # | ← Rev. 2 →   0 Div2 Problem C: I used the binary indexed tree approach...my code runs fine till testcase 11... Can any1 help me find my mistake? here's my solution http://www.codeforces.com/contest/296/submission/3512783
 » 7 years ago, # |   +89 Thanks a lot for the contest! But:Why didn't you make an illustration in Div 1 problem D?It was annoying to read that text passage about sets/subsets, without an illustration showing what it's all about.Even better (= more polite to contestants) would be to give a sample test like "3 3" or "2 3" and show (as pictures) all the valid caves in that pad.
•  » » 7 years ago, # ^ |   +51 Next time I will note your advice. Thanks :)
 » 7 years ago, # |   +3 could anyone please provide english version of the Ideas to problems page? If I click on translate button, only problem A is being translated to English, all other problems solutions are shown in Russian itself (they do not get translated). Thankyou.
 » 7 years ago, # | ← Rev. 3 →   0 Can anyone please explain the logic behind this solution of problem B of Div 2 ? I have having hard time understanding the dp state.Thanks!
 » 7 years ago, # |   0 Can someone explain solution to probl C div 1 / E div 2 in more detail please ? Thanks!
•  » » 7 years ago, # ^ |   +13 At first, note that we have only 2 type of people, let us call them "small" and "big" according to their weight. Assume some moment (state), then it can be defined by the number of "small" and "big" people on one shore and the position of the boat (the bank of the river it is adjacent to). Let the states be the vertices of the graph. It is understood that we can get from state to state with the help of the boat transportations. Therefore we have the directed (or undirected, it doesn't really matter) edge from one state to another if we can get from one to another by exactly one traversal. Obviously, the initial state is {0; 0; 0} (assuming we count people on the opposite bank, 0 corresponding to the initial bank, 1 — to the opposite), the final state is {n1; n2; 1}, where n1, n2 — the number of "small" and "big" people respectively.So the solution can be easily implemented by using breadth-first or any algorithm of finding the shortest path in the graph (because of quite small constraints). Moreover, you don't have to build the graph explicitly, you can do it implicitly (like me , for instance (: 3513759).The only thing you might still not understand is how to count the number of various ways to gain the minimal answer. Let us count in how many ways we can choose i people from x "small" ones and j people from y "big" ones. Obviously, that equals to C(x, i) * C(y, j), where C(n, k) = n! / (k! * (n - k)!). In such a way you can maintain another array that counts the number of possibilities and change it when you find the shorter path (assign the new value) or another path of the same length (add to the previous).Hope I made it at least a bit more clear to some contestants (:
•  » » » 7 years ago, # ^ |   0 Great. Many thanks!
•  » » » 4 years ago, # ^ | ← Rev. 4 →   0 Can someone please explain how we can have 72 ways for the following case?5 25050 50 50 100 100The minimum number of rides required are 3. My DP code(12225775) gives 46 ways and I have calculated it by hand as well giving the same answer. The possible moves are — Move 3 small people and bring 1 small person back — C(3, 3) * C(3, 1) = 3 Move 1 large and 1 small and bring 1 small back — C(2, 1) * C(3, 1) * C(1, 1) = 6 Move 1 large and 2 smalls and bring 1 small back — C(2, 1) * C(3, 2) * C(2, 1) = 12 Move 1 large and 2 smalls and bring 1 large back — C(2, 1) * C(3, 2) * C(1, 1) = 6 Move 1 large and 3 smalls and bring 1 small back — C(2, 1) * C(3, 3) * C(3, 1) = 6 Move 1 large and 3 smalls and bring 1 large back — C(2, 1) * C(3, 3) * C(1, 1) = 2 Move 2 larges and bring 1 large back — C(2, 2) * C(2, 1) = 2 Move 2 larges and 1 small and bring 1 small back — C(2, 2) * C(3, 1) * C(1, 1) = 3 Move 2 larges and 1 small and bring 1 large back — C(2, 2) * C(3, 1) * C(2, 1) = 6 After either of these moves, all remaining on the left side are transported together to the right side in 1 ride.The total comes out to be 46. I am unable to find any other case. Can anyone please point out my mistake?UPD : Found the mistake. Was only considering cases in which a single person comes back.
 » 7 years ago, # |   +12 Two coders form Poland in top 3! Nice to see :)
•  » » 7 years ago, # ^ |   +11 Although one of them is having relations with the German oppressor!
 » 7 years ago, # |   +8 Screencast of me solving this round.
•  » » 7 years ago, # ^ |   +8 Thank you a lot :)
•  » » 7 years ago, # ^ |   +3 What program do you use to test it on the sample tests?
•  » » » 7 years ago, # ^ |   0
 » 7 years ago, # |   +4 Could you please write an English solution?
 » 7 years ago, # |   0 I can't understand the statement of porblem c in div2 , what's the query stands for ? How to explain the sample tests ?
•  » » 7 years ago, # ^ | ← Rev. 4 →   +3 Explanation of first testcase : Initially , the elements of array (a) are : a[1] = 1 , a[2] = 2 , a[3] = 3.We have three operations : operation 1 : 1 2 1 : increase every element a[i] with 1 <= i <= 2 by 1operation 2 : 1 3 2 : increase every element a[i] with 1 <= i <= 3 by 2operation 3 : 2 3 4 : increase every element a[i] with 2 <= i <= 3 by 4and three queries : query 1 : 1 2 , query 2 : 1 3 , query 3 : 2 3We have to execute the queries. by (a,b,c)--->(a',b',c') I mean the new state of the array after performing some operation.Query 1 asks us to perform operations 1 and 2. (1,2,3) ---> (2,3,3) ---> (4,5,5)Query 2 asks us to perform operations 1,2 and 3.(4,5,5)--->(5,6,5)-->(7,8,7)-->(7,12,11)Query 3 asks us to perform operations 2 and 3. (7,12,11)--->(9,14,13)--->(9,18,17)
•  » » » 7 years ago, # ^ |   0 got it! thank you!
 » 7 years ago, # |   0 What a pity! I just had a very little bug in Div.2 Prob A , or I would get a lot more Rating!
 » 7 years ago, # |   +2 How I wish there is solution in English?
 » 7 years ago, # |   +5 solution written in Chinese
•  » » 7 years ago, # ^ |   0 Looks good to me. At least, much better than the 'official' one.