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

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

По многочисленным просьбам, делаем отдельный тред для объявления\обсуждения очередного раунда Алгоритма, который пройдет 30 мая в 05:00 (UTC +3). Раунд пройдет по системе TCM/Time и продлится 100 минут.

Пока ждете начала раунда можно потренироваться решая задачи предыдущих соревнований.

Не пропустите!

Обсуждение квалификационного и первого отборочного раунда.

UPD Третий отборочный раунд начнется по расписанию 6 июня в 13:00 и продлится 100 минут.

Время и дата раунда 2.2 уточняется, следите за обновлениями в расписании

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

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

I understand that you wanted to make Yandex available for people all around the world, but since score from eliminations is summed and vast majority of people competing are from Europe and Asia (mainly Russia) then it's just sadism to schedule round on 4 AM :P (5AM for Russia). I guess that moving it 4 hours forward or 4 hours backward will make it much more available to many people and it won't make a significant difference for people which live in timezones where this hour is comfortable.

Nowadays, following TopCoder usually brings nothing good ( ͡° ͜ʖ ͡°)

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

    Sadism is part of Russian culture :)

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

    5AM for Russia

    5AM in Moscow it's noon in Vladivostok.

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

      Or 3AM in Dublin. Just no :) Sorry for top participants who will have to participate in this absurd.

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

      OK, you got me there :). Though I know that China despite its size is in one timezone :P.

      By the way, are there many top competitive programmers in Russia outside bigger cities in west like Saint Petersburg, Moscow or Saratov?

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

Internal Server Error

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

Internal Server Error

Is it really so difficult to handle 2,000 people online?

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

Видать, организаторы умнее меня и в 5 утра спят :)

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

В добрых традициях Yandex — с первого раза не получилось )

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

codechef working smooth .. yandex site down .. parallel universe!

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

Ok, guys. Let's go back to sleep.

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

Internal Server Error ) 5 am is very nice time for jury :)

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

Не спишь тут до 5 утра, и такое :)

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

может жюри продлят контест на 10-15 минут из-за недоступности задач?

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

How to solve "Internal server error" problem (Spoilers):

Reduce it to external server error and then it is dynamic programming on servers

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

Can juri just paste problem statements here?

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

    May be they will decide to change date of round, there is no reason to spoiler problems.

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

    Yeah, and have us PM them our solutions.

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

    You probably shouldn't (unfair advantage to ppl who don't visit CF frequently), but you probably can (as in: it probably won't be removed immediately). Mathematical answer! :D

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

    Bad solution.

    1. Most but not all of the participants read CF.
    2. Looks like nobody has read the statements, that's ok.
    3. TCM/Time looks even more strange if we can't submit.
»
9 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

I think we have to sleep :(

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

I recommend open an incognito window/cleaning cookies for those getting ISE.

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

It seems that some people have already seen some problems statements...

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

Come on!

It has been 20 minutes. Will you postpone it or what?

Are you waiting for gaining more hate of contestants who wake up in the middle of the night?

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

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

Am I need to register for this contest? I have participate in Round 1?

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

Ну сообщите хоть, что анрейт, чтобы я со спокойной душой ушёл спать

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

    А то точно сейчас хочется цитировать nk.karpov "Sadism is part of Russian culture :)"

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

      А мне уже Лида сказала, что я могу идти спать, часа пол назад.

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

Its 4:24 AM in the morning here, i slept only 2 hours and woke to participate this contest and now its Internal Server Error, give us some update lperovskaya :P

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

    You should go back to sleep, you'll only have an unfair disadvantage, since some people have seen the problem statements.

    At least you're not in a bus with laptop battery charged barely enough for the contest in the original time frame (okay, even less than that).

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

Ну это нормально вообще? Я встал в 4:30 утра перед GCJ Round 2 ради этого!?

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

Единственная страница, которая у меня иногда открывается, это таблица результатов. Вполне себе садизм, да.

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

I thought previously that Bayan did really bad...but here you go...

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

Codechef is more stable than Yandex, what a time to be alive!

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

Может уважаемые организаторы уже скажут что-нибудь хорошее, например, что можно с чистой совестью идти спать, а не нажимать F5.

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

Странно, задачи висят в очереди, одна тестируется уже десяток минут, другая даже не начала проверяться.

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

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

У меня задача C загрузилась...

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

I wonder if somebody is working on that or they just sleep at this late night/early morning time :)

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

Yet another F5-style contest :(

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

Предлагаю отправлять решения по почте. Форма отправки не работает никогда.

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

I think this contest should be postponed.

I just get off from the bed to participate in this contest while my girlfriend is waiting for me and doubting of my motive in the midnight. Now, I don't understand should I wait for the contest or go back to my girlfriend.

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

what is the problem???

I have exam an hour later and can't submit anything!!

PS: now I can not see problems either!

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

Как все же отправить решения на задачу если у меня через раз либо Internal Server Error либо Список задач недоступен... ?

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

    По 20 раз отправляют... Впрочем, они всё равно не тестируются.

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

      30 май 2015, 05:15:24 696743 D GNU c++ 11 4.9 ожидание в открытую — — — — отчет

      Иногда появляется тестирование, вместо ожидание))

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

    Вопреки здравому смыслу, у меня при Internal Server Error посылка попадает в очередь...И там задумывается о вечном.

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

      У меня попала через несколько минут. За это время я успел подумать "о, не попало" и послать еще раз. Что за хрень...

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

    либо "форма отправки решения недоступна"

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

