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

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

Привет, друзья)

Уже скоро состоится очередной раунд Codeforces #171 для участников Div. 2. Как всегда, участники Div. 1 могут поучаствовать в соревновании вне конкурса.

Вновь и вновь для вас старалась уже знакомая группа авторов в составе: Павел Холкин (HolkinPV), Игорь Кудряшов (Igor_Kudryashov), Николай Кузнецов (NALP) и Геральд Агапов (Gerald). Традиционно хотим поблагодарить Михаила Мирзаянова (MikeMirzayanov) за системы Codeforces и Polygon, а также Марию Белову (Delinur) за перевод условий задач.

UPD: распределение баллов по задачам будет немного нестандартным: 500, 1000, 1500, 2000, 2000.

Надеемся, что соревнование окажется удачным для всех участников. Мы желаем всем высокого рейтинга, успешных взломов и хорошего настроения)

UPD2: соревнование завершено, надеемся оно вам понравилось)

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

1) study_english
2) ipip2005
3) rng_50216
4) bfrcns197
5) csavky103

UPD3: разбор задач можно найти здесь

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

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

Hope this contest will be great as all the others.Good luck to everyone!!!

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

I love Russian thinking in preparing contest problems ,Hope short statements & easy English words . GL & HF

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

Starting to prepare includes...

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

    Instead of preparing them before every contest, I advise you to set all things in your default source of whatever compiler you might be using, so that when you create a new file( program ) you will have already the predefined code. It will spare you a lot of time.

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

Hi everyone, I has just viewed dj3500's screencast: CodeForces #169 div2. I saw the "hightail" program and go to https://github.com/dj3500/hightail but I don't know how to install it. Can someone help me?

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

Again and again only div2 contest :( .

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

    I think that they want to increase the number of Div1 users, because Div1 contests make many users become div2 users.

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

Hope me can change the rating color to purple!!Keep Calm and type the code more quickly! the same to everbody! but, it seems that i got fever:(, It's feel terrible Now:(

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

Павел, только не забрасывай написание контестов. Эти контесты хорошая тренировка для нас.

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

Hey guys, no hope for a late reg? Please! I was just 3 mins late

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

it sounds like 50216 is a popular number. (rng_50216)

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

The user bfrcns197 solved problem E in 3'rd minute! Seems strange to me..

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

I was really surprised to see that E was identical with D from a past Div.1 round (132D - Constants in the language of Shakespeare). I just copy & pasted, commented out a single line, and got pretest passed...

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

    Can someone please give me a more simple example than test 10 of why my greedy approach is failing? http://mirror.codeforces.com/contest/279/submission/3248428

    I keep 2 counters, number of zeros and number of ones. I look at all groups of consecutive 0's and consecutive 1's. If such a group has size 1 , i increment the corrsponding counter, else, I increase by 2 the corresponding counter. In the end, the result should be min(number 1's , number 0's + 2), representing that either we erase all ones or try to convert all 0's into 1's and do 2 more operations at the end.

    Thanks !

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

      well i guess here is your problems

      for 1counter:

      if you have two blocks of 1 with more than 2 numbers seperated by only a number 0 (11011) you will only need to change the 2nd group into (11100) in 1 steps, so you get another block of number 1. to convert it you need 2 steps. so 3 in total.

      however, based on your solution, cause you have 2 blocks of '1' size 2, you need 4 steps.

      testing pretest 3, you luckily right because the number of '0'. but when they increase 1counter and 0couter by adding '100', your 1counter is far bigger than 0counter, so the ans must be based on 1counter.

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

Как решалась D за O(2^n * n)?

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

    Сделаем предподсчет m[mask] — маска чисел из a которые мы можем получить попарными суммами чисел из a которые есть в маске mask. Это делается за O(2nn) убиванием младшей единицы в mask взятием маски от полученной маски и дальше поинтером идем по отсортированному a чтобы проапдейтить m[mask] попарными суммами содержащими младший (убитый) бит. Дальше динамика z[idx][mask] — сколько итераций прошло и какая маска, но понятно что idx — это просто позиция старшей единицы в mask, поэтому idx в состоянии не нужен. И осталось перебрать переход за O(n).

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

Не, ну ребята, я заявляю свои авторские права!:) http://mirror.codeforces.com/contest/132/submission/1098610 http://mirror.codeforces.com/contest/279/submission/3249012

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

    Приношу свои извинения!

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

      тогда все OK, да.

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

      Это была шутка, можете копировать мои решения сколько угодно, я польщен:)

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

    удивительно, а в чем смысл, какая у нее цель? высокий рейтинг? как то тупо!

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

      А в чем цель писать задачу, к которой есть в кармане решение, заново? Высокий рейтинг на клавогонках по словарю своего языка?

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

    На Codeforces уже столько задач, что скоро можно будет рандомно выбирать 5терку из архива..

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

