AndreySergunin's blog

Codeforces Round #310
By AndreySergunin, 9 years ago, translation, In English

Hello, Codeforces.

Soon, on 27 june at 17:00 MSK regular, 310-th Codeforces round will take place. Problems have been prepared by me, Andrey Sergunin, and Egor Shcherbin (Lord_F).

We want to thank Max Akhmedov (Zlobober) for helping us preparing the contest, Maria Belova (Delinur) for translating statements in English and Mike Mirzayanov (MikeMirzayanov) for great Codeforces and Polygon systems.

Participants will be given five problems and two hours to solve them. Scoring will be announced later.

Good luck everyone!

This round will use the dynamic scoring.

UPD: Due to technical reasons round is delayed by 10 minutes.

UPD: The preliminary version of an editorial was posted.

UPD: Congratulation to the winners:

Div 1

  1. qwerty787788

  2. Petr

  3. Haghani

  4. KADR

  5. zxqfl

Div 2

  1. onufryw

  2. munaiyi

  3. _h_

  4. Chenyao

  5. mhadih

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

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

Thanks for the schedule change!

Looks like my ranting served its purpose :)

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

    Hey! Why the downvotes ?????????

    I'm happy because we'll have another contest tomorrow and it's at a different time than usual. The other day I was complaining because contests are always 19:30 MST, so now I'm thanking for the schedule change.

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

      I assumed the time was as usual and couldn't compete. I guess I'm going to have to check each time now.

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

Your curve is very inspiring :))

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

Consecutive Div1 + Div2 Contest :D

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

Good luck all, hope a good rating for all.

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

Finally a contest on a day off from work! There isn't a better way to enjoy my free time! Great ratings for all!

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

I have been waiting for an early contest (10pm in my timezone) for so long, thank you very much XD

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

    +1. It's my timezone too. As well as 24% of the world's population. Here, recent Codeforces rounds typically start at 00:30 and end at 2:30 am. I find that in the middle of the night I can write code reasonably well, but seeing the solution to a problem is very hard, even for problems I find easy in the daytime.

    I'm not complaining, because I think it's exactly right that Codeforces should optimise contest timing for the western Russia community, as a first priority. 19:30 in Moscow seems good if it encourages having an early supper, which is healthy :) For some odd reason, however, TopCoder contests don't cater for Americans very well, because they also run most frequently in the middle of the night in my timezone. It might be because (a) there are some cultural differences, or (b) empirically this time maximises participation.

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

Not a great time for some muslim coders that keep post. Contest is intersecting with iftar time:( In Tajikistan we can enjoy only one hour of contest.

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

    i'm agree with you

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

    for me this time is just perfect, before three days because of the round #309 I had to delay my iftar time(eating time after fasting) by 1 hour and a half in order to participate in that round.

    and also as clearly we can see most comments in this blog liked this time change so I think administrators really need to consider using various usual times instead of one usual time, that helped a lot of coders even if the times are not far from each other (like this one it's only 2 hours and a half different from the usual time)

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

Great time for Korea! It used to be 01:30-03:30, but today it's 23:00-01:00. I(and many) always wanted this...

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

i wish all of you have great contest

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

    Good for some, not good for others. This will always be the case.

    But at least it's different than usual, which means a chance to participate for coders who usually can't take part in contests due to intersection with work/school/etc..

    With varied schedules, if you can't take a particular context, you may be able to take the next one.

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

    why downvotes ...

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

It clashes with Challenge24...

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

    I think we all know where is must to participate. :)

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

مینداختی بعد افطار دیگه

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

it will be my 6th contest as a Div — 1 contestant . All my previous five attempt was so pleasant that i kick out to Div — 2 everytime :p i hope this time i will survive :D

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

    just solve first problem quickly(or at least not very late) and your rating will raise

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

      Easier said than done (For new candidate masters!) :D

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

    shakil_AUST your graph is really inspiring. :) Best of Luck

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

    Well i hope if i able to come Div — 1 again that time i will try my best to survive Div — 1 :D thank you for supporting :D

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

