Блог пользователя AndreySergunin

Автор AndreySergunin, 9 лет назад, По-русски

Привет, Codeforces.

Скоро, 27 июня в 17:00 MSK состоится очередной, 310-й раунд Codeforces, задачи для которого готовили я, Андрей Сергунин, и Егор Щербин (Lord_F).

Большое спасибо Максиму Ахмедову (Zlobober) за помощь в подготовке задач, Марии Беловой (Delinur) за переводы на английский, Михаилу Мирзаянову (MikeMirzayanov) за замечательные системы Codeforces и Polygon.

Участникам будет предложено пять задач и два часа на их решение. Разбаловка будет объявлена позже.

Желаем всем удачи!

В раунде будет использована динамическая разбалловка.

UPD: По техническим причинам раунд перенесён на 10 минут.

UPD: Добавлена предварительная версия разбора.

UPD: Поздравляем победителей:

Div 1

  1. qwerty787788

  2. Petr

  3. Haghani

  4. KADR

  5. zxqfl

Div 2

  1. onufryw

  2. munaiyi

  3. _h_

  4. Chenyao

  5. mhadih

  • Проголосовать: нравится
  • +392
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится +35 Проголосовать: не нравится

Фан-картинка к контесту, которую Андрей почему-то решил не прикреплять к анонсу:

»
9 лет назад, # |
  Проголосовать: нравится +47 Проголосовать: не нравится

Thanks for the schedule change!

Looks like my ranting served its purpose :)

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +34 Проголосовать: не нравится

    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.

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

Your curve is very inspiring :))

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится -7 Проголосовать: не нравится

Почему не на главной странице?

UPD: В то время пост не был на главной.

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится -42 Проголосовать: не нравится

Consecutive Div1 + Div2 Contest :D

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Good luck all, hope a good rating for all.

»
9 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

Мне показалось, или раунд сначала планировался на вечер пятницы?

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    Я не против переноса, просто я запланировал для себя участвовать в одном раунде на любом из сайтов один раз в неделю (Topcoder, Codeforces, Hackerrank и прочие), но в удобное для меня время. В понедельник я решал, какое соревнование посетить, выбрал это, но тогда была указана пятница. В итоге, я пропустил все остальные соревнования, а это вдруг перенесли на субботу, когда у меня нет никаких шансов на участие. Обидно.

»
9 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится +34 Проголосовать: не нравится

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

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится +22 Проголосовать: не нравится

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.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    i'm agree with you

  • »
    »
    9 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +30 Проголосовать: не нравится

    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)

»
9 лет назад, # |
  Проголосовать: нравится -20 Проголосовать: не нравится

Izi problem, izi life

»
9 лет назад, # |
  Проголосовать: нравится +46 Проголосовать: не нравится

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

»
9 лет назад, # |
Rev. 16   Проголосовать: нравится -33 Проголосовать: не нравится

i wish all of you have great contest

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

  • »
    »
    9 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

    why downvotes ...

»
9 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

It clashes with Challenge24...

»
9 лет назад, # |
  Проголосовать: нравится -63 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

It's a good time to start the competition.

»
9 лет назад, # |
  Проголосовать: нравится -53 Проголосовать: не нравится

It's a bad time for muslim users

»
9 лет назад, # |
Rev. 3   Проголосовать: нравится +6 Проголосовать: не нравится

01010100011010000110000101101110011010110010000001111001011011110111010100100000001100010011011000100000

»
9 лет назад, # |
  Проголосовать: нравится -71 Проголосовать: не нравится

don't want a maths contest this time :P

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится -18 Проголосовать: не нравится

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

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +65 Проголосовать: не нравится

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

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится -20 Проголосовать: не нравится

      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 .

      • »
        »
        »
        »
        9 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
9 лет назад, # |
Rev. 5   Проголосовать: нравится -22 Проголосовать: не нравится

Waiting for the contest.