За 6 минут до конца получил TL. Переписал рекурсивную динамику на итеративную. Не заработало. За 10 секунд до конца исправил баг. За 7 секунд до конца послал. Получил Претесты пройдены со временем работы 2000мс.

Какие ставки пройдет/не пройдет?

UPD: прошла)))

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

    На первом контесте в первом моем ПТЗ, мы долго пихали какую-то задачку. Добавляли лишние предподсчеты. В итоге пихнули. После контеста, нам сказали, что мы сдали задачу с запасом в 20мс от TL, 1MB от ML и 15 секунд до frozen.

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

E решалось жадно? и такая задача уже вроде была на кф, называлась, кажется, Шекспир.

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

    Я решал динамикой z[i,j] сколько позиций обработали и какая степень двойки уже набрана в позиции i (-2 <= j <= 2). Перебираем еще сколько возьмем текущей степени (-3,3) и делаем переходы. Здесь везде границы конечно должны быть от (-1,1) я просто не хотел разбираться со случаями.

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

    Я решал жадиной. Начиная с конца строки искал первую единицу и смотрел что перед этой единицой. Если тоже 1, то к строке делал прибавление числа (1<<разряд). Если 0, то вычитал 1<<разряд.

    На дорешивании прошло.

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

:( Я считал, что в задаче B книги расставлены по кругу, и нужно выбрать книгу, с которой лучше начать движение по кругу, затем читать, пока можно. Более часа потратил на дебаг, в итоге не успел дописать C , epicfail и 923е место.

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

    да всяко бывает) я теперь наверное сопьюсь от того, куда поставили задачу А) Технично так вынесли ею мозг в начале раунда. После этого про Б что только ни подумал — и про круг, и про параллелепипедик.

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

      +1 давать задачу на довольно трудоемкую реализацию в Div2 A есть не хорошо

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

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

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

        А эмуляция уже не в моде? Я вот за 6 минут написал и норм, фиолетовый. (:

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

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

          P.S. Поздравляю с выходом в див1 :).

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

E was easier than A, what a terrible contest !!! .... :o

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

    Is there any easier way to solve it rather than simulate the spiral per coordinate ? (Problem A)

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

      You can 'push' the given coordinates to the corner. Then handle the corner cases. Then it's just O(1) math stuff per query

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

        I suppose 'easier' meant faster. So calculating all the formulas was time-consuming, while writing simple emulation took 6 minutes only. (:

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

    So we learned the knowledge, and to grow in experience.

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

I wish every rating updates were as fast as the sysTests :)

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

Неужели я один неправильно понял это предложение в задаче B и потратил из-за этого уйму времени?

" Каждую книгу Валера читает целиком, то есть он не читает книгу, которую не успеет дочитать до конца из-за нехватки свободного времени."

Я почему-то понял это так: можно пропустить книгу, если не хватит времени ее прочитать, и продолжить дальше читать следующие книги. Кстати, кто-нибудь знает, как решать задачу в этой формулировке?

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

    http://en.wikipedia.org/wiki/Longest_increasing_subsequence

    upd: Человек спросил, можно ли решить задачу в формулировке, в которой он ее понял, я дал ему линк на то, о чем он спросил, внимание вопрос: за что минусуют?

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

      9 человек не понимают, как наибольшая возрастающая подпоследовательность относится к этой задаче

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

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

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

      Это неверно: n=5, t=7, a={3,4,2,4,2}, правильный ответ 2 (исправил тест, раньше было неправильно)

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

        По всей видимости, имелось ввиду решение задачи в той формулировке, в которой понял I_love_Chelsea.

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

          Ну оно неверное, выше приведен контртест

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

            отсортировали: 2 2 3 4 4. под t=7 подходят первые 3 элемента — 2 2 3. Среди них самый левый в исходном массиве — 3. начинаем читать с него, пропуская все ненужные книги.

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

              Вот только после прочтения первой книги мы обязаны читать вторую, так как времени на нее хватит

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

                Да, я не заметил разницы между "Можно пропускать книги, если не хватает времени" и "можно пропускать книги, если мы захотим".

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

              Если я правильно понял, I_love_Chelsea подразумевал возможность пропускать лишь книги, которые нельзя прочитать. А Вы хотите пропустить вторую книгу в исходном массиве с "ценой" 4, а 4 + 3 <= 7.

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