It's a good time to start the competition.

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

It's a bad time for muslim users

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

01010100011010000110000101101110011010110010000001111001011011110111010100100000001100010011011000100000

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

don't want a maths contest this time :P

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

So any body know wich kind of problems AndreySergunin usually gives (graph , math , dp ... ) ??

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

    Usually he doesn't give problems cuz it's his first round, btw. Let's wish AndreySergunin and Lord_F good luck!

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

      Thank you mister sherlock . Btw Lewin prepared his first round last time but he was preapring problems in topcoder so peoples have previous idea about what he post .

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

        U r welcome, Dr.Watson :) I can almost certainly say that they didn't prepare TC rounds either

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

Waiting for the contest.

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

I hope there aren't math problems.

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

    :-|

    Why?

    All of computer engineer love math problem .

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

      it is not because i dont like math, i just like data structures, sqrt decomposition , graph theory more.

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

    Maths problems is sometimes interesting(brainstorm). But too many maths problems will make my brain feel tired.

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

      i think that the best programming contest are those wich involve lots of math !

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

      But you are mathlover D: D:

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

      I with Kronecker made math-only contest, but Zlobober unfortunately rejected it.

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

        Because most of people don't like maths problems, which seems boring in their eyes.

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

      Math makes mathlover Tired.

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

        During this contest, I am struggled with div1C. I tried to solve it with two segment trees... However, I have never played with segment trees for months... At last I failed... I think I should train my data structure skill.

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

I wish I will have a better rating,Thank you very much.

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

nice time，Hope I can go to div1

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

Do you guys use information from the scoring?

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

    No，I don't use it,I only sovle problem by their order

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

