Hi everybody!

Codeforces round #247 for Div. 2 participants will take place on May 21 at 19:30 MSK. Traditionally, Div. 1 participants can take part out of the competition.

Problems have been prepared by me(Antoniuk) and Kirill Schetinin(KaiZeR). This is the first round prepared by us and we hope that you will enjoy the round.

We want to thank Gerald and Delinur for helping to prepare the round and MikeMirzayanov for Codeforces and Polygon.

**UPD**: Score distribution will be the next — **500-1500-1500-2000-2500**.

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

**UPD3**: Editorial.

**UPD4**: Statistics.

**Congratulations to winners!**

1) hzjsxxy

2) azariamuh

3) tonkosi

4) inutard

5) c.u.c.u.m.b.e.r

Gl & hf)

Ukrainian contests are always special , hope it will be a special one too

Wish luck for everyone :)

Antoniuk , your chart is quite interesting after you become yellow you drooped to gray then you backed again to yellow , can you tell what is the reason behind this?

I think he just share the feelings with gray coders :)

He's gray-friendly :D

He tried to draw a heart cardiogram.

He didn't drop to grey !?

1200 Exactly Nice catch

just for fun = =

Actually this is not rare :D

http://codeforces.com/profile/sillycross

Wow!! if Antoniuk was involved that will be definetly

awesome.Last contest that Gerald participated was Codeforces Round #104 (Div. 1), Since then, He is preparing contests...

Thank you, Gerald!

i am a little bit worried about the problem statement.

I hope the problem setter will have explanation for the first example for problem A.

Don't worry it's unrated for you :)

Sereja also comes from Ukraine. He is always setting very attractive problemset. :)

I don't know if it's only me, but the english translations are very bad. I was not able to comprehend problem E at all.

I can't understand russian version of problem's E statement, although Russian is my native language.

It looks like this problem much easier to solve than to understand.

I could not understand English statement, because it was not clear. After switching to Russian, failed to understand again. And I thought it is because I was not native Russian speaker. :(

I couldn't understand the statement of E.

It's not only you. For problems A-D the english translations were alright. For problem E, WTF?? I still don't understand what the problem wants us to do.

Problem D. There is no answer if m = 0 and d = 1

The statement says there is guaranteed to be a solution for given m, k. Which means that a test with m=0, k=1 will not appear.

what was the solution for problem D?

i think binary search + dp

If you try to find the formula for a given n, you will end up with something like (sum of binomials) = m. It can be solved greedily.

I think problem B should be 1000 instead of 1500 !?

Again, like other contests, a lot of newly registered participants (within 10 hours of the contest); but the worst of all is that the first person in standing, containing both div 1 and div 2, is one of those!

What is that mythical Test #9 in problem D? I can't pass it =\

It seems that D and E are way harder than normal for these contests. I solved E because I had code for R-B trees handy, which probably wasn't the expected solution.

Maybe your program writes "0"

That was indeed the case, but I wasn't using binsearch so my solution naturally got the zero. I don't understand the point of this, the goal is to solve the problem and not look for every possible corner case that has very little relation to the actual solution.

0 2

what about editorials?

Will be published soon after system testing.

What was the approach to solve problem C?

I used Dynamic Programming

Compute the total number of ways to break number n into summands which are <= k. Let it be S. Then number of ways to break n into summands which are <= d-1. Let it be R, these ways to break the number are "bad" and should not be counted in the final answer. Thus, the final answer is S-R.

No , I don't think that will give the correct answer in case when we take modulus along the way.

mod = 1000 ; Suppose final S = 1234 and final R = 999 ;

but when we will take modulo S%mod — R%mod <= 0 Which will give the wrong answer.

I gave just the general idea, modulus is the detail of implementation.

This is my first contest :) Hope I will get a high rating :)

I do not believe you.

Why did this solution pass systest?

Interesting part:

Interesting!

if s[i]=='4' then A[s[i]-'0'] is A[4]

strlen(s) works in O(n) time!

`scanf("%d %d %d %d\n",a+1,a+2,a+3,a+4);`

Any ideas on how to solve B for a much bigger N? First time i read the problem i thought n <= 10^5

I have solved it in O(N^2) using DP. I think it can't be solved faster. So, n could be somewhere around 2000.

What is the runtime (in seconds) for n=2000?

Same here! Wasted 5 minutes and then solved C before realizing n is always 5.

how this solution AC ?!!! http://codeforces.com/contest/431/submission/6671729

48 here same as '0'. Read this http://www.asciitable.com/

i don't mean that , i mean he made an array of size 4 and used index 4 !

Doing this results in undefined behavior. So, I guess he just got lucky.

Same solution for problem D got AC in MS C++ and WA in GNU C++.

6676019

6676015

Why? :(

As for your code, the behavior of

`X >> i`

is undefined when i = 64, for the behavior of`op1 << op2`

and`op1 >> op2`

is undefined if the op2 is negative, or greater than or equal to the length in bits of the op1. So, you can get AC in both MS C++ and GNU C++ by replacing`X >> i`

with`i < 64 ? X >> i : 0`

for example.Thank you, I got AC by calling the function with i=63 instead of 64.

I found that it's undefined even in MS C++...

Problem C should tell that the number must be positive or something like that. For example 17 mod 5 = 2 = -3. When you say print 17 module 5 I can print -3 too unless you specified that the answer must be positive. After 1:24 I got hacked and immediately submit another. which is now accepted but I lost a lot of point -50 and ~ -450 or -500 for timing.

the problem asked you to print the number of paths , how it can be negative ?

No, the problem asked me to print number of paths

module10^9 + 7.http://en.wikipedia.org/wiki/Modulo_operation

"The range of numbers for an integer modulo of n is 0 to n − 1."

Fair enough! My fault.

You can blame broken % operator in C++. But don't blame contest authors ;)

No! % operator works ok. I write my code in a way which the number could be negative.

I corrected it by replacing cout << ...; by cout << (... + 10..7) % 10..7;

That's what I did. I used long long and ( + 10....007) % 10...007 staff. If % operator was mathematically correct in C, there would be no need in jumping through hoops like this.

Wasn't problem A too easy to become a contest problem?!

Nice problems.... :)

Nice contest for me... :)

Hope to see you again... :)

Can someone please explain the statement of problem E ?

The subproblem can be formulated as this: You have an area of land, with h[i] being the height of the i-th section. You want to pour V liters of "rain" on this land (so that the water level is the same for each section that isn't dry). Find the resulting water level.

Now you have the initial heights, and a bunch of queries that either change the height of one section, or ask you to solve the subproblem for a given V.

When will the editorial be available??

Editorial

Can u explain Random task, bit more clearly.Not able to understand.

Is there a way to download the test cases, other than trying to "brute force" it by sending fake solutions? My solution to E fails on one single query on test #28, and all other queries are correct. Very suspicious...

Try writing big random test generator and brute checker function, and test your solution with it.

It seems far more productive that brute forcing tests.

Considering it works on all test cases except for one single query, I don't think I would be able to replicate that easily. Besides, I already did that last time I used the same data structure.

http://codeforces.com/contest/431/submission/6672763

http://codeforces.com/contest/431/submission/6672950

aren't these two solutions same ?

can someone explain me why this solution gets WA :6676798 my answer is : (all the paths using edges with weight k or lower) — ( all the paths using edges d-1 or lower)

Changed 6676977

i feel so stupid :| thanks

I like div-2-only contest because I have to compete with the second (or nth) account of the first-division people. No, it is a joke, lol. I don't like div-2-only because that.

Round Stats

The question A is like this game : Don't tap the white

good luck everyone...hope to seee some interesting problems :)