Am i the only one who thinks that final testing on the last few contests run much quickly than earlier ?

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

Странно, что задача Е уже была Д див 1, а сегодня стоила столько, сколько д див 2=) Может, потому что баян?)

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

    Прошу прощения, если обидел авторов шуткой. Все-таки трудно отследить все задачи.

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

      Неужели авторы хранят обиду вот уже четыре года?

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

Am I the only one who couldn't hack? I couldn't even see source codes.

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

Could someone help me find out why my code for problem C is failing? Here is my code . It got WA in test 21.

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

По задаче E:
11:42

Просто вспомнилось :)

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

    Спасибо за интересные задачи. Но мне показалось что задача C легче A.

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

      Мне кажется, что задача А — чистая реализация или математика, кому как. Задача С была хоть и несложной, но всё-таки более идейной, чем А. Так что порядок вполне логичен (это моё сугубо личное мнение).

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

      За что мне спасибо? :)

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

Объясните пожалуйста, почему в C нельзя было за один проход для каждого элемента посчитать, где заканчивается лестница, начавшаяся на нём, а потом при обработке запросов смотреть ближе ли левая граница запроса, чем посчитанное число?

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

    Почему же нельзя? Можно! Многие так и делали, насколько я видел.

    P.S. Надеюсь, "за один проход для каждого элемента" подразумевало один проход для всех элементов? (:

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

I think one of the reason behind low solve of Problem D is Poor Description.. I have read it more than 5 times, still i haven't understood what is the problem !!

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

what's the relationship between rng_58 and rng_50216?

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

Lots of solutions for D gave incorrect answer for the following test case:

2 1 1

Edit: My test is wrong. The numbers are distinct

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

I can't see what 's wrong with my solution to problem C Can anyone help me with that? submission : 3245705

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

    Check test: 3 1 2 1 1 1 3

    Strange that it passes all the previous tests.

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

      Very thanks. I found the bug; if we get another array for the size of good sequence which ends with "i", it would be ok!

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

    Input: 6 1 2 1 1 1 1 1 1 6

    My solution prints "Yes" and it seems to be ok, but your solution prints "No".

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

задача Б

10 15

10 9 1 1 5 10 5 3 7 2

Вывод:5 {читаем с книги №3} разве не так?

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

а никак не 3

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

    Как раз-таки 3, а не 5: если читать с книги №3, мы успеем прочитать 3-ю, 4-ую, 5-ую и потратим на это 7 минут. А 6-ую нам уже не успеть, ибо 7 + 10 > 15. Мы же можем только подряд книги читать, а пропускать нам никто не разрешал. Кажется, это уже обсуждалось здесь.

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

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

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

      "Каждую книгу Валера читает целиком, то есть он не читает книгу, которую не успеет дочитать до конца из-за нехватки свободного времени."

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

Can anyone explain Problem B (279B — Books)? This is how I understood the problem:

We are given an array A and an integer t. We have to search for a "sub-array" of A whose sum of elements is at most t. The answer should be the maximum length of such a sub-array.

However, I must have misinterpreted the problem. I have looked at some submitted solutions and they involve forming the sum of the first j elements of the array A and then substracting the elements A[k], A[k+1]... A[L]. Somehow two "pointers" j and k are involved which I do not understand.

I'd be grateful if someone could explain this. Thanks.

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

    You interpreted the task properly (if by subarray you mean a substring). You can calculate the solution in a single pass through the array, such that when you are at the j-th position, you also store the minimum i such that [i..j] is the maximum substring that ends in j. What you do is add the j-th value to the current sum, and while the sum is larger than t, subtract the i-th value and shift i one space forward. After each step is done, check whether the current interval size is larger than the maximum recorded so far and you're done.

    Here's my code for that: 3240473

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

      Your explanation is excellent! I first tried to solve it by searching for subarrays (substrings) [i..j] with maximal length and sum<=t by using two loops and got a timelimit exceeded, I guess since it results in O(n^2) runtime.

      Your algorithm is a clever idea with only O(n) runtime. Thank you PetarV!

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

        You also could have done it in O(n*log n) by keeping d[i]=sum{a[1..i]} and for each j=1..n binary search for the largest k>=j such that d[k] <= d[j-1] + t.

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

      I don't get it, why does it works?

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

how can we solve problem D ? I gave a solution with complexity O((n^2)*(2^n)) but definitely it gets TL.

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

    at first my solution was O((n^2)*(2^n)) and than I used that every number is distinct for precompution and got O((n^2)*n) . so think about it...

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

It's been quite a while since the contest ended. When will the editorial be published?

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

The editorial is late... can some1 please explain E.. I saw many codes.. but i dont understand how they arrived at that solution...

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

    +1 I used the greedy method to solve this problem,but i don't know how to use DP to solve. can some1 explain?

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

It's been quite a while since the contest ended. When will the editorial be published?

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

Please publish the tutorial quickly

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

please publish the editorial as you said.

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

    Comon guys, some of us are still very curious to see how dynamic programming applies to D and E.

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

      This is how I solved the problem, hopefully the reasoning is right For E using dp, Let a single move = addition of 2^k or 2^-k s = the binary string, s[0] being the first digit = the last character in the string

      Let dp[POS][i] = minimum number of moves needed to get a string l such that l[0..i] exactly match s[0..i] and l[i+1 ..] = 0 Let dp[NEG][i] = (same as above) l such that l[0..i] exactly match s[0..i] and l[i+1 ..] = 1

      If s[i] == 0, then dp[POS][i] = dp[POS][i-1], since you don't have to make any additional move. For dp[NEG][i], we can either make our move from a [POS][i-1] state, where we have to turn all bits from l[i+1....] to 1, but leave l[i] =0, so this takes 1+dp[POS][i-1] (just a single move, note that a negative power of 2 turns all bits to the left to 1, but leave the right bits unchanged -> -2^k = 11111... 000..). Or, we can make our move from a [NEG][i-1], which means we have to turn the ith bit to 0. This we can do by adding a single positive power of 2, which means only 1 extra move. Thus. dp[NEG][i-1] = 1+ Min(dp[POS][i-1], dp[NEG][i-1])

      And for s[i]==1 case, similar reasoning. Base case -> dp[POS][0] = 0 if first bit is 0, 1 if first bit is 1, dp[NEG][0] = 1, because you still have to make the bits to your left =11111...

      EDIT: whoops, something is wrong with my reasoning.. Hold on... EDIT EDIT: k nvm, I was confused about something else. Hopefully someone can agree/point out mistakes?

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

А почему товарищу albert96 дали +83 за этот раунд? Он вроде был в 1-ом диве и участвовал вне конкурса

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

When will the editorials of this round come out? The editorials of the next 5 rounds are already published. @admin: please prepare it as soon as possible.

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

Very good

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

tutorial please ?!

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

tutorial please ?! really need it !

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

Editorial -> when? please. Thnakyou.

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

Can someone tell me the logic behind this problem? 279C - Ladder
I've tried reading other people solutions but I dont understand properly.

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

    Vicennial Did you find it out? If possible, could you explain the solution idea?

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

      As explained in the editorial , for each index you should find

      i) lowest index i where decrement occurs (most people implemented it as array moving right to left and noting index where a[i] > a[i+1])

      ii) largest index j(before that index) where increase occurs , (implemented as array from left to right noting most recent index where a[i] > a[i-1] )

      now for subarray [x,y] ,if most recent decrement for index x is 'i' and most recent increment for index y is 'j' then, if( i <= j ) then segment is a ladder 35071213

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

        Can you explain the logic please? :)

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

          now for subarray [x,y] ,if most recent decrement for index x is 'i' and most recent increment for index y is 'j' then, if( i <= j ) then segment is a ladder.

          Explanation : think of it this way — if the segment is a ladder first all the increments should occur then all the decrements. eg 1 2 3 4 2 1

          Now for 'x' we look at the closest index on its right where decrement occurs . (say A) , Also for 'y' we look closest index to left where increment occurs say(say 'B') . Now A < B will only happen when the segment is a ladder . Try out some cases to verify this

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

Why am I getting WA in 19th test case for problem C ? Is there some extreme tricky case ? Here is my submission — Submission

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

You should have posted the editorial as the questions were good. Hope you do it atleast now. @HolkinPV

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

Could anyone explain why my code is wrong. Means could anyone give a possible test case/explanation of why my code is wrong. Link of submission attached-> (https://mirror.codeforces.com/contest/279/submission/101634918)

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

    I think this case 1 2 1 1 2 1 might fail your solution. For this case, array brr will always have zero values since if the query is L = 2 and R = 5, the answer should be No while your solution might output Yes