### muratt's blog

By muratt, 4 years ago, ,

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:

4-kalili

5-tjandra

UPD3: Editorial is now available.

• +338

 » 4 years ago, # |   +84 is it rated?
•  » » 4 years ago, # ^ | ← Rev. 3 →   -54 I hope it will be rated :D
•  » » » 4 years ago, # ^ |   -41 Div 2 冠军是我的!
•  » » » » 4 years ago, # ^ |   -30 但是我错了...............
•  » » 4 years ago, # ^ |   -36 There is wrote : " As they told me round will be rated ",how do you think ? it is rated or not?
•  » » » 4 years ago, # ^ |   +10 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.
•  » » » » 4 years ago, # ^ |   -36 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.
•  » » » » » 4 years ago, # ^ |   +19 Dude you surely don't understand sarcasm!
 » 4 years ago, # |   +15 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 unlucky!!
•  » » 4 years ago, # ^ |   +76 So write the alphabet on the piano keys and write code while playing music. That will be the real art
•  » » » 4 years ago, # ^ |   +38 You mean coding with new language? Piano++ or something with music when coding?
•  » » » 4 years ago, # ^ |   +92 Nice idea for another vim plugin.
 » 4 years ago, # | ← Rev. 2 →   +14 Good luck and have fun!
 » 4 years ago, # |   +51 I guess it's first Turkish round
•  » » 4 years ago, # ^ |   +31 Yes, It's first Turkish round.
 » 4 years ago, # |   +29 Hope to see interesting problems and good luck to everyone!
•  » » 4 years ago, # ^ |   +12 I'm sure you will see.
 » 4 years ago, # |   +21 Asin bayraklari!
•  » » 4 years ago, # ^ |   -8 !iralkaryab nisA
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 Bugun sinavvv erken kalkin cocuklar elimizde taze bilgisayarlari, ustumuzde yeni T-shitleri. (Turkish song) :)
•  » » 4 years ago, # ^ |   +31
•  » » 3 years ago, # ^ |   0 Put The Flags To The Balcony
»
4 years ago, # |
-48