»
9 лет назад, # |
  Проголосовать: нравится -47 Проголосовать: не нравится

I hope there aren't math problems.

»
9 лет назад, # |
  Проголосовать: нравится -42 Проголосовать: не нравится

Участникам будет предложено пять задач и два часа на их решение.

Мне кажется что это не совсем точно отражает действительность. На самом деле будет предложено 7 задач, но по 5 задач для каждого дивизиона.

»
9 лет назад, # |
  Проголосовать: нравится -13 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

nice time,Hope I can go to div1

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Do you guys use information from the scoring?

»
9 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

delayed by 10 mins :(

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

It's delayed for 10 mins ):

»
9 лет назад, # |
  Проголосовать: нравится +61 Проголосовать: не нравится

10 min delay again

»
9 лет назад, # |
  Проголосовать: нравится +24 Проголосовать: не нравится

Первому раунду, начавшемуся вовремя будет выдана ачивка.

»
9 лет назад, # |
  Проголосовать: нравится +87 Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится -13 Проголосовать: не нравится

scoring ??!

»
9 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

This Time Is Better For Contests ..

»
9 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

    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.

»
9 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

может кто нибудь обьяснить как изменяется вклад у участников, почему у меня -1?

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I wanted to participate but i couldn't because of the unusual timing, the registration closed two minutes before I checked :(

»
9 лет назад, # |
  Проголосовать: нравится +78 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится +37 Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Any suggestions on how to solve Div. 2 D?

»
9 лет назад, # |
  Проголосовать: нравится +101 Проголосовать: не нравится

Changing of description of Div1A was too critical

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

    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.

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится +69 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится +43 Проголосовать: не нравится

        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.

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится
      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится +19 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          9 лет назад, # ^ |
            Проголосовать: нравится +4 Проголосовать: не нравится

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

          • »
            »
            »
            »
            »
            »
            9 лет назад, # ^ |
              Проголосовать: нравится +5 Проголосовать: не нравится

            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.

    • »
      »
      »
      9 лет назад, # ^ |
      Rev. 3   Проголосовать: нравится +9 Проголосовать: не нравится

      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?

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится +22 Проголосовать: не нравится

Допустил мелкую ошибку в A из-за условия как будто на китайском языке и переслал задачу
@
Получил штраф как будто отправил ее через час

Участвуешь в раунде с динамическим подсчетом очков
@
Первые две задачи всегда 250 и 500

»
9 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

После таких задач понимаешь, что контесты на математику — просто манна небесная

»
9 лет назад, # |
  Проголосовать: нравится +56 Проголосовать: не нравится

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

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +18 Проголосовать: не нравится

    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.

»
9 лет назад, # |
Rev. 4   Проголосовать: нравится +2 Проголосовать: не нравится

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.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 .

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          9 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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.

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      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.

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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?

»
9 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится +19 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    9 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

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

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    the same here, this is my code

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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)

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      I also got stuck on test 10.

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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

      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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.

»
9 лет назад, # |
  Проголосовать: нравится +40 Проголосовать: не нравится

