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:

1) study_english

2) ipip2005

3) rng_50216

4) xiaolaoye

5) AllProblemAreNetworkFlow

**UPD3**: the editorial will be published soon

I love Russian thinking in preparing contest problems ,Hope short statements & easy English words . GL & HF

Согласен =)

haha

?

Starting to prepare includes...

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.

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?

I think it's a Java program and need to be compiled. Can anyone experienced in java compile it?

i think we have good contest.don't you?

Again and again only div2 contest :( .

I think that they want to increase the number of Div1 users, because Div1 contests make many users become div2 users.

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:(

Hey guys, no hope for a late reg? Please! I was just 3 mins late

well i was just a few seconds late, but i guess the show must go on

it sounds like 50216 is a popular number. (rng_50216)

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...

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/3248428

I 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 !

well i guess here is your problems

for 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.

sorry for bad English

Gracias!

This is not correct!!! contest will not rated,this is correct Copy & Paste haha Pfffffffffffffff

wow !!! so fast system testing :)

E was easier than A, what a terrible contest !!! .... :o

Is there any easier way to solve it rather than simulate the spiral per coordinate ? (Problem A)

You can 'push' the given coordinates to the corner. Then handle the corner cases. Then it's just O(1) math stuff per query

I suppose 'easier' meant faster. So calculating all the formulas was time-consuming, while writing simple emulation took 6 minutes only. (:

So we learned the knowledge, and to grow in experience.

I wish every rating updates were as fast as the sysTests :)

Am i the only one who thinks that final testing on the last few contests run much quickly than earlier ?

Am I the only one who couldn't hack? I couldn't even see source codes.

With Chrome I couldn't see either. Had to use IE for hacking.

Could someone help me find out why my code for problem C is failing? Here is my code . It got WA in test 21.

It must be a strongly tricky case, lots of submissions got WA in this particular case.

that's a case like,

My output is 'Yes'. Isn't it correct?

Try this

It must be three "Yes". And i have the same mistake like you have ->My Submission Even the the same line .. ^^

Oh, now I can see what was wrong. Thanx.

thanks bro...i can now see where i failed system testing hopefully now i can use this lesson to do better algorithms in future...

NP guys.I just want to be a nice person in CF but look my contribution ...

Sen kalbimizdesin bro...

Really helpful.... Thanks

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 !!

what's the relationship between rng_58 and rng_50216?

rng_50216 is the child of rng_58 and peter50216.

the last drop of ethic.

lol :D :D

and..which one is the mom ?

YuukaKazami?

No!My boyfriend is sevenkplus!

Lots of solutions for D gave incorrect answer for the following test case:

2 1 1

Edit: My test is wrong. The numbers are distinct

I can't see what 's wrong with my solution to problem C Can anyone help me with that? submission : 3245705

Check test: 3 1 2 1 1 1 3

Strange that it passes all the previous tests.

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!

Input: 6 1 2 1 1 1 1 1 1 6

My solution prints "Yes" and it seems to be ok, but your solution prints "No".

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.

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

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!

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.

I have already wondered why problem 279B (Books) had the tag "binary search" in the problemset list. I like that idea. Thanks sfarma_pietre!

Thanks! Really helped me too.

I don't get it, why does it works?

how can we solve problem D ? I gave a solution with complexity O((n^2)*(2^n)) but definitely it gets TL.

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...

You mean you got o(n^3) solution ?

It's been quite a while since the contest ended. When will the editorial be published?

The editorial is late... can some1 please explain E.. I saw many codes.. but i dont understand how they arrived at that solution...

+1 I used the greedy method to solve this problem,but i don't know how to use DP to solve. can some1 explain?

hey how can I see solutions of other contestants.....

It's been quite a while since the contest ended. When will the editorial be published?

Editorial please? Thanks!

Please publish the tutorial quickly

When is the editorial?

please publish the editorial as you said.

Comon guys, some of us are still very curious to see how dynamic programming applies to D and E.

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 string

Let 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 ..] = 1

If 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?

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.

Very good

Could you please provide the editorial.

tutorial please ?! really need it !

Editorial -> when? please. Thnakyou.

Can someone tell me the logic behind this problem? 279C - Ladder

I've tried reading other people solutions but I dont understand properly.

Vicennial Did you find it out? If possible, could you explain the solution idea?

As explained in the editorial , for each index you should find

i) 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

Can you explain the logic please? :)

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

Got it.. Thanks! :))

Why am I getting WA in 19th test case for problem C ? Is there some extreme tricky case ? Here is my submission — Submission

Consider the case, 4 1 2 1 1 2 1 4

I also made the same mistake :P

You should have posted the editorial as the questions were good. Hope you do it atleast now. @HolkinPV

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

Me too getting the exactly the same problem

Consider the case, 4 1 2 1 1 2 1 4

I also made the same mistake :P

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)

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