Drink Application :D

 IF ( !odd (CF Round #) ) drink = "Cappuccino"; ELSE drink = "Coffee";
 memset(Mug, drink, SZ);

 » 4 years ago, # |   +87 And also thanks to me, who prepared the meals for contest team.
 » 4 years ago, # |   -15 lets hope dynamic score distribution for more interrseting xD
•  » » 4 years ago, # ^ |   0 Please, read this
 » 4 years ago, # |   +29 I hope, that statements will be short like this blog.
•  » » 4 years ago, # ^ |   -34 I hope, the problems won't be like adamant's.
 » 4 years ago, # |   +6 It is also first turkish round in CF =)
 » 4 years ago, # | ← Rev. 2 →   -9 " 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 :)
 » 4 years ago, # | ← Rev. 2 →   -6 How Long Does this Contest take ?
•  » » 4 years ago, # ^ | ← Rev. 2 →   +21 2 hours
•  » » » 4 years ago, # ^ |   +13 i hope your rate reach to this number of seconds my friend
•  » » » 4 years ago, # ^ |   -9 that is 7200000 milliseconds
 » 4 years ago, # | ← Rev. 2 →   +8 This contest will be very exciting. I hope i will be successful.
 » 4 years ago, # |   -31 NE MUTLU TURKUM DIYENE !!!!
•  » » 4 years ago, # ^ |   -15 Onlar konusur Turkler yapar
 » 4 years ago, # | ← Rev. 2 →   +1 i m looking forward to join contest
 » 4 years ago, # |   -44 I am seriously considering join the contest.
 » 4 years ago, # |   +18 A Regular codeforces round these do happen every once in a while now don't they nevertheless i hope it's fun ^_^
 » 4 years ago, # | ← Rev. 2 →   +27 Why is my registration canceled automatically? So is it with TooDiffiCuIt.UPD:It says 522 people have registered, but when I clicked into the page to see the registrants, I only saw 300+ people.
•  » » 4 years ago, # ^ |   +22 I encountered the same situation last time.
 » 4 years ago, # |   -32 I am back
 » 4 years ago, # | ← Rev. 2 →   -22 Beresta ready for another crossover? Coz I am.
 » 4 years ago, # |   +18 24 minutes to go! best site <3 love you codeforces! <3
 » 4 years ago, # |   +5 Sa beyler
 » 4 years ago, # |   0 We are still waiting for score distribution.
 » 4 years ago, # |   +14 Good luck everyone ... Try to do your best!
 » 4 years ago, # |   -20 На этом соревнование количество турков зашкаливает.
 » 4 years ago, # |   -15 I don't like "WA"...
•  » » 4 years ago, # ^ |   -8 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.
 » 4 years ago, # |   -76 Can someone give me a hit to solve DIV2.D?
•  » » 4 years ago, # ^ |   +4 How about no.
•  » » 4 years ago, # ^ |   +8 I think you shouldn't ask for that during the contest...
•  » » » 4 years ago, # ^ |   -17 yes, i haven't participated of this contest, my question is for after contest :D
 » 4 years ago, # |   +61 The score distribution for Div.1 today should be 250-250-30000-30000-30000 :P
•  » » 4 years ago, # ^ |   0 I should say the same for Div2 :P 250-250-25000-25000-250000000
 » 4 years ago, # |   +24 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.
•  » » 4 years ago, # ^ |   -9 I just know div2 C didn't have test for n==1 cause I hacked someone....
 » 4 years ago, # |   0 Passed pretest of Div2C after ages but I know it's gonna fail.Testcase0 1 0 2 0 010 3Answer — 4I am going cry in the corner of my bathroom. ;(
•  » » 4 years ago, # ^ |   +7 I think many solutions of C will fail today.
•  » » » 4 years ago, # ^ | ← Rev. 2 →   +4 Let's hope so. Anyways, my rank will be higher(in magnitude) because I solved A and B with slow speed.
•  » » » 4 years ago, # ^ |   0 And you were right.
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 OMG Nooooo I forgot. There can be only one bottle :( Now I realise why my solution was failing Div2 C on TestCase #3
•  » » » 4 years ago, # ^ |   0 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.
•  » » » 4 years ago, # ^ |   0 No, there was no pretest for N=1. I did some mistake which passed pretests, though I corrected it later.
•  » » 4 years ago, # ^ |   0 Oh... that case fails me too. ;(
•  » » 4 years ago, # ^ |   0 I have answer 4 for this test, but failed test 25.
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 Looks like my approach was wrong. :)
 » 4 years ago, # |   -37 Such interesting contest, so many problems were solved by everyone
 » 4 years ago, # |   0 Can anybody talk about how they did Div1C?
•  » » 4 years ago, # ^ | ← Rev. 3 →   0 UPD2: never mind, misread problem statement was sure that f(i,j) = gcd(... a[i — 1], a[j + 1] ... )
•  » » » 4 years ago, # ^ |   +5 UPD: it works because all a[i] different __That's just stupid...
 » 4 years ago, # |   0 Worst feeling in the world: "Contest finished reload page" while pressing the submit button (no it didn't count)
•  » » 4 years ago, # ^ |   +1 Even worse feeling, when you submit that solution after the contest and it says "ALL TESTS PASSED"
•  » » » 4 years ago, # ^ | ← Rev. 2 →   +5 That would be a mixed feeling between "man I'm awesome" and "f*** this **%* ** 12#\$* @!#*!@% !*@#( #@!"
 » 4 years ago, # |   0 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.
 » 4 years ago, # |   +3 How to solve DIV2D?
•  » » 4 years ago, # ^ |   +3 Binary search the maximum height after removing k blocks, then binary search the minimum depth you can fill with k blocks. More or less.
•  » » » 4 years ago, # ^ |   +3 It is sad I recieved so many WAs implementing the same logic. =(
•  » » » » 4 years ago, # ^ |   +3 Same, I just couldn't get the binary search idea to pass test 15.
•  » » 4 years ago, # ^ |   0 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
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 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.
 » 4 years ago, # | ← Rev. 2 →   +33 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.
•  » » 4 years ago, # ^ |   +1 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.
•  » » 4 years ago, # ^ |   +9 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.
 » 4 years ago, # |   0 Does binary search work for Div2D?
•  » » 4 years ago, # ^ |   0 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.
 » 4 years ago, # |   0 What was pretest 3 for Div2 C ?
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 I think it had only one bottle : Testcase 0 1 0 2 0 0 1 0 3 Answer — 4 Try this one
•  » » » 4 years ago, # ^ |   0 It works for this case :/
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 UPD: Sorry, seems like I have seen some combination of your comment and the one above it and I thought you ask for Div2D :(
•  » » » 4 years ago, # ^ |   +3 Thats not even a valid input
•  » » 4 years ago, # ^ |   0 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.895607473206Dont know why I failed this http://codeforces.com/contest/672/submission/17863191
•  » » » 4 years ago, # ^ |   +4 If someone can explain why this answer is correct it would be great.
•  » » » 4 years ago, # ^ |   0 See the difference. It's huge(two point something).
•  » » » 4 years ago, # ^ |   0 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
 » 4 years ago, # | ← Rev. 2 →   +4 Most complicated solution I could see for Div 2 Ahttp://codeforces.com/contest/672/submission/17850982Please share, if anyone get idea behind it :D
•  » » 4 years ago, # ^ |   0 Use to_string() to convert integer to string in C++11.
•  » » 4 years ago, # ^ |   +24 And the easiest one for Div 2A http://www.codeforces.com/contest/672/submission/17859081 (no offence to the writer though)
•  » » » 4 years ago, # ^ |   0 Hahahah thats just the best solution ive seen today :D
•  » » » 4 years ago, # ^ |   +4 I did the same :) 17847805
 » 4 years ago, # |   0 How do you solve Div-2C ? Anyone. Thanks.
•  » » 4 years ago, # ^ |   -7 Dynamic Programming..state (index,adil,bera)100000*2*2adil and bera represent if they went first time or not..after that both start at bin cycle so no problem
•  » » » 4 years ago, # ^ |   0 What if the first bottle to pick is not the same as the first bottle on the input?
•  » » » 4 years ago, # ^ |   0 Could you post a link to your solution on Ideone ? Thanks.
•  » » » 4 years ago, # ^ | ← Rev. 2 →   -11 Deep down I knew it was Dynamic Programming :/ But I couldnt figure it out. sigh
•  » » 4 years ago, # ^ | ← Rev. 4 →   +1 Lets 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.
•  » » 4 years ago, # ^ |   +3 I solved it greedy...
•  » » 4 years ago, # ^ | ← Rev. 10 →   0 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 bottles after the first recycled 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 i and j, the total distance would be:2·distFromBottleToBin[0] + 2·distFromBottleToBin[1] + ... + 1 ·distFromBottleToBin[i] + ... + 1 ·distFromBottleToBin[j] + ... + 2·distFromBottleToBin[n - 1]. Since they are not standing on them you should add up additional cost of traveling to the i'th and j'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.
 » 4 years ago, # |   0 When you solve E ~5 mins after contest T_T
 » 4 years ago, # |   +4 Oh My God!!! I got bluescreen before 5 minute the end!!!
•  » » 4 years ago, # ^ |   0 Are you still using Windows XP?
•  » » » 4 years ago, # ^ |   +10 I use Windows 10 and it also has bluscreen
•  » » » » 4 years ago, # ^ |   +9 We need some ice here.
•  » » » » 4 years ago, # ^ |   +4 Windows 10's blue screen is cool though
•  » » » » » 4 years ago, # ^ |   0 causes may vary but blue screen is the same :)
 » 4 years ago, # |   +8 I am unluckiest person trying to hack the luckiest person !!!check the return statementcode: 17850999
•  » » 4 years ago, # ^ |   +3 I dint understand. Could please explain ?
•  » » » 4 years ago, # ^ |   +5 Should be "return false;" instead of "false;"
•  » » 4 years ago, # ^ |   0 Actually, most compilers are smart enough to return false, if nothing is returned!
•  » » 4 years ago, # ^ |   0 maybe function bool in default version always return false;
 » 4 years ago, # |   +6 When would Editorial be published?
 » 4 years ago, # |   +2 I was one semicolon away from finishing Div2C.
 » 4 years ago, # |   -7 How can i increase my efficiency and accuracy in contests?
•  » » 4 years ago, # ^ |   +7 study?
•  » » 4 years ago, # ^ |   0 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.
 » 4 years ago, # | ← Rev. 2 →   +1 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 ?
•  » » 4 years ago, # ^ |   0 Well the coordinates wont change to 0,0 but it will change to Tx and Ty which is the location of the recycling bin
•  » » » 4 years ago, # ^ |   0 OOPS!!Sorry , i spoke about first example.
 » 4 years ago, # |   0 Can some one give me the ideal path for div2-c sample test 2? I just can't figure it out...please.
 » 4 years ago, # |   +114 I screwed up but I enjoyed div1-ABC a lot. Nice problems with fine difficulty. Keep my upvote muratt.
•  » » 4 years ago, # ^ |   +42 Thank you! It is very nice to hear this from you :D
 » 4 years ago, # |   0 When I saw " all ints starting from 1" I thought it meant...18 19 100 101 102...you know like all the ints starting WITH 1 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 :)
 » 4 years ago, # |   0 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.
 » 4 years ago, # |   +16 System testing isn't over yet and it is like
 » 4 years ago, # | ← Rev. 3 →   -8 Weak tests! this AC code fails on test 0 1 0 2 0 0 1 0 3 muratt can you take a look please.
•  » » 4 years ago, # ^ | ← Rev. 2 →   +9 Nope, this code gives 4.0000 and this is correct.Bera takes the rubbish then goes to bin.
•  » » » 4 years ago, # ^ |   0 Right. Sorry, On my machine it gives 0.0000. I dont now why.
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   0 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.
•  » » 4 years ago, # ^ |   +1 hi there! :o3
 » 4 years ago, # |   +41 Can anyone tell me how he solved div1D? I really liked the task, but didn't have any idea how to solve it.
 » 4 years ago, # | ← Rev. 2 →   +15 Test case 25. xD
•  » » 4 years ago, # ^ |   0 41 too as I see
•  » » » 4 years ago, # ^ |   0 69 and 80 also
•  » » » 4 years ago, # ^ |   0 Is there any way to figure out what was different about 41? Codeforces only gives me a portion of the input.
•  » » » » 4 years ago, # ^ | ← Rev. 3 →   +6 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 :/)
•  » » 4 years ago, # ^ |   0 Wrong answer on test 50 -_-
 » 4 years ago, # |   -13 Resubmitted C at final moment and got AC. Nice problems, my upvote for you muratt
 » 4 years ago, # |   +18
 » 4 years ago, # |   0 Div2 C WA on test 80 :(
 » 4 years ago, # |   0 n > 26 costed me an AC, I'm so upset...
 » 4 years ago, # |   +14 When your D gives less points than your B :D
•  » » 4 years ago, # ^ |   -8 even it gives .. :)
•  » » 4 years ago, # ^ |   +7 it is a risk to start contest from D.
 » 4 years ago, # | ← Rev. 7 →   0 why am i getting wrong answer ?!17852756thanks!
•  » » 4 years ago, # ^ | ← Rev. 3 →   0 You need to print 6 numbers after comma.accepted code
•  » » 4 years ago, # ^ |   0 You can see the test it failed at the bottom of the page. Precision problems.
•  » » 4 years ago, # ^ |   0 NOOOOOOOOOOOOOOOOOOOO! why ;_; . just for it :(((((((((((((((.thanks i have to kill myself
 » 4 years ago, # |   +81 56 more submissions and I would have made it :(
 » 4 years ago, # |   +5 Whats the reason for wa @ test 25
 » 4 years ago, # |   0 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???
•  » » 4 years ago, # ^ |   0 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.
•  » » » 4 years ago, # ^ |   0 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...
 » 4 years ago, # |   +5 when will tutorial be published?
•  » » 4 years ago, # ^ |   +19 No, they usually hide it :)
•  » » » 4 years ago, # ^ |   +5 :)
 » 4 years ago, # |   0 Had a silly mistake in Div 2 B. Surprised (and sad), no one hacked this during contest :o :( //data refers to map of characters in string if (data.size() == 26) { cout << -1; } 
 » 4 years ago, # |   +5 How to solve div2 D?
 » 4 years ago, # | ← Rev. 2 →   +11 Nice problems, but I'd prefer C to be easier to implement, especially because D needs quite a long code too.
•  » » 4 years ago, # ^ |   0 Actually my codes are ~100 lines for both. But as i see there are some quite long solutions.
 » 4 years ago, # | ← Rev. 5 →   0 What is the correct answer for this test to Div1 A? 100 0 0 100 0 0 2 0 1 1 0 My program returns 102 and I have been hacked with it.
•  » » 4 years ago, # ^ |   0 102
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 My program returns 102 too and i got accepted in main testsEDIT : solving by hand, answer is clearly 102, so we are both correct
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 OK, my program returns diffrent valuess running in Dev C++ and in online compiler so it's my mistake. Thanks.
•  » » 4 years ago, # ^ |   +3 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 0Output: 200.0000000000Answer: 102.000000000000Time: 0Memory: 4489216[close]
 » 4 years ago, # | ← Rev. 2 →   0 Thanks for quickly system test and hopefully rating should be updated quickly.
 » 4 years ago, # |   +15 Thanks contest was good.
 » 4 years ago, # | ← Rev. 2 →   0 del
 » 4 years ago, # |   +6 o.O
 » 4 years ago, # |   0 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.
•  » » 4 years ago, # ^ |   0 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?
•  » » » 4 years ago, # ^ | ← Rev. 5 →   0 I tried to do dp(v) and then for each worker that has a path u -> v, I tried adding that cost plus dp(u), plus dp(i) for all children i of v that don't lie in the path from u to v, 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.
•  » » » » 4 years ago, # ^ | ← Rev. 3 →   +5 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.
 » 4 years ago, # |   +11 The first and second places at Div2 from Uzbekistan. Go, go, go Uzbekistan!
 » 4 years ago, # |   +23 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.
•  » » 4 years ago, # ^ |   0 It should be worth 2250 points.
 » 4 years ago, # |   +13 What about the editorial?
 » 4 years ago, # |   +1 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 :)
 » 4 years ago, # |   0 In problem div2 Cwhy this submission 17859797 gets RTE?!!
•  » » 4 years ago, # ^ | ← Rev. 2 →   +10 Your comparison operator is incorrect. Yeah, copypaste sucks: bool cmpA(po a,po b){ return a.disZ-a.disA>b.disZ-b.disB; // Should be disA } 
 » 4 years ago, # | ← Rev. 2 →   +7 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.
 » 4 years ago, # |   0 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 !
•  » » 4 years ago, # ^ |   +13 printf("%.12lf",(double)cevap); `