Не делайте, пожалуйста, больше задачки про матрёшек! :(

Или пишите очень формально, потому что разобраться, что от меня хотят в условии, было просто невозможно

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Матрешки это кадр. До оповещения не где в условие не было сказано, что вложенные матрешки в друг-друга нельзя вставлять

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Как решать матрешки?

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    По сути тривиальная задача — находим группу, которая начинается с единицы, смотрим сколько за ней следует возрастающих чисел (типа 1 2 3 4 5). Этот кусок мы не будем разбирать. Оставшиеся в этой группе разбираем и собираем (т.е. 2 * (len — found_len))

    Все остальное разбираем полностью и собираем полностью, это даст еще 2 * len — 1 секунд.

»
9 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится +102 Проголосовать: не нравится

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

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +19 Проголосовать: не нравится

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

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
9 лет назад, # |
  Проголосовать: нравится +30 Проголосовать: не нравится

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

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится

Back to div2.. see you guys ^_^

»
9 лет назад, # |
Rev. 5   Проголосовать: нравится -14 Проголосовать: не нравится

The contest was great !!!

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +45 Проголосовать: не нравится
    cin>>n>>k;
      for(i=1;i<=n;i++) {
    

    How did this pass 14 pretests?

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится +13 Проголосовать: не нравится

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

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

По-моему, в условии задачи Div1 A остался ещё один косяк:

... преступник, следуя загадочному плану, разобрал все матрёшки и собрал их в одну большую цепочку (1 → 2 → ... → n).

Отсюда можно сделать вывод, что даже если изначально цепочка была одна, то преступник всё-равно вначале её разобрал, а потом собрал обратно. Только из примера можно понять, что это не так...

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I am going to learn SET

»
9 лет назад, # |
  Проголосовать: нравится +30 Проголосовать: не нравится

Я не знаю, как работают появляющиеся оповещения, но почему-то то и дело они не появляются, или, наоборот, появляются снова и снова после закрытия. Хотелось бы иметь какой-то элемент на странице, который бы бросался в глаза, если есть непрочитанные оповещения, и не убирался бы до того, как пользователь откроет вкладку "задачи".

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

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

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится +6 Проголосовать: не нравится

      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.

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      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

      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          9 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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.

          • »
            »
            »
            »
            »
            »
            9 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится +31 Проголосовать: не нравится

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

»
9 лет назад, # |
Rev. 3   Проголосовать: нравится -11 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится +53 Проголосовать: не нравится

Спасибо авторам за интересный раунд.

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Somebody explain me problem C in simple langugage

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Problem statement or solution?

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

»
9 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Теперь ждем обновления рейтинга.... долго-долго ждем....

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Good time! Wish more contests like this.

»
9 лет назад, # |
  Проголосовать: нравится +39 Проголосовать: не нравится

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

Copy paste why...

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится -22 Проголосовать: не нравится

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

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится +14 Проголосовать: не нравится

      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

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +31 Проголосовать: не нравится

    for(auto it:M) WA

    for(auto &it:M) AC

    :)

  • »
    »
    9 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

    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). :'(

»
9 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    Please gcd let not my integers overflow today.

»
9 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
9 лет назад, # |
Rev. 3   Проголосовать: нравится +10 Проголосовать: не нравится

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

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится -8 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Я после объявления окончательных результатов был 783-м, но сейчас я уже поднялся до 768-го места. Как это возможно? Тут проходит еще проверка на читеров или что-то еще?

»
9 лет назад, # |
  Проголосовать: нравится +21 Проголосовать: не нравится

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.

»
9 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

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.

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится +27 Проголосовать: не нравится

Finally.

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

»
9 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    the same here in test case 2 !!!

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

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      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?

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    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

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Можно ли узнать, почему мои попытки были проигнорированы?

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится -27 Проголосовать: не нравится

    ПОТОМУ ЧТО СИДИШЬ ДОМА ЗА КУДАХШТРУДЕЛЕМ КАК СЫЧ, ВЫШЕЛ БЫ ХОТЬ НА УЛИЦУ ПРОГУЛЯТЬСЯ, СЕРВЕР УЖЕ ПЕРЕГРЕЛСЯ!

»
9 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

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.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    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

»
9 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

Разбора не будет?

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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)

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +21 Проголосовать: не нравится

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

    You probably wanted b.lower_bound() instead.

  • »
    »
    9 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

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

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится +39 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

When The editorial of round 310 will be available ?

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится +2 Проголосовать: не нравится

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

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится +10 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

looks like the editorial is going to take forever !!

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

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Nice contest!

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Что такое "Попытка игнорирована"?

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone share the link to the editorial ,I really didn't find it, in fact in contest material there is a link to the wrong editorial (codeforces round 309) thanks

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится -17 Проголосовать: не нравится

*Deleted

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится -21 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    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.