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

I can't wait to participate in the contest！！！！ I love codeforces!!!!

Good luck everyone

unfortunately I cant participate in this round but seems a great contest like all contest that sereja have prepared.

good luck & good rating changes .

than contests author is Sereja my rating decreases, I hope that today this tradition will be destroyed;))))

Ignore this please. It wronged my meaning. . .

Where is score distribution?

If there is any change in score distribution it will be mentioned before the contest. If not then the score distribution will be traditional.

Thank you. :)

here.

"I strongly recommend you to read ALL the problems" — it does remind me of problems with close difficulty :P

sereja tells this before every contest written by him.

Its hard to form problems with 7 different difficulty levels, where the only assessing tool for difficulty level is experience!

Great contest. Good Luck

very good system test speed thank you codeforces

Thanks for ultra-fast system testing :)

Very nice and balanced problem set...One of the best contest I have ever participated in...

Thanks

good problems.thanks.

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

Use Binary Index Tree or Segment Tree.

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

Or you can just use idea described in this editorial (problem C, two last paragraphs). That problem also was about intersection the segments.

My submission id is:

3509624

and this user's submission seems very alike with mine, can you please state what changes did he used and why he got AC?

3511139

Thanks :)

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.

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 3

Array is 1 2 3...

1st query is 1 2 1, so array stays now 2 1 3 (?) and so on? :/

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.

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!

what's your problem with them? I can't understand your wondering.

Great contest!Thanks to Sereja and Gerald!

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.

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.

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?

Thanks a lot Dixtosa :-) What a silly mistake :-(

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

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!

int main() { cin>>n;

rep(i,1,n) { int x; cin>>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];

}

`rep(i,0,1010)`

, but`#define MX ( 1000 +3 )`

. I think this is the reason.Thanks a lot guys. Really silly mistake, should've been more careful :(

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.

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.

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

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

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.

Next time I will note your advice. Thanks :)

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.

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!

Can someone explain solution to probl C div 1 / E div 2 in more detail please ? Thanks!

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

Great. Many thanks!

Can someone please explain how we can have 72 ways for the following case?

5 250

50 50 50 100 100

The 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 —

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.

Two coders form Poland in top 3! Nice to see :)

Although one of them is having relations with the German oppressor!

Screencast of me solving this round.

Thank you a lot :)

What program do you use to test it on the sample tests?

Some links: http://codeforces.ru/blog/entry/6785#comment-12392

http://codeforces.ru/blog/entry/6941

Could you please write an English solution?

I can't understand the statement of porblem c in div2 , what's the query stands for ? How to explain the sample tests ?

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 1

operation 2 : 1 3 2 : increase every element a[i] with 1 <= i <= 3 by 2

operation 3 : 2 3 4 : increase every element a[i] with 2 <= i <= 3 by 4

and three

queries:query 1 : 1 2 , query 2 : 1 3 , query 3 : 2 3

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

got it! thank you!

What a pity! I just had a very little bug in Div.2 Prob A , or I would get a lot more Rating!

How I wish there is solution in English?

solution written in Chinese

Looks good to me. At least, much better than the 'official' one.

please explain, in problem div-2/C why we need to declare first hash/prefix array of long long type.