Rating changes for the last round are temporarily rolled back. They will be returned soon. ×

### HolkinPV's blog

By HolkinPV, 8 years ago, translation,

Hello, friends)

Soon is coming regular Codeforces round #171 for Div.2 participants. Traditionally Div.1 participants can take part out of the competition.

Again and again the problems were prepared by the familiar group of authors: Pavel Kholkin (HolkinPV), Igor Kudryashov (Igor_Kudryashov), Nikolay Kuznetsov (NALP) and Gerald Agapov (Gerald). Traditionally thanks to Michael Mirzayanov (MikeMirzayanov) for Codeforces and Polygon systems and Mary Belova (Delinur) for translating the problems.

UPD: score distribution will be not standard a little bit: 500, 1000, 1500, 2000, 2000.

We wish everyone good luck, successful hacks, high rating and good mood)

UPD2: the contest is over, we hope you enjoy it)

Congratulations to winners:

UPD3: the editorial will be published soon

• +136

 » 8 years ago, # |   +42 I love Russian thinking in preparing contest problems ,Hope short statements & easy English words . GL & HF
•  » » 8 years ago, # ^ |   -29 Согласен =)
•  » » » 8 years ago, # ^ |   -8 haha
•  » » » » 8 years ago, # ^ |   -8 ?
 » 8 years ago, # |   -20 Starting to prepare includes...
•  » » 8 years ago, # ^ |   +7 Instead of preparing them before every contest, I advise you to set all things in your default source of whatever compiler you might be using, so that when you create a new file( program ) you will have already the predefined code. It will spare you a lot of time.
 » 8 years ago, # |   +16 Hi everyone, I has just viewed dj3500's screencast: CodeForces #169 div2. I saw the "hightail" program and go to https://github.com/dj3500/hightail but I don't know how to install it. Can someone help me?
•  » » 8 years ago, # ^ |   0 I think it's a Java program and need to be compiled. Can anyone experienced in java compile it?
 » 8 years ago, # | ← Rev. 2 →   -14 i think we have good contest.don't you?
 » 8 years ago, # |   -27 Again and again only div2 contest :( .
•  » » 8 years ago, # ^ |   +15 I think that they want to increase the number of Div1 users, because Div1 contests make many users become div2 users.
 » 8 years ago, # |   0 Hope me can change the rating color to purple!!Keep Calm and type the code more quickly! the same to everbody! but, it seems that i got fever:(, It's feel terrible Now:(
 » 8 years ago, # |   -6 Hey guys, no hope for a late reg? Please! I was just 3 mins late
•  » » 8 years ago, # ^ |   0 well i was just a few seconds late, but i guess the show must go on
 » 8 years ago, # |   0 it sounds like 50216 is a popular number. (rng_50216)
 » 8 years ago, # |   +59 I was really surprised to see that E was identical with D from a past Div.1 round (132D - Constants in the language of Shakespeare). I just copy & pasted, commented out a single line, and got pretest passed...
•  » » 8 years ago, # ^ |   0 Can someone please give me a more simple example than test 10 of why my greedy approach is failing? http://codeforces.com/contest/279/submission/3248428I keep 2 counters, number of zeros and number of ones. I look at all groups of consecutive 0's and consecutive 1's. If such a group has size 1 , i increment the corrsponding counter, else, I increase by 2 the corresponding counter. In the end, the result should be min(number 1's , number 0's + 2), representing that either we erase all ones or try to convert all 0's into 1's and do 2 more operations at the end.Thanks !
•  » » » 8 years ago, # ^ | ← Rev. 2 →   +1 well i guess here is your problemsfor 1counter:if you have two blocks of 1 with more than 2 numbers seperated by only a number 0 (11011) you will only need to change the 2nd group into (11100) in 1 steps, so you get another block of number 1. to convert it you need 2 steps. so 3 in total.however, based on your solution, cause you have 2 blocks of '1' size 2, you need 4 steps. testing pretest 3, you luckily right because the number of '0'. but when they increase 1counter and 0couter by adding '100', your 1counter is far bigger than 0counter, so the ans must be based on 1counter.
•  » » » » 8 years ago, # ^ |   0 sorry for bad English
•  » » » » » 8 years ago, # ^ |   0 Gracias!
•  » » 8 years ago, # ^ |   0 This is not correct!!! contest will not rated,this is correct Copy & Paste haha Pfffffffffffffff
 » 8 years ago, # |   0 wow !!! so fast system testing :)
 » 8 years ago, # | ← Rev. 3 →   +1 E was easier than A, what a terrible contest !!! .... :o