I wonder why they don't use Codeforces as the contest platform when Yandex 2012 went well on Codeforces. Now it's like a joke.

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

    I believe its "Not Invented Here" problem.

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

    I guess Codeforces doesn't yet support whatever minor unimportant modifications they want (like the blind/open thing). Make Codeforces more versatile and you avoid these problems.

    They should have canceled the contest after 20 minutes of this, tops. Very unprofessional. Not canceling it at all is even more disastrous (whoever f5s the hardest qualifies for onsite).

    Maybe they tried to cancel it but got internal server error.

    EDIT: After 1 hour, they finally got sane. Good night.

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

Ура, у меня открылись все задачи! Задача 1 — прочитать условия — успешно решена.

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

They said in QR such a problem won't happen in future rounds... hmmm

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

Хочу сказать добрые слова организаторам из Яндекс, но сейчас не могу ни одного вспомнить...

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

То чувство, когда написал задачу и отправил только через полчаса...

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

    ...а она ещё и не тестится.

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

    то чувство, когда отправил на 15-ой минуте, вердикт выдало за 15 минут до конца))

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

Из-за технических проблем с серверами системы Яндекс.Контест результаты второго раунда НЕ будут учитываться в результатах отборочного этапа. Время и дата второго отборочного раунда будут сообщены дополнительно. Приносим свои извинения за доставленные неудобства.

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

    Это всё из-за того, что я много порешал.

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

Technical issues

Due to technical issues with Yandex.Contest platform results of this round will not be taken into account in elimination stage results. We will inform you about new scheduled time for second round additionally. Sorry for the inconvenience

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

