Hello Codeforces!

I am glad to invite you all to participate in **regular** Codeforces Round #352 that will take place on 11 May, 19:35 MSK. This will be my first round, so I hope that it will be interesting for you guys. There will be 5 problems for each division, and contest will last 2 hours.

Round wouldn't take place without the help of GlebsHP, I am very thankful for his great help. I also want to thank to Zlobober, winger, AlexFetisov, ikbal and ykaya for testing problems, to hasanb for inspiring me in a problem. I got great help and wise advices from all of them so this is their round too as much as mine. Of course I want to thank Mike and all others who puts his effort into Codeforces and Polygon systems. I don't know what we would do without this great platform.

**UPD1**: Score distribution:

Div. 2: 500-1000-1500-2000-2500

Div. 1: 500-1000-1500-2000-3000

**UPD2**: I will post editorial as soon as possible, thank you for your patience. Congratulations to winners!

**Div.1 winners**:

2-W4yneb0t

3-jcvb

4-Merkurev

5--XraY-

**Div.2 winners**:

5-tjandra

**UPD3**: Editorial is now available.

is it rated?

I hope it will be rated :D

Div 2 冠军是我的!

但是我错了...............

There is wrote : " As they told me round will be rated ",how do you think ? it is rated or not?

But here also it is written "but do not be hesitated to ask again for just to be sure.". harunsami simply took the advice, everything is correct.

I didn't say that this is wrong,but it is clear that author doesn't know surely if contest is rated..To my mind he will update as soon as he find the answer.

Dude you surely don't understand sarcasm!

I have piano lessons on Sundays and Wednesdays at 07:30. 99% of CF rounds are on Sundays or Wednesdays at 07:30. I'm so

~~un~~lucky!!So write the alphabet on the piano keys and write code while playing music. That will be the

realartYou mean coding with new language?

Piano++or something with music when coding?Nice idea for another vim plugin.

Good luck and have fun!

I guess it's first Turkish round

Yes, It's first Turkish round.

Hope to see interesting problems and good luck to everyone!

I'm sure you will see.

Asin bayraklari!

!iralkaryab nisA

Bugun sinavvv erken kalkin cocuklar elimizde taze bilgisayarlari, ustumuzde yeni T-shitleri. (Turkish song) :)

Put The Flags To The Balcony

Drink Application :D!odd(CF Round #) )And also thanks to me, who prepared the meals for contest team.

lets hope dynamic score distribution for more interrseting xD

Please, read this

I hope, that statements will be short like this blog.

I hope, the problems won't be like adamant's.

It is also first turkish round in CF =)

" As they told me round will be rated, but don't be hesitated to ask again for just to be sure. "ok , is it rated ?

joke apart , good luck and have fun :)

How Long Does this Contest take ?

2 hours

i hope your rate reach to this number of seconds my friend

that is 7200000 milliseconds

This contest will be very exciting. I hope i will be successful.

NE MUTLU TURKUM DIYENE !!!!

Onlar konusur Turkler yapar

i m looking forward to join contest

I am seriously considering join the contest.

A

Regularcodeforces round these do happen every once in a while now don't they nevertheless i hope it's fun ^_^Why is my registration canceled automatically? So is it with Retired_MiFaFaOvO.

UPD:It says 522 people have registered, but when I clicked into the page to see the registrants, I only saw 300+ people.I encountered the same situation last time.

I am back

Beresta ready for another crossover? Coz I am.

24 minutes to go! best site <3 love you codeforces! <3

Sa beyler

We are still waiting for score distribution.

Good luck everyone ... Try to do your best!

На этом соревнование количество турков зашкаливает.

I don't like "WA"...

I believe TLE is worst, because you probably need to write a completely different algorithm to get AC, whereas in the case of a WA, you may find a bug quickly and then solve the problem.

Can someone give me a hit to solve DIV2.D?

How about no.

I think you shouldn't ask for that during the contest...

yes, i haven't participated of this contest, my question is for after contest :D

The score distribution for Div.1 today should be 250-250-30000-30000-30000 :P

I should say the same for Div2 :P 250-250-25000-25000-250000000

Did pretests for Div1 D really not have a test for n == 1?

I had a solution that printed -1 in such case instead of 0, but, luckily, fixed it.

I just know div2 C didn't have test for n==1 cause I hacked someone....

Passed pretest of Div2C after ages but I know it's gonna fail.

Testcase

0 1 0 2 0 0

1

0 3

Answer — 4

