Hi Codeforces!

We would like to invite you to participate in Codeforces Round #266 Div2, which will be held this Friday, September 12th at 19:30 MSK. As usual, Div1 participants can take part out of the competition.

Problems have been prepared by Antoniuk and me. It's the second round prepared by us, and we still hope it won't be the last.

We want to thank Gerald for helping to prepare this round, Delinur for translating the statements, and also MikeMirzayanov for Codeforces and Polygon.

It will be used a standart scoring: **500-1000-1500-2000-2500**.

Gl & hf!

**UPD**. Round has finished. Thanks for participating.

**UPD2** Congratulations to top-5 participants:

1) dominator_hza

2) Final_Battle

3) free_pascal

4) vanhanh.pham

5) NUOUN

**UPD3**. Editorial .

I really liked k-tree! Hope to see some more problems like that!

Brazil's ACM/ICPC First Phase will be held this Saturday, this contest came in a good time for a last preparation. Thank you.

it won't be 500-1000-1500-2000-2500?

no it will be :D

just a moment ago KaiZeR haven't show score...

i really shocked when see only 4 comments :D usualy it's in order of 50-100

how will be destiny of worse ?

He discovered a white color under the grey wow :D

but i don't think there is a negative rating he will just stop at zero :D

[UPD]He got negative rating now i'm surprised :DNo!! He has broken all the barriers!

Even before tourist could reach 3300, he has splurged to -37 ! Unbelievable!

[Rating graph of worse... ]

He/She has registered

In the last contest his/her rating changes was

`-48`

. tourist missed rating`3300`

for a single point in his last contest. Will worse touch the`0`

rating ???I don't think he uses Russian version

But he does speak Russian, you can see this from his comments

I think users didn't find any specific problem in the text of the blog entry or ... to talk! Everything was ok :)

Wow! tourist just finished in 22 minutes!

Where is scoreboard for out of competition participants?

There should be a check box to toggle on/off for unofficial.

Is there any problem in java compiler? Runtime error for me even in custom invocation, working fine in my computer. UPD- BigInteger function nextProbablePrime() giving runtime error on codeforces.

.

Really?

UPD. same in G++ 4.7 w/o C++0x

hard math contest !!!

sometimes easy math is very hard , how to solve B?

If you'll increase both numbers by more than 1e5, then product will increase by more than 1e10. But it is clear that you can get better answer, so you may check only all possibilities of increasing one of numbers by 0..1e5, and for every such possibility calculate required increasing of second number.

i did increase to sqrt(6*n), it's correct

Maybe I'm misinterpreting, but how would this method work for something like

1000000000 1 3000000001?

EDIT: Never mind, indeed misinterpreted.

2 3000000001

Thanks. This is better then the editorial.

how to solve D??

DP[i][j] — how many ways to solve first

ipoints while havingjopen segments.You have following moves at position i:

And for every possibility you should check that number of segments covering position i after such move is h-a[i];

Answer will be in DP[n][0] (you solved all points, all segments were closed).

Also there is an O(n) solution 7772910

Yes, and you can also improve naive DP[i][j] to something similar to your solution, that will also work in O(N), noticing that we should care about only few values of j for some fixed i (if j<h-ar[i]-1 or j>h-ar[i] then it makes no sense).

Thanks very clear explanation

A simple linear solution. Consider the sequence

b_{i}=h-a_{i}. If some twob_{i},b_{i + 1}differ by more than one, the answer is 0, since some two blocks begin or end in the same position.Otherwise the answer is the product of values

val_{(i, i + 1)}:b_{i - 1}=b_{i}+ 1, then we must end one of theb_{i - 1}blocks. This can be chosen inb_{i - 1}, soval_{(i, i + 1)}=b_{i};b_{i - 1}=b_{i}, then we can end any ofb_{i - 1}blocks that still continue at positioni- 1, and start a new block at positioni. Or we can continue all of the blocks. Soval_{(i, i + 1)}=b_{i}+ 1;b_{i - 1}=b_{i}- 1, we should begin a new block, soval_{(i, i + 1)}= 1;What does Val mean?

