muratt's blog

Codeforces Round #352
By muratt, 9 years ago, In English

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:

1-subscriber

2-W4yneb0t

3-jcvb

4-Merkurev

5--XraY-

Div.2 winners:

1-the_arr_of_war

2-Shavkat_Aminov

3-Lightning34

4-I_Love_Ginger

5-tjandra

UPD3: Editorial is now available.

  • Vote: I like it
  • +338
  • Vote: I do not like it

Comments Comments (180)
| Write comment?
»
9 years ago, # |
  Vote: I like it +84 Vote: I do not like it

is it rated?

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 3   Vote: I like it -54 Vote: I do not like it

    I hope it will be rated :D

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it -36 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it -36 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it +19 Vote: I do not like it

          Dude you surely don't understand sarcasm!

          → Reply
»
9 years ago, # |
  Vote: I like it +15 Vote: I do not like it

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!!

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +76 Vote: I do not like it

    So write the alphabet on the piano keys and write code while playing music. That will be the real art

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +38 Vote: I do not like it

      You mean coding with new language? Piano++ or something with music when coding?

      → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +92 Vote: I do not like it

      Nice idea for another vim plugin.

      → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +14 Vote: I do not like it

Good luck and have fun!

→ Reply
»
9 years ago, # |
  Vote: I like it +51 Vote: I do not like it

I guess it's first Turkish round

→ Reply
»
9 years ago, # |
  Vote: I like it +29 Vote: I do not like it

Hope to see interesting problems and good luck to everyone!

→ Reply
»
9 years ago, # |
  Vote: I like it +21 Vote: I do not like it

Asin bayraklari!

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it -48 Vote: I do not like it

.

→ Reply
»
9 years ago, # |
  Vote: I like it +87 Vote: I do not like it

And also thanks to me, who prepared the meals for contest team.

→ Reply
»
9 years ago, # |
  Vote: I like it +29 Vote: I do not like it

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

→ Reply
»
9 years ago, # |
  Vote: I like it +6 Vote: I do not like it

It is also first turkish round in CF =)

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it -9 Vote: I do not like it

" 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 :)

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it -6 Vote: I do not like it

How Long Does this Contest take ?

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

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

→ Reply
»
9 years ago, # |
  Vote: I like it -31 Vote: I do not like it

NE MUTLU TURKUM DIYENE !!!!

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

i m looking forward to join contest

→ Reply
»
9 years ago, # |
  Vote: I like it -44 Vote: I do not like it

I am seriously considering join the contest.

→ Reply
»
9 years ago, # |
  Vote: I like it +18 Vote: I do not like it

A Regular codeforces round these do happen every once in a while now don't they nevertheless i hope it's fun ^_^

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +27 Vote: I do not like it

Why is my registration canceled automatically? So is it with jqdai0815.

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

→ Reply
»
9 years ago, # |
  Vote: I like it -32 Vote: I do not like it

I am back

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it -22 Vote: I do not like it

Beresta ready for another crossover? Coz I am.

→ Reply
»
9 years ago, # |
  Vote: I like it +18 Vote: I do not like it

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

→ Reply
»
9 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Sa beyler

→ Reply
»
9 years ago, # |
  Vote: I like it +14 Vote: I do not like it

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

→ Reply
»
9 years ago, # |
  Vote: I like it -15 Vote: I do not like it

I don't like "WA"...

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    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.

    → Reply
»
9 years ago, # |
  Vote: I like it -76 Vote: I do not like it

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

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    How about no.

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it -17 Vote: I do not like it

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

      → Reply