delayed by 10 mins :(

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

It's delayed for 10 mins ):

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

10 min delay again

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

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

scoring ??!

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

This Time Is Better For Contests ..

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

UPD: Due to technical reasons round is delayed by 10 minutes.
it seems that another chance for authors to delay score distribution :D

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

    Even though there is nothing about score distribution in English version of the post, the Russian version of it says that the score distribution will be dynamic.

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

When will the score distribution be announced? I believe it will be before the contest starts.

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

I've got nothing against dynamic scoring, but damn those penalties on 250pt problem are harsh..

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

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

Oh God! Save me from the wrath of system tests...

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

Changing of description of Div1A was too critical

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

    But it was kinda obvious from the start because you can't put A into B if B is in something else in real life too.

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

      By the same argument, it was obvious that you can't take A out of B if B is in something else, but this was explicitly stated in BOLD LETTERS in the statement for some reason.

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

        Well, you're right. I didn't notice that.

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

        My personal sorry for that place. Using the bold letters here and hoping for a participant's common sence was a huge mistake that led to a such situation that even Russian-speaking contests were confused how the matryoshkas work.

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

      https://en.wikipedia.org/wiki/Banach%E2%80%93Tarski_paradox

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

        This is interesting! Aside from that, I know that you know what I meant by saying obvious. This is definitely not something that come to mind first (at least for me).

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

          If I know how Matryoshka works, it could be obvious. Unfortunately, I wasn't. In point of view of you, I can understand what you mean saying 'obvious'.

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

            For some reason, I thought it's like different size of cups or buckets, so I was really confused with the restriction. Now that I googled it, it's actually really obvious.

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

      Don't think it's obvious.

      When I was thinking about matryoshkas I didn't imagine closed ones, only bottom halves of them. If you're messing around with these toys in real life that way, you definitely can put A into B even if B is already in C, but it is kinda hard to pry out A from B if B is already in C. Pretty consistent with the first version of the problem, isn't?

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

The Codeforces system is so fair! I tried submitting E at 01:59 and I got no response from the server!

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

    D: I submitted mine at 1:59:40, nearly broke my shoulder while running back to my laptop when I realized what a stupid mistake I made.

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

      "nearly broke my shoulder while running back to my laptop" LOL

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

      All that for WA 54 =(

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

Any suggestions on how to solve Div2 D / Div1 B?

EDIT: I sorted the bridges in ascending order. I did the same with distance between each adjacent island, keeping track of the minimum and maximum length allowed.

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

    I think this will be the approach though i got runtime error while submitting

    First store the max and min length required between each island . Sort according to min length . Start in reverse order that is take largest min length first . Find a suitable bridge using lower_bound .

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

      Ah, ok. I simply iterated from the beginning of both arrays. If the length of the current bridge was not in between the current min and max, then I moved on to the next available bridge.

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

        This looks like TLE, accorting to the 10^5 bounds.

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

          I apologize. I didn't finish elaborating.

          In my code, once I found a valid match, I would start looking for the next match considering only the bridges that came after the current one.

          However, this idea fails with the test case given by Bluespeck.

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

      My approach is somewhat different. I store all bridges in a set, because you can use a bridge only once, so with the set, you can easily erase the bridge from the set. I sorted all max (r_(i+1) — l_i) and min (l_(i + 1) — r_i) lengths by the maximum length. Then you try to fit the smallest bridge in the gap. If there is no bridge, or your lower_bound gives a bigger bridge, it's not possible.

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

      I wonder if this is correct. You will find a "suitable" bridge — I assume the shortest bridge that is greater or equal than current min. How can you know that you shouldn't take a greater because it is too large to cover other islands?

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

I have a question. IF the problem is worth 250 points and you make 5 wrong submissions of it, at the end of the round, will you get negative score or still 30% of that problem's value (or whatever the minimum point value for the problem is)?

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

    you get at least 30% of the problem points which is equal to 75 ,so if your penalties (time + wrong submissions) make the problem less than 75 you will take 75 points

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

      Thanks. Howevr I think that wrong submission penalty should be dynamic. Especially with a dynamic scoring.

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

I thought very hard but couldn't find a way to solve div 2 D . How to solve it?

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

What's wrong with the Div2. D greedy solution? Sorting bridges and sorting island pairs (with their maximum value and minimum possible value) + binary search (some kind of lower_bound in bridges).

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

    I had something similar, but there will be cases where this fails.

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

      Here's my code. It may be too complex. It didn't pass the 6'th test. http://ideone.com/kFJqP5

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

      It's like you sort the islands pairs looking at minimum possible bridge and then at maximum possible bridge it fits. Then, for each pair you search in the sorted bridges array for the shortest possible bridge.

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

    Greedy solution is the right one, something is wrong with your "greediness".

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

    Not sure... I took a greedy solution too and got stuck on pretest 10.

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

      Well, the thing is that you put the next bridge in the interval that isn't already used and ends first.

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

        Could you explain your solution? I checked your profile and it says you didn't submit for that question.

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

    the same here, this is my code

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

    i think binary search don't help in this case, i pass pretests with set in which i store bridges lengths(and you can also do lower_bound in set in log time)

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

    try it: 3 2 1 3 4 5 7 7 3 4

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

    Here is my approach , for each GAP , find the min and max value it can take. Let it be ai and bi. Now sort the GAPS with respect to the DIFFERENCE (bi-ai) , so lowest difference gets first. Now , sort the bridges too with smallest first.

    Now , iterate over the GAPS , try to match it with the smallest bridge.

    For the Example , the (min,max) for the gaps are (3,7) ,(1,3) and (2,5) . After sorting we get (1,3) ,(2,5) and (3,7) . Now , we first put smallest bridge 3 to (1,3) , then next one 4 to (2,5) and the third one 5 to (3,7). But I am stuck at case 10. 11805605

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

      That one failed test 1? I think you mean http://mirror.codeforces.com/contest/556/submission/11805830

      I also got stuck on test 10.

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

      I stuck at test case 10 with this approach too. It would really appreciated if someone smarter guy or girl could give a short example, why this strategy is bad :-)

      11805791

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

        Consider two gaps, [1,3] (i.e. 3 is max, 1 is min value it can take) and [3,4].

        You have two bridges of length 3 and 4.

        The greedy sol'n above results in using the smaller bridge of length 3 for the second gap, and leaves no bridge left for the first gap, when you could have satisfied both gaps.

        The difference in ai and bi is not a good metric; having smaller range of values doesn't imply it should be satisfied first.

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

The statement for Div1.A/Div2.C can be more clear.

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

I think submission penalties for Div1 A should be cancelled for people who got WA on pretest 6 prior to the clarification.

Full disclosure: I am one of those people

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

    not only submission penalties , extra time penalty because of resubmit should be removed too.

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

    What is pretest 6 on Div1 A/ Div2 C? I did not see the clarification because I started at min 40.

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

I've read Div1.A task. Thought that its too easy for Div1. Read again. And again — trying to find something tricky. Spent 10 mins, surrender on that. Coded this simple solution for simple task and it passed pretests o_O.

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

I misread the statement of Div1-A twice and lost nearly 1 hour on that...

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

    I lost a lotta time on that too... Maybe could've figured out the bug in my DIV1-B if they had a clearer statement from the start! :(

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

For me today was the day for WA on pretest 6 (8 WA on 6th pretest ) . Any tricky case for div1 B ?

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

I found out that my Div1D solution was right before AC, but I made a silly mistake :(

So, I hope lot's of TL in Div1D! kekekekeke

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

Back to div2.. see you guys ^_^

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

    Huh, me too probably, only solved A :)

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

    Don't worry, I won't leave you alone <3

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

      it's not a big deal, we will have round #311 in 3 days, and we will all be back guys! ;)

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

        ...and I like blue color more than purple anyway.

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

          yeah, I agree. :D that would be good if this color were removed and replaced by some other

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

    Same here :p !! If only the first problem's clarification was made earlier!!! Well, who knows now? I will just try to improve myself and come back! :D

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

The contest was great !!!

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

Problem B div 2 is O(n^2) ?????

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

    My solution have O(2*N)

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

      can you explain?

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

      can you explain your approach?

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

        Just check for index 0 that how many steps counter clockwise you need to rotate to make its value 0. perform those number of steps in every other array index and check at last if it matches then "Yes" else "No". Complexity O(n).

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

    No, my solution works for O(n)

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

    You check if it's strictly ordered (like 0,1,2,3,4,5..n-1). If not — iterate through the array and do all the changes. I have done that exactly 2000 times.

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

    O(n)

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

    11790948 O (N log N) can be O(N)

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

    My solution also run approximately O(N).

    At first I calculate how many time I need to push the button, then I cheek for all i (in range).

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

Can somebody please explain why this solution gets TLE, it's linear — http://mirror.codeforces.com/contest/555/submission/11791988.

I tried scanf/printf and I wrote it in C too but the outcome was the same. Then I deleted everything and wrote it again and it passed but why it didn't pass at the beginning?

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +45 Vote: I do not like it 
    cin>>n>>k;
  for(i=1;i<=n;i++) {

    How did this pass 14 pretests?

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

      lol thanks... I looked at the code more than 10 times and didn't notice that FACEPALM

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

I am going to learn SET

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

Div2A: Time limit exceeded on pretest 12 Wasn't expecting time limit errors on A task... anyone else hit by that?

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

    Me but i resolved it by another way and get pretest passed

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

      Same thing, but still surprised to have an TLE on O(n^2) solution for n<10^5

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

Scoring system is dynamic. But points deduction is absolute(-50) .. and when the score keeps decreasing, -100 pushes the score like hundreds of places behind. Please take a look Mike

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

    It will be the same as if the task have static 250, no? If so, nothing changed.

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

      It kind of discourages hacking and not much value for speed is given either. Difference of +100 initally due to early submission time is now like +10 or +20. But 2 faults in hacking gives -100 difference direct.

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

      In my case, I solved problem A in 30 mins, which has 171 points (after conversion to 250). I missed 2 hacks , which reduces score to 71 points and puts me at the fag end of the leaderboard

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

        Imo, its pretty fair. You should hack only if sure it succeed.

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

          Hacking is my mistake, okay. But still, if 2 hacks make my score less than someone whose submission time is ages(people who submitted near end have higher points) after me, I feel there is an imbalance somewhere.

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

            Well you know, its balanced with task complexity — if you try to hack on e.g. task E it won't be the same.

            Also If you succeed these two hacks you get more scores than some ppl who solved A+B. Is it fair from your point? Its the opposite side of this hacking thing. Just not your one this time :)

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

After this round, I think learning Russian is more important than English .

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

Contest time on early night truly affects my performance (at least for me)

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

Somebody explain me problem C in simple langugage

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

    Problem statement or solution?

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

      problem statement . what exactly do we have to do. I am having really hard time with words like contained and nested .

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

    just imagine the dolls and how can you remove one, or put a doll inside another.

    first, you need a minimum of k-1 seconds to reassemble the chain from initial configuration.

    this is clear with a case like this:

    4 4 1 1 1 2 1 3 1 4

    here you only need to put 1->2, 2->3, 3->4

    then you need to test all chains, if you find a chain of size 'S' and has elements '1, 2, 3, 4, .. ,S'

    then this chain is consistent and there is no need to reassemble it.

    other wise you will need to disassemble all elements from the point of inconsistency.

    e.g.: a chain with: 1, 2, 4, 5

    you need to extract element 2 by removing 5 then 4

    hope this help's

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

      Can 2 chains be attached together ? suppose 1->2 and other 3->4 can these 2 be combined in a single step?

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

Good time! Wish more contests like this.

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

for(auto& v: adj[u]) if(v!=p) (WA 51) into for(auto& v: adj2[u]) if(v!=p) (AC)

Copy paste why...

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

    how can adj[u] changes to adj2[u] if copy paste?

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

      Yeah, I copy pasted two dfses, but I only changed one instead of both lists after I copy pasted. I was afraid I was going to run out of time if I didn't copy paste, but looks like I should've taken the extra 5 seconds to check it over.

      For reference:

      WA: 11804870

      AC: 11805918

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

    for(auto it:M) WA

    for(auto &it:M) AC

    :)

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

    I ended up debugging my B during the contest. Found bug after the contest.
    Bug : Have to do sort(diff, diff + m) rather than sort(diff, diff + n). :'(

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