•  » » 8 years ago, # ^ | ← Rev. 2 →   0 Is there any easier way to solve it rather than simulate the spiral per coordinate ? (Problem A)
•  » » » 8 years ago, # ^ |   +1 You can 'push' the given coordinates to the corner. Then handle the corner cases. Then it's just O(1) math stuff per query
•  » » » » 8 years ago, # ^ |   0 I suppose 'easier' meant faster. So calculating all the formulas was time-consuming, while writing simple emulation took 6 minutes only. (:
•  » » 8 years ago, # ^ |   0 So we learned the knowledge, and to grow in experience.
 » 8 years ago, # |   0 I wish every rating updates were as fast as the sysTests :)
 » 8 years ago, # |   +1 Am i the only one who thinks that final testing on the last few contests run much quickly than earlier ?
 » 8 years ago, # |   +24 Am I the only one who couldn't hack? I couldn't even see source codes.
•  » » 8 years ago, # ^ |   0 With Chrome I couldn't see either. Had to use IE for hacking.
 » 8 years ago, # |   +2 Could someone help me find out why my code for problem C is failing? Here is my code . It got WA in test 21.
•  » » 8 years ago, # ^ |   0 It must be a strongly tricky case, lots of submissions got WA in this particular case.
•  » » 8 years ago, # ^ | ← Rev. 2 →   0 that's a case like, 10 1 1 1 1 1 2 3 4 5 2 1 1 10 
•  » » » 8 years ago, # ^ |   0 My output is 'Yes'. Isn't it correct?
•  » » 8 years ago, # ^ |   +4 Try this 7 3 4 2 2 2 2 2 10 2 7 2 6 5 7 It must be three "Yes". And i have the same mistake like you have ->My Submission Even the the same line .. ^^
•  » » » 8 years ago, # ^ |   +4 Oh, now I can see what was wrong. Thanx.
•  » » » 8 years ago, # ^ |   +1 thanks bro...i can now see where i failed system testing hopefully now i can use this lesson to do better algorithms in future...
•  » » » » 8 years ago, # ^ |   +12 NP guys.I just want to be a nice person in CF but look my contribution ...
•  » » » » » 8 years ago, # ^ |   0 Sen kalbimizdesin bro...
•  » » » 4 years ago, # ^ |   0 Really helpful.... Thanks
 » 8 years ago, # |   0 I think one of the reason behind low solve of Problem D is Poor Description.. I have read it more than 5 times, still i haven't understood what is the problem !!
 » 8 years ago, # |   +12 what's the relationship between rng_58 and rng_50216?
•  » » 8 years ago, # ^ | ← Rev. 2 →   +123 rng_50216 is the child of rng_58 and peter50216.
•  » » » 8 years ago, # ^ |   -9 the last drop of ethic.
•  » » » 8 years ago, # ^ |   -10 lol :D :D
•  » » » 8 years ago, # ^ | ← Rev. 2 →   +6 and..which one is the mom ?
•  » » » » 8 years ago, # ^ |   +12
•  » » » » » 8 years ago, # ^ |   +9 No!My boyfriend is sevenkplus!
 » 8 years ago, # | ← Rev. 2 →   +5 Lots of solutions for D gave incorrect answer for the following test case:2 1 1Edit: My test is wrong. The numbers are distinct
 » 8 years ago, # |   0 I can't see what 's wrong with my solution to problem C Can anyone help me with that? submission : 3245705