I am going cry in the corner of my bathroom. ;(

I think many solutions of C will fail today.

Let's hope so. Anyways, my rank will be higher(in magnitude) because I solved A and B with slow speed.

And you were right.

OMG Nooooo I forgot. There can be only one bottle :( Now I realise why my solution was failing Div2 C on TestCase #3

Test 3 might be something else(maybe precision or maybe maximum distance of bottle from both Adil and Bera was equal). But n=1 was definitely not in pretests.

No, there was no pretest for N=1. I did some mistake which passed pretests, though I corrected it later.

Oh... that case fails me too. ;(

I have answer 4 for this test, but failed test 25.

Looks like my approach was wrong. :)

Such interesting contest, so many problems were solved by everyone

Can anybody talk about how they did Div1C?

UPD2: never mind, misread problem statement was sure that f(i,j) = gcd(... a[i — 1], a[j + 1] ... )

UPD: it works because all a[i] different__That's just stupid...

Worst feeling in the world: "Contest finished reload page" while pressing the submit button (no it didn't count)

Even worse feeling, when you submit that solution after the contest and it says

"ALL TESTS PASSED"That would be a mixed feeling between "man I'm awesome" and "f*** this **%* ** 12#$* @!#*!@% !*@#( #@!"

I hate it when I finish my solution to Div2 C literally seconds after the finish of the contest!!!. Also, it seems I haven't read the statement carefully, which is the reason why I started that late.

How to solve DIV2D?

Binary search the maximum height after removing k blocks, then binary search the minimum depth you can fill with k blocks. More or less.

It is sad I recieved so many WAs implementing the same logic. =(

Same, I just couldn't get the binary search idea to pass test 15.

Let's see if it passes the tests, but I just sorted the list and then searched from each end until I reached a value that was on the other side of the average (if I did this the difference was 0 or 1 depending on whether sum%n == 0) or you've removed too many blocks already, and then max-min

My solution is not using binary search. I am calculating final number where highest and lowest number end after k days, if they cross over answer is 0 or 1. 0 when total sum can be evenly distributed among n numbers, 1 otherwise.

For calculating final number where current highest ends, I keep on jumping to smaller non 1 frequency number if k is enough, else use up all of k and end up somewhere in middle (0 frequency number, this is breaking condition and at max happens only once). Maximum O(n) traverse.

Similarly calculated final state where lowest number end.

I'm starting to hate CF rating system; I don't think that fast solving first 2 problems and hacking a few other contestants really deserves a +130 rating change in Div1.

I hate hacking too :)) but I have to admit that understanding someone's code in such a relatively short time is really an admirable skill. Besides, it also helps careless coders realise their mistake. So, it is worth awarding.

The thing is that when you have a lot of people and only 5 problems, it's really hard to judge how well you perform (unless you performed exceptionally good/bad) so even though at times it might seem unfair, in the long run it is fair. And it really doesn't matter what kind of judgement system you use there will always be someone that will think it's unfair.

Does binary search work for Div2D?

I did two binary searches one for best low value and one for best hi value. I think a ternary search will also work. Do not have the approach though.

What was pretest 3 for Div2 C ?

I think it had only one bottle :

Testcase0 1 0 2 0 0

1

0 3

Answer — 4

Try this one

It works for this case :/

UPD: Sorry, seems like I have seen some combination of your comment and the one above it and I thought you ask for Div2D :(

Thats not even a valid input

The test case was :

107 50 116 37 104 118

12

16 78

95 113

112 84

5 88

54 85

112 80

19 98

25 14

48 76

95 70

77 94

38 32

Participant's output

1579.43936611

Jury's answer

1576.895607473206

Dont know why I failed this http://codeforces.com/contest/672/submission/17863191

If someone can explain why this answer is correct it would be great.

See the difference. It's huge(two point something).

When both A and B choose the same bottle , you should not just compare max_A and max_B but max_A + secondmax_B > max_B + secondmax_A

Most complicated solution I could see for

Div 2 Ahttp://codeforces.com/contest/672/submission/17850982

Please share, if anyone get idea behind it :D

Use to_string() to convert integer to string in C++11.

And the easiest one for Div 2A http://www.codeforces.com/contest/672/submission/17859081 (no offence to the writer though)

Hahahah thats just the best solution ive seen today :D

I did the same :) 17847805

How do you solve Div-2C ? Anyone. Thanks.

Dynamic Programming..

state (index,adil,bera)

100000*2*2

adil and bera represent if they went first time or not..after that both start at bin cycle so no problem

What if the first bottle to pick is not the same as the first bottle on the input?

Could you post a link to your solution on Ideone ? Thanks.

Deep down I knew it was Dynamic Programming :/ But I couldnt figure it out.

sighLets us consider there is only person.

After picking a bottle and throwing it in bin, then for all other bottles distances will be 2 * distance of that bottle from origin because you will start and end at origin after throwing each bottle. So first of all calculate sum of distance of all bottles and multiply it by 2.

Then find the bottle which at has this value minimum (distance of bottle from person — distance of person from origin). Add this to answer.

For two people, you can think of it in a similar way.

I solved it greedy...

Notice, that when Adil or Bera get to the recycling bin, they always walk the path to the bottle

twice(it doesn't matter who is gathering bottlesafter the firstrecycled bottle).That is, imagine these are distances from bottles to the recycling bin:

distFromBottleToBin[0] = ...distFromBottleToBin[1] = ......

distFromBottleToBin[n- 1] = ...If Adil or Bera started standing right on the bottles

iandj, the total distance would be:2·

distFromBottleToBin[0] +2·

distFromBottleToBin[1] + ... +1·distFromBottleToBin[i] + ... +1·distFromBottleToBin[j] + ... +2·

distFromBottleToBin[n- 1].Since they are

notstanding on them you should add up additional cost of traveling to thei'th andj'th (closest to them) bottles:1·

distFromBottleToBin[i] +distFromAdilToBottle[i] +1·

distFromBottleToBin[j] +distFromBeraToBottle[j]Notice also that if Adil and Bera are further from all the bottles than the recycling bin, then we have to choose the closest bottle to either one of them and one of them will be doing

nothing.When you solve E ~5 mins after contest T_T

Oh My God!!! I got bluescreen before 5 minute the end!!!

Are you still using Windows XP?

I use Windows 10 and it also has bluscreen

We need some ice here.

Windows 10's blue screen is cool though

causes may vary but blue screen is the same :)

I am unluckiest person trying to hack the luckiest person !!!

check the return statementcode: 17850999

I dint understand. Could please explain ?

Should be "return false;" instead of "false;"

Actually, most compilers are smart enough to return false, if nothing is returned!

maybe function bool in default version always return false;

When would Editorial be published?

I was one semicolon away from finishing Div2C.

How can i increase my efficiency and accuracy in contests?

study?

Well, maybe not the best way to do it, but you can just participate in contests, read editorials and implement solutions. Also for div1 problems, if you feel ok with it.

How to solve C,div2 ? My idea was to sort the coordonates of objects and after that answer would be : ans += min (A,B),where A=Distance from Adil to recycling bin through bottle i and B from Bera.(for i=1, to n). But how to sort them ? I think that only the first two are important, 'cause after recycling one bottle, the coordonates of character will be changed to r0,r1.In this case , first element should be the closest bottle to Adil , the second the closest bottle to Bera(but the disstance from r0,r1 to it should be longer than from Bera to r0,r1); Is good this solution or not ?

Well the coordinates wont change to 0,0 but it will change to Tx and Ty which is the location of the recycling bin

OOPS!!Sorry , i spoke about first example.

Can some one give me the ideal path for div2-c sample test 2? I just can't figure it out...please.

I screwed up but I enjoyed div1-ABC a lot. Nice problems with fine difficulty. Keep my upvote muratt.

Thank you! It is very nice to hear this from you :D

When I saw " all ints starting from 1" I thought it meant...18 19 100 101 102...you know like all the ints starting

WITH1 I guess that's why I get stuck on gray but still it was a great round hope there will be more soon so I can return to green again :)Hated today's Div2 C so much. Wasted a lot of time trying to implement it in the first place, and then to overcome WA 8 (without succeeding); I wish I had spent that time on problem D.

The worst thing is that the approach to solve the problem was actually pretty much straightforward, but implementing it and taking all cases into consideration turned out to be very, very time-consuming.

System testing isn't over yet and it is like

Weak tests! this AC code fails on test 0 1 0 2 0 0 1 0 3 muratt can you take a look please.

Nope, this code gives 4.0000 and this is correct.

Bera takes the rubbish then goes to bin.

Right. Sorry, On my machine it gives 0.0000. I don`t now why.

Because this code has a portion where double value is printed with printf and in your codeblocks you have turned on c++11 flag. It is a common bug of codeblocks.

hi there! :o3

Can anyone tell me how he solved div1D? I really liked the task, but didn't have any idea how to solve it.

Test case 25. xD

41 too as I see

69 and 80 also

Is there any way to figure out what was different about 41? Codeforces only gives me a portion of the input.

I figured out why I got it wrong in my O(N) solution on case 41. This appears to be the first case where the distance between every point and the recycling bin is shorter than any point to either person. (Would've been a one line fix if I saw this in contest :/)

Wrong answer on test 50 -_-

Resubmitted C at final moment and got AC. Nice problems, my upvote for you muratt

Div2 C WA on test 80 :(

n > 26 costed me an AC, I'm so upset...

When your D gives less points than your B :D

even it gives .. :)

it is a risk to start contest from D.

why am i getting wrong answer ?!

17852756

thanks!

You need to print 6 numbers after comma.

accepted code

You can see the test it failed at the bottom of the page. Precision problems.

NOOOOOOOOOOOOOOOOOOOO! why ;_; . just for it :(((((((((((((((.

thanks i have to kill myself

56 more submissions and I would have made it :(

Whats the reason for wa @ test 25

Hey Guys, here is my code for div2-c . Can some body please help me?

What I do is 1>1st consider that either person A and B collect all bottles..

2> Consider point i to be starting point for person A. Then consider all points except point i to be starting point for person B. Now calcualte the sum of all these distance and check if it is minimum...

Did i Miss any case???

I didn't read your code. But your idea is O(n^2) right? For each point you check all other points. This was my innitial idea too, but there is a way to solve it in O(n), it's very similar to your idea, you just have to think a bit more.

I acutally created a segment tree for person A, and then iterated over distance of person B, combined their sum and checked the answer...There should be no problem with the Time complexity, I have missed some case or made some mistake...

when will tutorial be published?

No, they usually hide it :)

:)

Had a silly mistake in Div 2 B. Surprised (and sad), no one hacked this during contest :o :(

How to solve div2 D?

Nice problems, but I'd prefer C to be easier to implement, especially because D needs quite a long code too.

Actually my codes are ~100 lines for both. But as i see there are some quite long solutions.

What is the correct answer for this test to Div1 A?

My program returns 102 and I have been hacked with it.

102

My program returns 102 too and i got accepted in main tests

EDIT : solving by hand, answer is clearly 102, so we are both correct

OK, my program returns diffrent valuess running in Dev C++ and in online compiler so it's my mistake. Thanks.

According to your first hack based on previous code :-

The details of that hack

wrong answer 1st numbers differ — expected: '102.0000000', found: '200.0000000', error = '0.9607843'

Input: 100 0 0 100 0 0 2 0 1 1 0

Output: 200.0000000000

Answer: 102.000000000000

Time: 0

Memory: 4489216

[close]

Thanks for quickly system test and hopefully rating should be updated quickly.

Thanks

contest was good.

del

o.O

Can anyone please explain how to solve Div 1 D? I thought in the lines of HLD + DP, but couldn't find the correct approach.

I wasn't able to find any solution. I guess that once you solved the DP in N^2 or N^3 or something like that, the optimizations are not the big problem. What DP did you try to use?

I tried to do

dp(v) and then for each worker that has a pathu->v, I tried adding that cost plusdp(u), plusdp(i) for all childreniofvthat don't lie in the path fromutov, but then I realized that I'm missing a lot of paths that way. Then I tried a few more variations, without success.In the end, I couldn't find anything. The problem is that you pay each worker only once. If the cost of a worker was per road, then the problem would be easy. RMQ after HLD would solve it. Perhaps even a carefully implemented DFS + multiset would work, I don't know.

My solution is a lot like your solution. In stead of going u to v, we can use all paths u to k where k is in the path between u and v with same cost c. Then in optimal paths will not intersect. So we can calculate answer for all nodes subtrees. We will use segment tree contructed by workers. Each leaf will keep the value you said above, we can easily update them when we go to current node s parent. You can see detailed solution when editorial published.

The first and second places at Div2 from Uzbekistan. Go, go, go Uzbekistan!

I finished problem C in the last few minutes and now I have become an IGM! Thanks for the nice problems though I think C should be worth more points.

It should be worth 2250 points.

What about the editorial?

Nice problemset, thank you muratt :)

btw, why div_2 E problem only worth 2500 pts, not 3000 pts? imho the difficulty on div_2 E is far greater than div_2 D, maybe the author have some magic easy solution (?) i don't know.. waiting for editorials :)

In problem div2 C

why this submission 17859797 gets RTE?!!

Your comparison operator is incorrect. Yeah, copypaste sucks:

I think that Div1D is very good and interesting problem!!

First, I thought this problem need heavy data structure(ex. HL Decomposition, Link-cut Tree ....), but this problem need only segment tree with range add/min.

And I came back to redcoder! Thanks for this nice problem set.

Can Somebody help me about my solution ? 17880268 When i compile at my pc, it prints correct answer (at least for given examples). it doesn't print 0.000... like here. Thanks !