»
9 years ago, # |
  Vote: I like it +61 Vote: I do not like it

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

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
9 years ago, # |
  Vote: I like it +24 Vote: I do not like it

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.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it -9 Vote: I do not like it

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

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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. ;(

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    I think many solutions of C will fail today.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 2   Vote: I like it +4 Vote: I do not like it

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

      → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      And you were right.

      → Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
9 years ago, # |
  Vote: I like it -37 Vote: I do not like it

Such interesting contest, so many problems were solved by everyone

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anybody talk about how they did Div1C?

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      UPD: it works because all a[i] different __

      That's just stupid...

      → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

    "ALL TESTS PASSED"

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 2   Vote: I like it +5 Vote: I do not like it

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

      → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

How to solve DIV2D?

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

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

        → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +33 Vote: I do not like it

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.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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.

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    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.

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Does binary search work for Div2D?

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What was pretest 3 for Div2 C ?

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    I think it had only one bottle :

    Testcase
    0 1 0 2 0 0
    1
    0 3
    Answer — 4

    Try this one

    → Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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://mirror.codeforces.com/contest/672/submission/17863191

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

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

      → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

      → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +4 Vote: I do not like it

Most complicated solution I could see for Div 2 A
http://mirror.codeforces.com/contest/672/submission/17850982

Please share, if anyone get idea behind it :D

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it -7 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 4   Vote: I like it +1 Vote: I do not like it

    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.

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    I solved it greedy...

    → Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 10   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

When you solve E ~5 mins after contest T_T

→ Reply
»
9 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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

→ Reply
»
9 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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

check the return statement

code: 17850999

→ Reply
»
9 years ago, # |
  Vote: I like it +6 Vote: I do not like it

When would Editorial be published?

→ Reply
»
9 years ago, # |
  Vote: I like it +2 Vote: I do not like it

I was one semicolon away from finishing Div2C.

→ Reply
»
9 years ago, # |
  Vote: I like it -7 Vote: I do not like it

How can i increase my efficiency and accuracy in contests?

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    study?

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like 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 ?

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
9 years ago, # |
  Vote: I like it +114 Vote: I do not like it

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

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +42 Vote: I do not like it

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

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
9 years ago, # |
  Vote: I like it +16 Vote: I do not like it

System testing isn't over yet and it is like

→ Reply
»
9 years ago, # |
← Rev. 3   Vote: I like it -8 Vote: I do not like it

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

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it +9 Vote: I do not like it

    Nope, this code gives 4.0000 and this is correct.

    Bera takes the rubbish then goes to bin.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    hi there! :o3

    → Reply
»
9 years ago, # |
  Vote: I like it +41 Vote: I do not like it

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

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +15 Vote: I do not like it

Test case 25. xD

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    41 too as I see

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      69 and 80 also

      → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
        ← Rev. 3   Vote: I like it +6 Vote: I do not like it

        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 :/)

        → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Wrong answer on test 50 -_-

    → Reply
»
9 years ago, # |
  Vote: I like it -13 Vote: I do not like it

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

→ Reply
»
9 years ago, # |
  Vote: I like it +18 Vote: I do not like it

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Div2 C WA on test 80 :(

→ Reply
»
9 years ago, # |
  Vote: I like it +14 Vote: I do not like it

When your D gives less points than your B :D

→ Reply
»
9 years ago, # |
← Rev. 7   Vote: I like it 0 Vote: I do not like it

why am i getting wrong answer ?!

17852756

thanks!

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    You need to print 6 numbers after comma.

    accepted code

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    thanks i have to kill myself

    → Reply
»
9 years ago, # |
  Vote: I like it +81 Vote: I do not like it

56 more submissions and I would have made it :(

→ Reply
»
9 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Whats the reason for wa @ test 25

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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???

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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...

      → Reply
»
9 years ago, # |
  Vote: I like it +5 Vote: I do not like it

when will tutorial be published?

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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;
}
→ Reply
»
9 years ago, # |
  Vote: I like it +5 Vote: I do not like it

How to solve div2 D?

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +11 Vote: I do not like it

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

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
9 years ago, # |
← Rev. 5   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    102

    → Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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

    → Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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]

    → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
9 years ago, # |
  Vote: I like it +15 Vote: I do not like it

Thanks
contest was good.

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

del

→ Reply
»
9 years ago, # |
  Vote: I like it +6 Vote: I do not like it

o.O

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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?

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 5   Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
        ← Rev. 3   Vote: I like it +5 Vote: I do not like it

        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.

        → Reply
»
9 years ago, # |
  Vote: I like it +11 Vote: I do not like it

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

→ Reply
»
9 years ago, # |
  Vote: I like it +23 Vote: I do not like it

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.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It should be worth 2250 points.

    → Reply
»
9 years ago, # |
  Vote: I like it +13 Vote: I do not like it

What about the editorial?

→ Reply
»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem div2 C

why this submission 17859797 gets RTE?!!

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it +10 Vote: I do not like it

    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
}
    → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +7 Vote: I do not like it

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.

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 !

→ Reply