What is the meaning of val(i,i+1) here?

Imagine that ending a segment and starting a new segment is the same as putting a red border between two cells: see this picture:

The white cells must be covered by the segments [l;r]. Thus if $$$b_i \neq b_{i+1}$$$, we must either end a segment (if $$$b_i > b_{i+1}$$$), or start a new segment (if $$$b_i < b_{i+1}$$$). If $$$b_i = b_{i+1}$$$, we can either end a segment and start a new one, or do nothing.

$$$val_{(i,i+1)}$$$ is the number of ways to do that in each case. In the picture, $$$val_{(i,i+1)}$$$ corresponds to the number of ways you can put a red border between the $$$i$$$-th and the $$$(i+1)$$$-th columns. Note that you cannot put more than two red borders between the same two columns $$$i$$$, $$$i+1$$$.

Thanks :)

I think this time problem B was one of the hardest problem B's I have ever solved...

Yeah, I was confused about how to solve (

a+x)(b+y) ≥ 6nwherexandyare the number by whichaandbare incremented. I tried to solve this for most of the time and I couldn't concentrate on problem C because I couldn't solve B!Either x or y is small: just check all values up to million

A lot of us tried a greedy approach or maths, making it seem tough, but a brute force approach would have solved this.

As pointed out by I_love_Tanya_Romanova and Toxic in the comments, both numbers cannot exceed 1e5 (LeBron's idea) or sqrt(6*n) (AvadaKedavra's idea). You just check a or b for all possibilities from 0 to 1e5 or sqrt(6*n) and calculate the required increase of the second number.

I think this time problem B was one of the hardest problem B's I have ever not solved...

Ironically, though there were few solves, the tests for B seem to be pretty weak — my submission 7762305 was accepted despite failing on many many tests (any of the lines in http://pastebin.com/rP0u5f4t would result in WA) due to having > rather than >=.

The actual problem was pretty nice itself though — proving that the solution will run in time is not too simple or obvious.

Seems like there was some miscalculation of the problems' complexities :D

Thanks for this. I should not be happy for solving the C question for the first time. :(

Hard but nice problems!

Rank: 235 , best performance so far. :)

Biggest mistake that I made was locking all solutions when I did not have any intention of spending much time on hacking.

Solution B got hacked. Could not resubmit. :(

Probably will remain EXPERT for some time.

Congrats, I too had my best performance so far today! Solved E for first time! :)

can anyone tell me why this solution gives WA while it works for that case on my pc http://codeforces.com/contest/466/submission/7772471

Not sure if that's the cause but a thing I notice is you do not return 0 in the end of the function, so I suppose the returned value is undefined, therefore it may return true at some moment?

i donot get it can u plz explain more how can it return true?

Well you don't return 0 if the function doesn't find an answer? You know, a function must always return a value. Since you don't tell it to return 0 (false) it may return whatever it likes in theory :D

yes right but in that case i donot call the function

but that was the bug weired

That bug was the difference between me and div 1

You do call it. 6*11=66, while 7*7=49, so n>a*b, therefore you do call the function.

the contest effect sorry

Finally worse did it.

Congrats to worse for becoming the first ever white coder on codeforces !

Even though ratings have been updated, colors have not. I am a specialist with rating 1553. :P

I guess they are struggling with assigning white color to worse.

Looks like

`Exception in thread "RatingUpdater"`

:Dworse has broken the system :)

What happened to my account rating ? http://screencast.com/t/pdEJQN5CZu

Probably worse's today achievement completely distorted the global rating update system.

Me too... http://codeforces.com/contests/with/Tudor

I solved nothing but A this contest.

I've actually solved E(for the first time in my life) but made a simple mistake. In one of the lines, I used the variable which I use to count the number of tasks received till now instead of the variable that holds the number of task that is in question... Passed pretests but got WA in system tests :( I suspected that I'd get TLE in system tests but when I corrected that line I got AC...