please god don't let them take as long as the system test to publish the editorial

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

    Behold the bug in thy prayer! Repeat after me and be wise:

    Please gcd let not my integers overflow today.

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

You have to normalize the coordonates on C div1 because QlogQ gets AC but QlogN doesn't, very very smart.

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

    I've got AC with O(Qlog2Q) in upsolving. So I think O(QlogN) can pass.

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

Div 1 B.I saw people using similar approach like mine,and solved this problem using set.But I've time limit,can anyone offer optimizations or tell me the reason why my solution fails while other's don't? code

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

The contest ended 1.5 hour ago. He solved all the problems 0.5 hour before the end.

He visited 3 hours ago.

Am I the only one confused??

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

    "Last visit" doesn't mean he has beel left this site 3 hours ago, this is mean he last time entered site 3 hours ago.

    He just solved all problems and left.

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

    probably it's the time when the person last logged in.

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

    That feature does not work at all :) I told MikeMirzayanov about it long time ago, but I think they have other things to do :)

    Sometimes it shows time from moment when you entered site, not when you left it; sometimes if you entered for a short period of time only — it does not update at all. Sometimes value randomly updates to older — you see "3 hours ago" there, press f5 and it becomes "9 hours ago".

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

      Personally I like the last one. The next weekend will be earlier, right?

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