•  » » 8 years ago, # ^ | ← Rev. 2 →   +1 Check test: 3 1 2 1 1 1 3Strange that it passes all the previous tests.
•  » » » 8 years ago, # ^ | ← Rev. 2 →   0 Very thanks. I found the bug; if we get another array for the size of good sequence which ends with "i", it would be ok!
•  » » 8 years ago, # ^ |   0 Input: 6 1 2 1 1 1 1 1 1 6My solution prints "Yes" and it seems to be ok, but your solution prints "No".
 » 8 years ago, # |   0 Can anyone explain Problem B (279B — Books)? This is how I understood the problem:We are given an array A and an integer t. We have to search for a "sub-array" of A whose sum of elements is at most t. The answer should be the maximum length of such a sub-array. However, I must have misinterpreted the problem. I have looked at some submitted solutions and they involve forming the sum of the first j elements of the array A and then substracting the elements A[k], A[k+1]... A[L]. Somehow two "pointers" j and k are involved which I do not understand. I'd be grateful if someone could explain this. Thanks.
•  » » 8 years ago, # ^ |   0 You interpreted the task properly (if by subarray you mean a substring). You can calculate the solution in a single pass through the array, such that when you are at the j-th position, you also store the minimum i such that [i..j] is the maximum substring that ends in j. What you do is add the j-th value to the current sum, and while the sum is larger than t, subtract the i-th value and shift i one space forward. After each step is done, check whether the current interval size is larger than the maximum recorded so far and you're done.Here's my code for that: 3240473
•  » » » 8 years ago, # ^ |   0 Your explanation is excellent! I first tried to solve it by searching for subarrays (substrings) [i..j] with maximal length and sum<=t by using two loops and got a timelimit exceeded, I guess since it results in O(n^2) runtime. Your algorithm is a clever idea with only O(n) runtime. Thank you PetarV!
•  » » » » 8 years ago, # ^ | ← Rev. 2 →   +3 You also could have done it in O(n*log n) by keeping d[i]=sum{a[1..i]} and for each j=1..n binary search for the largest k>=j such that d[k] <= d[j-1] + t.
•  » » » » » 8 years ago, # ^ |   0 I have already wondered why problem 279B (Books) had the tag "binary search" in the problemset list. I like that idea. Thanks sfarma_pietre!
•  » » » 6 years ago, # ^ |   0 Thanks! Really helped me too.
•  » » » 5 years ago, # ^ |   0 I don't get it, why does it works?
 » 8 years ago, # |   0 how can we solve problem D ? I gave a solution with complexity O((n^2)*(2^n)) but definitely it gets TL.
•  » » 8 years ago, # ^ | ← Rev. 2 →   0 at first my solution was O((n^2)*(2^n)) and than I used that every number is distinct for precompution and got O((n^2)*n) . so think about it...
•  » » » 8 years ago, # ^ |   0 You mean you got o(n^3) solution ?
 » 8 years ago, # |   +17 It's been quite a while since the contest ended. When will the editorial be published?
 » 8 years ago, # |   +7 The editorial is late... can some1 please explain E.. I saw many codes.. but i dont understand how they arrived at that solution...
•  » » 8 years ago, # ^ |   +3 +1 I used the greedy method to solve this problem,but i don't know how to use DP to solve. can some1 explain?
•  » » 6 years ago, # ^ |   0 hey how can I see solutions of other contestants.....
 » 8 years ago, # |   +10 It's been quite a while since the contest ended. When will the editorial be published?
•  » » 8 years ago, # ^ |   +10 Editorial please? Thanks!
 » 8 years ago, # |   +10 Please publish the tutorial quickly
•  » » 8 years ago, # ^ |   0 When is the editorial?
 » 8 years ago, # |   0 please publish the editorial as you said.