Anyways... Let's look at the bright side.. I've solved my first E even though it's not official.

This is first time I solved problem E! :D And became candidate master! :D :D

At first I got many WA 3 times on problem 1, I thought that for sure I will become Specialist again (got Expert only in previous contest).

After A passed pretests, I tried C and again got WA 2 times... tried E and got TLE. Finally I tried different method and E worked, then turned out I had to use long long int in C and that passed pretests as well.

Edit: I previously asked about other solutions to E, but I found a very simple one now.

I am unable to guess why my code gives WA plz can someone help me find the bug .Here's my submission http://codeforces.com/contest/466/submission/7774444

Wow , nice submission id 7774444

It's a lucky number according to Codeforces Beta Round #84 (Div. 2 Only) :D

though, his submission unluckily got WA

It must have only been nearly lucky :(

Why is that so? I mean lucky !

So, apparently E had weak testdata. Or else, How did this solution pass? http://codeforces.com/contest/466/submission/7765318 I can break this solution with very easy testcase.

there are many question like this with weak tests... anyway after this time if i cant solve a problem efficent i will send a naive solution :|

Can you give one?

I think an input of the following type would work:

Basically, the idea is that we have a chain of bosses 50,000 employees long, with 500001=>50000=>...=>1, so 1 is the boss of everyone. Then, we have 25,000 documents. Each document we give to employee 50,001 and we ask if it reached employee 1. It seems like you're doing a linear search for each document. So your running time will be on the order of 50,000*25,000 = 1.25 billion operations.

Ah, you are correct. For some reason I assumed maximum height of tree as log(N + M).

I jumped to exactly 1700 in this contest. Now it appears that I am in some sort of bizarre limbo...

[UPD: Fixed now, as add1ctus said.]

You are a candidate master, but it seems that worse broke the rating system by getting negative rating (thus not fitting into the 0 — 1199 gray rank, but in a new color — white). Hopefully once it gets fixed you will be promoted to candidate master.

I see, thanks!

It seems, there is a bug in standings table: purple participant is impossible for Div.2.

There is a bug with the rating/rank system. He had 1472 rating before Round #266 and got promoted to purple after the competition. Check his profile.

What happened to phantom11's country-wise standings?

I couldnt understand the concept to B. Anyone?

If a >= sqrt(6n) and b >= sqrt(6n), then a*b >= 6n; in this case, do nothing. Let a be the smaller of the two input numbers, and b be the larger of the two.

One trivial solution is to increase b until the room is big enough. E.g. if a = 10, b = 11, 6n = 1001 (somehow): then the trivial solution is 10*101 = 1010. Then your "overflow" is at most a, which as we said was <= sqrt(6n). Let TRIVIAL be the value of this trivial solution, i.e. in this case, 1010.

Therefore, the optimal solution has "overflow" at most a. Suppose that the optimal solution is x*y, with x <= y (WLOG). Then x <= sqrt(6n) + 1, because otherwise, x*y > (sqrt(6n)+1)*(sqrt(6n)+1) >= 6n + 2sqrt(6n) > 6n + a >= TRIVIAL, therefore the solution was non-optimal.

What we have shown is: you are guaranteed that an optimal solution exists with

at least the smaller numberbeing less than sqrt(6n). It is possible that one of the two is larger, though, e.g. 1*6n = 6n. However, your goal is only to find the smaller number, through the following method.Fix w between 1 and sqrt(6n). For every w, let h be the smallest integer s.t. w*h >= 6n, i.e. h = ceil(6n/w). Keep track of the best value you've found so far. Then, you iterate through sqrt(6n) < 10^5 possible values of w, and for every such w, your computation is constant time, so your algorithm is linear in sqrt(6n).

Here is my code : http://codeforces.ru/contest/466/submission/7796449 In my computer and ideone.com http://ideone.com/6lt8wR it runned test 1 and give me 4 but on codeforces it give me 0 ??? Who can explain me ??

Similar is happening with me too. My submission gives answer as 2041 for input test case 2. However on ideone and my local compiler, answer is 1.