Hi, Java fans.

Trying to solve div1B using TreeSet I found out that I can't use the structure if there are duplicate keys.

Here you can find why.

"For example, if one adds two keys a and b such that (!a.equals(b) && a.compareTo(b) == 0) to a sorted set that does not use an explicit comparator, the second add operation returns false (and the size of the sorted set does not increase) because a and b are equivalent from the sorted set's perspective".

How to solve the problem then? Well, one could use TreeMap<Long, LinkedSet> instead.

http://mirror.codeforces.com/contest/555/submission/11800486

http://mirror.codeforces.com/contest/555/submission/11805972

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

Didn't like the MemoryLimitExceeded in Problem Div1C. It was too easy to get MLE if you focused in solving it on time. Good problems but either memory limit should be higher or N limited to 100,000 instead of 200,000 :(

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

If the input would have been sorted in Div. 1 D I would have 100% solved for the first time. With unsorted input I was late for 2 minutes.

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

I really wonder what 'technical reasons' are in Codeforces Round 307 (Div. 2), Codeforces Round 307 (Div. 2), Codeforces Round 305 (Div. 1), and others.

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

Finally.

P.S. I changed my avatar to red. One should always have a target. Hope I become red, as my avatar this year.

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

Hi all,

In Div 2 C/Div 1 A, I have submitted this solution which got WA: Solution1 And after the contest I checked the test case on which it was failing(Test case 8) and tried it on my ubuntu machine it gave me 33(which is the correct answer but it gave Wrong Answer on Codeforces). Then I submitted another solution: CorrectSolution it got accepted. In this I just have cleared the boolean array "khali". Can please anybody tell me why my same solution gave 33 on ubuntu machine and 27 on Codeforces on test case 8? This is the test case->