•  » » 8 years ago, # ^ |   +3 Comon guys, some of us are still very curious to see how dynamic programming applies to D and E.
•  » » » 8 years ago, # ^ | ← Rev. 4 →   +4 This is how I solved the problem, hopefully the reasoning is right For E using dp, Let a single move = addition of 2^k or 2^-k s = the binary string, s[0] being the first digit = the last character in the stringLet dp[POS][i] = minimum number of moves needed to get a string l such that l[0..i] exactly match s[0..i] and l[i+1 ..] = 0 Let dp[NEG][i] = (same as above) l such that l[0..i] exactly match s[0..i] and l[i+1 ..] = 1If s[i] == 0, then dp[POS][i] = dp[POS][i-1], since you don't have to make any additional move. For dp[NEG][i], we can either make our move from a [POS][i-1] state, where we have to turn all bits from l[i+1....] to 1, but leave l[i] =0, so this takes 1+dp[POS][i-1] (just a single move, note that a negative power of 2 turns all bits to the left to 1, but leave the right bits unchanged -> -2^k = 11111... 000..). Or, we can make our move from a [NEG][i-1], which means we have to turn the ith bit to 0. This we can do by adding a single positive power of 2, which means only 1 extra move. Thus. dp[NEG][i-1] = 1+ Min(dp[POS][i-1], dp[NEG][i-1])And for s[i]==1 case, similar reasoning. Base case -> dp[POS][0] = 0 if first bit is 0, 1 if first bit is 1, dp[NEG][0] = 1, because you still have to make the bits to your left =11111...EDIT: whoops, something is wrong with my reasoning.. Hold on... EDIT EDIT: k nvm, I was confused about something else. Hopefully someone can agree/point out mistakes?
 » 8 years ago, # |   0 When will the editorials of this round come out? The editorials of the next 5 rounds are already published. @admin: please prepare it as soon as possible.
 » 8 years ago, # |   0 Very good
 » 6 years ago, # |   0 Could you please provide the editorial.
 » 5 years ago, # |   0 tutorial please ?! really need it !
 » 5 years ago, # |   +2 Editorial -> when? please. Thnakyou.
 » 5 years ago, # | ← Rev. 2 →   0 Can someone tell me the logic behind this problem? 279C - LadderI've tried reading other people solutions but I dont understand properly.
•  » » 4 years ago, # ^ |   0 Vicennial Did you find it out? If possible, could you explain the solution idea?
•  » » » 3 years ago, # ^ |   0 As explained in the editorial , for each index you should findi) lowest index i where decrement occurs (most people implemented it as array moving right to left and noting index where a[i] > a[i+1])ii) largest index j(before that index) where increase occurs , (implemented as array from left to right noting most recent index where a[i] > a[i-1] )now for subarray [x,y] ,if most recent decrement for index x is 'i' and most recent increment for index y is 'j' then, if( i <= j ) then segment is a ladder 35071213
•  » » » » 3 years ago, # ^ |   0 Can you explain the logic please? :)
•  » » » » » 3 years ago, # ^ |   0 now for subarray [x,y] ,if most recent decrement for index x is 'i' and most recent increment for index y is 'j' then, if( i <= j ) then segment is a ladder.Explanation : think of it this way — if the segment is a ladder first all the increments should occur then all the decrements. eg 1 2 3 4 2 1Now for 'x' we look at the closest index on its right where decrement occurs . (say A) , Also for 'y' we look closest index to left where increment occurs say(say 'B') . Now A < B will only happen when the segment is a ladder . Try out some cases to verify this
•  » » » » » » 3 years ago, # ^ |   0 Got it.. Thanks! :))
 » 4 years ago, # | ← Rev. 3 →   0 Why am I getting WA in 19th test case for problem C ? Is there some extreme tricky case ? Here is my submission — Submission
•  » » 3 years ago, # ^ |   0 Consider the case, 4 1 2 1 1 2 1 4I also made the same mistake :P
 » 4 years ago, # | ← Rev. 4 →   0 You should have posted the editorial as the questions were good. Hope you do it atleast now. @HolkinPV
 » 3 years ago, # |   0 I don't know why but my code gets "wrong answer 19677th words differ — expected: 'No', found: 'Yes' " while running case #19 of Ladder problem.Could someone check for me? https://pastebin.com/RnuDmcCc
•  » » 6 months ago, # ^ |   0 Me too getting the exactly the same problem
•  » » 6 months ago, # ^ |   0 Consider the case, 4 1 2 1 1 2 1 4I also made the same mistake :P
 » 6 months ago, # |   0 Could anyone explain why my code is wrong. Means could anyone give a possible test case/explanation of why my code is wrong. Link of submission attached-> (https://codeforces.com/contest/279/submission/101634918)
•  » » 6 months ago, # ^ |   0 I think this case 1 2 1 1 2 1 might fail your solution. For this case, array brr will always have zero values since if the query is L = 2 and R = 5, the answer should be No while your solution might output Yes