Due to technical issues with Yandex.Contest platform results of this round will not be taken into account in elimination stage results. We will inform you about new scheduled time for second round additionally. Sorry for the inconvenience

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

    Wow! How lucky am I! I have to be in class during the contest, and can't participate. Now I have chance to join it again :D Hope the additional round won't be held on this time again :(

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

      Idea of different times for contests was so that everybody could take at least one with convenient timing. So replacement round should be at the same time.

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

        But we already wake up at 5AM. It's so scary :(

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

          And I am just going to sleep — 23:00 here, tomorrow morning is GCJ Round 2. So nice timing for me ;) I will have to wake up early for one of the rounds too.

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

    Please do not schedule it at 4 AM..... x_0

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

      Lets be fair it's 4 AM not in all timezones and I think 3 rounds are trying to cover all timezones. =)

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

    And the next round 2 is going to be scheduled on the same time?(

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

Хочу передать большой привет организаторам, и поставить для них песню.

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

я обычно редко ругаюсь публично, но на «Из-за технических проблем с серверами системы Яндекс.Контест результаты второго раунда НЕ будут учитываться в результатах отборочного этапа. Время и дата второго отборочного раунда будут сообщены дополнительно. Приносим свои извинения за доставленные неудобства» я могу спросить только что за хуйня блеадь, пиздец нахуй. Я конечно понимаю, место в таблице — не самая важная вещь в жизни, это не входит даже в десяток самых важных вещей, но блеадь, как-то печально сегодня. Збс ваще. спокойно порешал бы в удобное для меня время когда-нибудь потом.

Задачи очень интересные, показались отлично сбалансироваными по сложности и отлично подготовлеными. Хочется поблагодарить авторов контеста. очень грустно, что так получилось. Решение контеста доставило кучу положительных эмоций несмотря на возникшие технические проблемы.

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

    А какой бы вы ответ хотели?

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

      Прошу отметить, что я не попал в топ-30, не получил ни одного очка гран-при и даже не рассчитываю попасть хоть однажды в топ-30 в 2015 году для прохождения на следующий этап соревнования.

      Как приемлимый вариант ответа — написать те же слова, но через 10-30 минут после начала раунда, а не под его конец.

      Второй вариант — расширить количество проходящих по системе yeputons

      tourist'у ничего не помешало сдать 6 задач, более чем десятку людей сдать 4 задачи, а мне сдать 2. И я сомневаюсь, что сдал бы больше, если б не было падений сервера.

      Я согласен, что при проведении раунда возникли проблемы и предполагаю, что решение о неучитывании результатов раунда может быть лучшим решением, но это не отменяет моего отношения к ответу. Нет ответа, который я хочу, но конкретно эти слова в этот день вызвали неприятие в голове.

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

Я ж правильно надеюсь, что разбор второго раунда все таки будет не смотря на все возникшие ситуации?

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

I want to have some words of support for contest staff here. Bad things happens on all platforms. Some people here asked "Why not Codeforces?", but aren't they very same people who would gladly complain about Codeforces server being down only if Codeforces would be available. TopCoder rounds got cancelled once in a while, etc. I think people would be much more forgiving if it would not happen in this particular round that scheduled at early morning/night for Europe

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

Да ладно всем ругаться. Вот Гене же ничего не помешало все сдать в слепую )

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

Предлагаю немного снаркомании: берём две таблицы (с результатами этого раунда и без), берём по системе гран-при сколько надо, объединяем множества, получаем список финалистов.

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

How to solve D?!

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

    If d = 2^p2 * 5^p5 then answer is max(p2, p5) Else impossible

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

    Take a worst case like a number = VeryBigPrimeNumber * 10^k + b, where b = h * d, where h = const. VeryBigPrimeNumber >>>> d, so you need that d = 5^p1 * 2^p2, beacuse 10^k have only two prime divisors(2 and 5) and you need that 10^k mod d == 0. So, if(d != 5^p1 * 2^p2) then ans := -1, else ans := max(p1, p2)! You can found p1 and p2 in O(logN). (My Internet is SlowPoke :) )

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

    Let's assume that the answer for some d is k. It means that we can decompose any integer n into a sum n = a × 10k + b and all we need to check divisibility of n by d is to look at b, i. e. a doesn't affect divisibility by d. Thus, 10k is divisible by d. If d = 2i * 5j the answer is max(i, j). Otherwise there is no such k, the answer is "impossible".

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

Как решить задачу A? Сам получаю TL код

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

    Это за квадрат, а надо за n log n. Будем хранить динамику dp[i] — количество способов добраться до i-ой ступеньки и массив префиксных сумм этой динамики pre[i]. Для каждого i можно бинпоиском найти максимальный номер j, такой что для всех ступенек с номером меньше j нельзя попасть в i. Тогда dp[i]=pre[i]-pre[j-1]

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

      И вместо бинпоиска поддерживать указатель на этот j, он будет двигаться только вверх. O(n)

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

        О, действительно, всё намного проще. Спасибо.

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

        Код можете показать?

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

            Не очень понимаю решение -- можете объяснит по подробнее ? Зачем нам массив sumdp и dp&

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

              Допустим, вы находитесь на i — ой ступеньке, вы знаете что вы можете попасть в нее со всех ступенек j, j + 1, j + 2 .. i — 1 , т.е. вам нужно знать сумму dp[x], j <= x < i : sumdp[i] — как раз сумма всех dp[x], 1 <= x <= i, тогда эта сумма равна dp[i] = sumdp[i — 1] — sumdp[j — 1], sumdp[i] = sumdp[i — 1] + dp[i]

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