20 6
3 8 9 13
3 4 14 20
2 15 17
3 2 5 11
5 7 10 12 18 19
4 1 3 6 16
→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    the same here in test case 2 !!!

    i have compiled it at visual studio , jetbrains , ideaone . correct answer except at codeforces

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

      Try clearing some array that you have initialized. I am not getting that why linux machine result(having the same gcc compiler) differs from codeforces compiler result?

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

        i am not in linux , i am on windows still WA

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

    From Stack Overflow- " There is no automatic initialization in C++. Your new bool will be "initialized" to whatever was in memory at that moment, which is more likely to be true (since any non-zero value is true), but there is no guarantee either way. You might get lucky and use a compiler that plays nice with you and will always assign a false value to a new bool, but that would be compiler dependent and not based on any language standard. You should always initialize your variables."

    Same happened with me:P

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

      What a luck..!! That all of my n sized boolean array took 0 value(false value) by default even though I didn't initialized it and I wasted around 45 minutes + 2 Wrong submissions..

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

Got screwed over by the MinGW C++ compiler:

int n = 5;
n = n--;
cout << n;

It turns out this code gives different results for GCC and MinGW. :( Shouldn't have coded that in the first place, but I was sleepy so I didn't notice it.

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

    Instead of n=n--; n-- would have sufficed. It actually decrements the content of the register in which n is stored, so we would have our desired result. The line you wrote performs unexpectedly in different situations

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

Can somebody tell me why my code for Div1B http://mirror.codeforces.com/contest/555/submission/11803847 TLEs ?

I sort every pair of islands by their maximum distance ascendingly (Sorting the indices actually) and then I insert the bridges in a set and looper over the pair of islands, and find the minimum possible bridge that fits then erase it it found. Complexity should be O(N lgN)

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

    Know your libraries. std::lower_bound is O(n) for a set, not O(log n).

    You probably wanted b.lower_bound() instead.

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

      Thanks, Now it's accepted, I definitely have to take note of this!

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

    lower_bound(set.begin(), set.end(), x) works in O(N).
    set.lower_bound(x) works in O(logN)

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

The Tutorial link in problems of this round opens Codeforces Round 309's Editorial.Is Round 310's Editorial published?

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

    Nope, it's not published yet.

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

Don't you think posting 1 to 5 ranked coders is motivating? :D

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

When The editorial of round 310 will be available ?

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

Can anybody help me with the logic of Div 2 problem D? Plz elaborate in detail.

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

    I don't think the editorial is coming up any time soon, so here goes. Given that we have to connect two islands with co-ordinates (a,b) (c,d) with some bridge of length l such that l<=(d-a) and l>=(c-b), since all islands lie on a straight line.

    Now we are going to implement a greedy solution, ie we sort all islands by their smaller distance(c-b) and try to assign the smallest bridge possible to the bridge.

    This solution will however fail in cases where although the smaller distance between the islands (c-b) is the minimum among all islands, but the larger distance is greater than the rest of the islands. You can think of it in terms of flexibility of an island defined as the range of accepting lengths of bridges from [c-b,d-a].

    Consider 3 islands as :

    1 5 (I1)

    6 7 (I2)

    8 9 (I3)

    Bridges are of length : 3,5

    Our initial greedy algorithm will assign bridge of length 3 to connect I1 and I2 and then would be unable to connect I2 and I3, but clearly switching the bridges gives us a solution.

    Therefore, we sort all islands by their larger distance(d-a) and then try to assign a bridge to it that is as close as possible to (c-b), ie we give highest priority to island with lowest flexibility and try to assign a bridge to it that just connects the island.

    code

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

Can anybody help me with my runtime error for Div.2 D at test case 11 (11810093). Every test case passed until the big one with 100000 islands and bridges.

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

This time sorry_dreamoon-(qwerty787788) has beaten Haghani :)

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

looks like the editorial is going to take forever !!

please any body, what is wrong with my approach for problem Div2 D.

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

Nice contest!

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

in general,my friend and I have a very tired contest......As I said -> DeaphetS he is the most hansome boy in our school .

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

Can someone please explain me why my all 3 submitted solutions were skipped in yesterday's contest 11804905 ,11800557 and 11788258 ?

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

    Solutions usually get skipped when they are found to be similar to someone's code. Did you ideone?

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

I didn't find the tutorial for this contest, somebody give me the link .

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

Div 1D is very intuitive and easy! Comparatively div2D was tricky imo.

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

    It maybe your illusion......

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

      that's what I thought, but after looking at someone's accepted code, it was the same as my logic. complexity= n*logn*logl in worst case.

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

Finaly solve problem Div.2 D (11818401): Let represent an island as pair ii = (li, ri). You have to sort all island pairs (ii, ii + 1) after their maximum distance in ascending order. The bridges can be save in a set. Than we start at the beginning of the sorted island pairs and perform for the minimum distance dmini = li + 1 - ri the operation lower_bound(dmini) on the set. We have to check if the resulting bridge fulfill the requirements and erase the bridge from set otherwise print "No" and exit. We repeat the procedure for each island pair. Note that we have to put a little work on the datastructure since the output requires the indicies of the bridges.

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

where can I find the editorial ? (the contest material is linked to the wrong page)

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

Can anyone explain Haghani's solution of problem DIV 2E/1C ? Its so simple and elegant but i don't get how it works.

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

This Problem and Case of Matryoshkas (Div2) are exactly same problems.

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

I'm sorry for necroposting and pedantry, but the first picture in the note for problem D (Div. 1) isn't consistent with the sample test -- the coordinates there are 0, 5, 8, while in the sample test they are 0, 3, 5. It confused me (while upsolving), and can confuse someone else. Supposing that the picture was made in MetaPost, it's a matter of several minutes for the authors to correct this.

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

    Yeah, thank you for reminding of that. Actually, only coordinates are wrong while the overall illustration is kinda correct. But you're right and it should've been corrected. Your supposition is wrong and it might take some time to fix it.

    → Reply