How to solve E? I used such dp — f[len_prefix][wasC1][wasC2][wasC3][ost][flag] I fixed the three biggest numbers and then calculate dp. But it gets TLE. Who can help me? Code Link Here

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

    I had even one more field in dp [did we have only zeroes before] but wasC1..C3 were compressed to one bitmask 0..7 and I got AC in 2.8s.

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

      i had a dp with state[len][0..7][mod][flag][zero][C1][C2][C3]. It worked nearly in 198ms.

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

Before the round starts, this blog was +53. Now it's +16, and still decreasing. What a sad story :(( I think all contests should be encouraged, as all managers have tried their best.

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

I'm interested how to solve C without coding brute force for small numbers and looking for a pattern?

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

Как и два года назад, задача C — адский боян. Причем из серии "если знаешь идею, пишется за минуту".

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

How to solve A ? I am getting a WA on test 5. Submission.

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

    You need to compute the answer modulo 109 + 7.

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

    May not be the best solution, but you can solve using seg-tree with lazy propagation. For a height 'X' the number of ways is sum of number of ways of reaching height 'X-i' where 1<=i<=MaxJump . You can view this in a slightly different way that ways[X] will be added to ways[X+i] for i in the same range. Consider this as a range update (you can find the range indices using binary search) . Finally find the value of the last leaf of segtree, which is the answer.

    If there is a solution better than O(n*logn), please do post your solution.

    Code : http://ideone.com/gnBviP

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

        I didn't understand solition, please explain in simple words. I know about two pointer

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

          we know that dp[i] gets updated from dp[j] and dp[j+1] and ... dp[i-1] let's name this j az up[i] we know that if i < k -> up[i] <= up[k] so up[i-1] <= up[i] so we just need to move forward from up[i-1] to find the place that has less than m distance from i and that's that

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

      Another linear solution:

      Suppose dp[i] stores the number of ways to reach the ith step, and sum[i] stores sum of dp[0] to dp[i]. Also, you can store the cumulative sum of all the stairs uptil ith position in, say y[i]. now, you just need to search for lower_bound(y[i]-m) in the array y, and dp[i]=sum[i-1]-dp[lower_bound-1].

      http://ideone.com/jnj6zv

      Note: instead of calling lower_bound each time, you can preprocess the lower_bound indices in O(n) and calculate the dp and sum arrays in O(n).

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

Кто сдал F, у вас O(nlogn)?
Я O(nlog2n) ногами упихал, но кажется, что это не то, чего хотели авторы.

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

    У меня O(n log^2 n) на java без упихивания прошел

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

any updates on the new time of rescheduled round??

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

OK, so I will try to elaborate a bit more why organizing event at this hour is wrong and how it could be improved.

Firstly, we will use quantity argument. Look at the standings table. Keep in mind that this was middle of the night for Europe/West Asia. Scheduling hour of contest as such does good only for people from America (Northern and Southern). I just counted and there were about 14 people competing from those countries (USA, Argentina, Canada, Brazil, Dominicana and Cuba counted :P). And best of them was on 41st place. Does this really has any sense scheduling contest on that hour, making favor for that incredibly small amount of people and forcing about 200-300 not to sleep before 6/7AM? Moreover many people won't compete, so this competition kinda changes from "who is better programmer?" to "who can stay woken up longer?" and make results not reliable. Btw people competing at that hour have much smaller abilities, normally I would treat being unable to solve D as serious mental disability, but I managed to fail this either way :P (it was 5 AM >_>).

Considering people from America — isn't hour as one first contest was held at comfortable for them? If I'm not mistaken it's 1PM, so it superfine. 8PM in Poland/9PM in Moscow seems to be very good hour for people all around the world. Maybe for East Easia it is not that comfortable, so we can shift it 3 hours earlier. It is 9 AM in San Francisco and 1AM in Tokyo, so I think it's really fine. Given this — choosing hours 3 PM, 6PM, 9PM in Moscow would be the best option, because in that form everyone in whole world has at least 2 chances to compete in fine hours and amount of competitors such that they cannot compete 3 times not in the middle of night is much smaller than it is now.

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

    winger lives in USA, and he is on the third place.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    1. Not all of the competitor who live in America represent it on the competition, so this count is not really perfect.
    2. 9 AM can be a bit early for some people, especially for the ones that got used to wake up at 10-11 AM.
»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Возможно это уже спрашивали, но Раунд 2.2 будет после 3 — го или же нет?