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

Автор fchirica, 11 лет назад, перевод, По-русски

Привет всем!

Мы приглашаем вас поучаствовать в Codeforces Round #225, который состоится в понедельник 20-го января в 19:30 по московскому времени. Это третий раунд, где я участвую в качестве автора (другие два: Codeforces Round #198 и Codeforces Round #191 (Div. 2)).

Если вы посмотрите мои прошлые раунды, то увидите, что главный герой задач — Яхуб. Один из авторов этого раунда — ... Яхуб... реальный человек, с которого взят главный герой задач. Знакомьтесь, Rares Buhai (rares.buhai), он же Яхуб. Он является автором задач Div. 2 C / Div. 1 A, Div. 1 D и Div. 1 E. Скорей всего, задачи покажутся вам интересными, поскольку их автор два раза становился золотым медалистом IOI (и он может участвовать еще два раза). Все остальные задачи готовил я. Они мне нравятся, но я буду не объективным, если скажу, что они интересные. Посмотрим, что скажут участники после контеста :)

Как и в прошлый раз, будет небольшой спойлер по поводу задач. Мы постарались сделать задачи разнообразными, насколько это возможно. Чтобы занять высокое место, человек должен уметь решать задачи типа “ad-hoc”, а также иметь хорошие алгоритмические знания.

Как обычно, мы благодарим MikeMirzayanov за Codeforces, Delinur за перводы задач, Gerald за помощь в подготовке раунда и DamianS и ll931110 за тестирование.

Желаем вам высокого рейтинга и фана от задач!

UPD Распределение баллов

Дивизион 1: 500 — 1500 — 1500 — 2000 — 2500

Дивизион 2: 500 — 1000 — 1500 — 2500 — 2500

UPD Контест закончился! Спасибо всем, кто участвовал! Должен сказать, что мы были сильно удивлены вашими необычными решениями задачи D в первом дивизионе.

Победители Div. 1:

  1. yeputons
  2. Arcueid
  3. Dmitry_Egorov
  4. ACMonster
  5. scott_wu

Победители Div. 2:

  1. Sick_coder
  2. akaring
  3. c0d3junki3
  4. raihatneloy
  5. sky0917

UPD Разбор задач

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

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

"Чтобы заполучить высокое место, человек должен уметь решать задачи типа “ad-hoc”・ а также иметь хорошие алгоритмические знания" — вот это спойлер. Удачи.

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

.

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

    Текст переводил я. Напиши, что тебе не нравится мне в личку, поправлю.

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

      Это третий автор, где я участвую в качестве автора

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

        Это раунд автор, где я участвую в качестве автора

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

      Если вы посмотрите мои прошлые раунды, то увидите, что главый герой задач –ач Яхуб. Один из авторов этого раунда –ач... Яхуб... реальный человек, с которого взят главный герой задач “чб”・

      Вот из этой фразы плохо понятно, что rares.buhai и есть тот самый Яхуб.

      Все-таки без Google Translate тут не обошлось:)

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

is the score distribution going to be dynamic ?

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

Hm, what is an "ad hoc" problem?

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

    It means that the problem has a unique, uncommon or unusual solution.

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

    Problem that depend only on observation , doesn't need a special algorithm to be solved with

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

    problems which are not based on any particular algorithm, and usually based on observations and deduction of patterns.

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

    Ad hoc problems are those whose algorithms do not fall into standard categories with well-studied solutions. Each ad hoc problem is different; no specific or general techniques exist to solve them.

    Of course, this makes the problems the fun ones, since each one presents a new challenge. The solutions might require a novel data structure or an unusual set of loops or conditionals. Sometimes they require special combinations that are rare or at least rarely encountered.

    Ad hoc problems usually require careful reading and usually yield to an attack that revolves around carefully sequencing the instructions given in the problem.

    Ad hoc problems can still require reasonable optimizations and at least a degree of analysis that enables one to avoid loops nested five deep, for example.

    I took this definition from USACO Training Pages. I recommend it strongly if you want to improve your level of problem solving.

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

It' s my first Div.1 contest, looking forward to it. And thanks to the authors, we can have another contest in a few days:)

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

Another round which is not during weekend :(.

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

Что такое "ad-hoc"?

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

Cool! Another round with Romanian problem setters. I can't wait to participate. Will Iahub also be the main character this time, too? :) Or will you also have a Sufle character? :) [ the reverse of elfus ]

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

    Thank you for the hint! It's just now when I realize what Iahub means (the reverse of Buhai).

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

Я не участвовал в Codeforces Round #191, но 198-й мне очень нравилось. Надеюсь, что 225-й (15^2) тоже будет хорошим :)

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

    "225-й (15^2)" ну просто ОЧЕНЬ важное уточнение:)

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

Good Luck to everyone!

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

Seems that it is going to be a very interesting round. Good luck to everyone..

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

Это мой первый раунд который я буду писать на Java надеюсь все нормально пройдет....

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

    судя по твоей последней статистике...вряд ли(

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

    Разве Вы все прошлые контесты не на java 7 писали? :)

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

Div1 500, 1500, 1500 ?!

I was aiming at solving A & B now I have to reconsider this :D :D :D

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

A round with a very interesting score distribution... It seems that I'll back to Div2 again :)

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

Do you wish good luck to everyone?

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

Размял пальцы в Guitar Hero, теперь приступим. :)

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

where is the link for problems ofRound#225

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

Finally, a round where we can see the score distribution earlier than expected....

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

GL & HF!))

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

I hadn't found any broken solution. Maybe pretests are too strong?

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

NO HACKS for div2! :o

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

    Actually there are. I suppose most of the solutions of div1 B/div2 D will fail.

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

Есть какое-то решение для C в div2 без дерева отрезков?

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

    Я делал без дерева, ибо чайник.

    Создал 2 массива: в первом считаю количество единиц, начиная с начала до каждого элемента, во втором — количество нулей, начиная с конца также для каждого элемента. Потом подсчитываю количество нулей во втором массиве непосредственно перед очередной единицей, и единиц перед нулями в первом. Результатом будет минимальное из двух полученных значений.

    Может это слишком"нубский" метод, но претесты прошёл.

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

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

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

    Утверждается, что ответ — это количество пар смотрящих друг на друга коров.

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

    Если это про коров то да, смотрим сколько коров смотрят друг на друга, идем слева направо, если она смотрит направо +1 счетчик, если она налево то ответ + счетчик. Если они смотрят друг на друга — значит одна точно потеряет молоко при дойке второй.

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

    У меня претесты прошло такое (возможно, упадёт на систестах, т.к. не знаю, как доказать): Посчитаем для каждой позиции i кол-во коров, которые смотрят направо и их номер <=i. Пройдёмся в цикле, прибавляя к ответу это число, если корова смотрит налево.

    P.S. Аналогичный вопрос про div. 1 B.

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

Problem C was interesting. Same for D where the answer was only 2n — 2 or -1. B was too boring a problem to waste time though.

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

was it a very hard contest for you or just me??

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

    I think it was good contest for me.

    I actually got quite much time to think on problem C which isn't usual for me in the contests.

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

    this is how a contest should be. neither too easy nor too hard. well done fchirica.

    PS: next time, try to improve the gradient of difficulty of the problems. that was the only thing lacking today. :)

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

Как решалась D(div 2)/B(div 1)?

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

    Там ответ либо -1 либо 2*n-2.Нужно проверить на -1 и все.

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

      Как за приемлемое время проверить-то?..

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

        Если полностью перекрывается 1 строка или 1 столбец. Или вулкан есть в клетках : (1,x) ,(2,x-1),(3,x-2) ... (y,1).

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

          Ну явно есть другие варианты. Например, что-нибудь вот такое:
          ......
          #....#
          .#..#.
          ..##..
          ..##..
          ......

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

      А как это доказать?

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

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

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

        Ну очевидно, что если мы можем двигаться только в двух направлениях, то с каждым шагом мы будем приближаться к цели на одну клетку. И любой путь, который мы пройдём (если сможем к ней дойти) будет иметь одну и ту же длину.

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

      Логично, однако, как проверить на -1?

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

        запишем в пары наши входные данные, потом отсортируем, первая координата Y в паре. Идем по вершинам, поддерживаем массив плохих вершин (одномерный). Каждый раз когда переходим на новый слой(т.е. у текущей вершины новая координата Y), если он не следующий (Yold != Ycurr — 1), то удаляем из плохих все, что не вплотную к началу (т.е. оставляем непрерывный отрезок от 1, если он был), если слой следующий (Yold = Ycurr — 1), то добавляем все его плохие в новый массив плохих (все вершины с Y= Ycurr), проходимся по старому массиву вершин, для значения старого v(это на самом деле x), если v — 1 в новом, то значит v тоже плохое. Для быстроты можно все на 2 сетах делать.

        • учесть прикол если на 1 слое стоят стенки и вправо за них не можем уйти никогда.
        • »
          »
          »
          »
          »
          11 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Массив плохих вершин? А как сжато хранить? Оо

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

            Эм, их максимум 10^5, кроме тех, что блокируются на 1 слое (т.е. если право не можем уйти)

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

              Ой... Кажется я понял, чем плохо моё недорешение.

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

      извиняюсь, потерто

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

Division 2B, it is intended that you can simply print every single pair?

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

    yaa..

    more like printing optimized bubble sort steps will do it within the limits of pairs allowed.

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

Кто-нибудь писал по C div 1 / E div 2 корневую эвристику? Если да, у кого-нибудь был с ней TL6?

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

    31 раз получил TL6, похоже корневая не заходит (Java)

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

      У меня на С++ не заходила. Вроде по ограничениям должна была. Даже смена массивов на векторы не помогла. А как ее решали вообще?

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

        Двумя деревьями отрезков — для чётных и нечётных по глубине вершин. Естественно, в порядке dfs-а.

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

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

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

        Заходит, за 1с. 5754923

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

        Мне кажется, надо делать меньше dfs-ов: где-нибудь раз в 1000 или 2000 запросов производить обновление, тогда зайдет. Не тестил.

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

          Избавился от рекурсии в ДФС-е с подачи Dmitry_Egorov, поднял константу до 4000, задача прошла (с 1000 и даже 2000 ТЛ на 11 и 18 тестах соответственно). Спасибо :)

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

    не уверен, но мне кажется что 6ой претест это т.н. бамбук и соответствующие запросы к самому нижнему элементу с изменением корня

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

what a terrible system test fail rate on Div 1 B...

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

div 2 — A is too basic

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

    it always is! those problems is designed so that every participant can get it accepted, even if he/she does it after one or two wrong submissions. :D

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

Very nice contest :)! The problems were very interesting and fun to solve!

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

Div1-B оказалась коварной: на систестах упало 142 решения, а удержалось — 41.

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

This round taught me it's more important to think more than code faster!
I could have much more time and points if I had thought some minutes more!
Thanks for good problemset ;)

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

Wow, system test for div 2 D was powerful!

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

    The whole system test was powerful :) I've amazed the speed. Maybe need some sleep to be more interesting :)

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

What's the point of additional constraints in div1E? It can be done in O(2K + N) regardless of how long are given strings. My solution passes in 280 ms.

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

    Cool! Can you share your solution?

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

      Suppose we have an array a of length 2K. We want to construct array b so that bi = . Partite a into two arrays a' = a[0..2K - 1) and a" = a[2K - 1..2K) and solve the problem recursively for them, obtain arrays b' and b". bi = b'i if i < 2K - 1 and bi = b'i - 2K - 1 + b"i - 2K - 1 otherwise. This is clearly a linear solution. Actually, this is a O(K2K) solution, my bad.

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

        As I can see, it is k*2^k solution as we have k levels with O(2^k) merge for each of them. I have exactly the same soltuion but I do it in non-recursive way. 5753388

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

    Well, the "easy" solution I guess was O(N+2^K*K^3) — by precomputing the amount of words with all possible combinations of 1, 2 or 3 letters and then solving each query with inclusion-exclusion formula, but I managed to optimize it to O(N+2^K*K^2) by using some previous results and that was enough. But this solution heavily uses that the length is up to 3, so that we can stop inclusion-exclusion formula when there are more than 3 bits on.

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

I've solved the Div1-C with heavy-light decomposition. This is the first time when I use this in contest :) . Is there any simpler solution?

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

    I use heavy-light decomposition too.

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

    It is enough to decompose the tree in such a way that every subtree is represented by continuous interval. You can use a simple pre-order DFS and build a standard segment tree on top of the resulting sequence (or Fenwick tree).

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

    I converted the tree to linear brackets sequence. For each node, record the smallest begin time and largest the finish time of all the nodes with odd depth of the subtree. Also Record the even part.

    After that, just use segment tree to implement the add operation and the query operation.

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

На задачу Е див2/С див 1, тесты не очень правильные. Если рассматривать граф как ориентированый, то все ровно решение будет работать, хотя в условии написано просто про существование ребра между вершинами.

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

There is NO Accepted Solution for B in my room (16) ! I haven't seen any problem like this before!

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

Практически весь контест пытался написать решение с деревом отрезков на B. После контеста, наконец, отловил основные баги. И поймал TLE 9. Потому что я... Ну вы поняли, победитель по жизни, ага.

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

    Если кто-то сможет найти время и объяснить, в чём основные огрехи моего жуткого решения (помимо ущербного стиля), буду очень благодарен. Как мне кажется, ассимптотика решения порядка mlogn. Буду рад, если кто-то докажет обратное.

    5758834

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

Really weak pretests for problem B Div1!

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

    actually, i dont think the pretests were weak. it's just that the system tests were really strong!

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

    There is no weak pretests for problem B div1, there is just a lot of weak solutions :)

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

How exactly does -50 on wrong pretests work ? Will it only get reduced from that problem if we actually submit an answer for that problem otherwise not ?

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

    Only if you pass the system tests on that problem. And the hacks on it should always count.

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

    Each wrong answer on pretests gives you -50 score for that problem , but you will only get the penalty if you actually manage to solve the problem correctly, otherwise your score for that problem is 0.

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

    You will get the penalty only if you get AC on that same problem later.

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

I was stuck in B, and didn't take a look at D until there's half an hour left. This taught me to read all the problems before thinking.

It's the first time I solve D :)

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

    I took an unnecessarily long time on C — I could solve it quickly, but silly mistakes appeared. After I solved C, I solved D in about 20 minutes.

    D and B should've been swapped. The idea isn't really hard, but it's prone to mistakes.

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

А кто-нибудь уже разобрался, в чем такой ужас 13 теста в Div.2 D/Div.1 B? Я смотрю, много у кого на нем упало решение в обоих дивизионах.

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

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

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

    Похоже, что-то вроде этого:

    ...#..

    ..#...

    .#....

    ....#.

    ...#..

    ..#...

    Есть у кого идеи, как такое выловить?

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

      Мой BFS тут явно свалится... Так что пока что нет:(

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

        n<=10^9. BFS тут свалится даже если попытается найти путь в пустой матрице без вулканов =)

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

          Нет Не настолько тупой bfs Если идти по вулканам, доставая их из сета. Мы можем за как раз m log m найти, есть ли у нас "замкнутые" области вокруг клетки 1;1 или n;n Но сюда уже видимо никак не прикрутишь запрет на ходьбу вверх и влево

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

          Конечно я бы не стал писать bfs тупо по матрице :D я б даже создать такую большую не смог бы...

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

      Слишком фейлово, чтоб быть на виду)

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

There is 150 test cases for B! But All of the failures are on tests less than 13!! :)) I think 13 test cases were enough!

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

thank you for great contest, but pretest was a bit weak on problem B div 1.

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

Hello.. I just want to ask something.. why my code got Wrong Answer on Problem A?? When I compile it from my laptop, it gives me the right answer.. And when I submit another for practice and just delete some STL include but my main code is still the same, it keeps get Wrong Answer and the Wrong Answer's test case is not the same.. First it is on Case 8, then second on case 7, the third one on Case 9.. What is going on???

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

    you are trying to use element with indicies -1 and n in your array, Besides, you are using data in that array that was never initialized

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

    I modified your code and got AC 5759068. Hope this help you understand.

    If i == 0 then you don't need to check peta[i-1][j], the same is for j. And since you fill the blank from small ij's, you don't have to check peta[i+1][j] and peta[i][j+1] either.

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

what was the tricky case for problem D div 2 ?!

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

will there be any editorials for the problems? and when will be the ratings updated?

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

I got WA on pretest 2 problem B div2 and I lost 50 point :( . I am sure I saw this happened before for some participant and they didn't lose points for WA on given cases !!

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

Sad to get green again...T_T

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

Thank you for the contest, and, specifically, for the Div 1/D task.

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

    For me, D was the least interesting xD

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

      Considering that the reason I found it beautiful was because of how well the simple solution is hidden in the task, I do understand your point of view that if you haven't solved it, you might find it the least interesting problem of the lot.

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

        Let's not jump to conclusions here :) I began solving it 10 minutes before the end of the contest and finished it 1 minute after the end. So yeah, not interesting.

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

          OK, sorry, I thought that I had looked at upsolving results and somehow failed.

          Anyway, yeah, I most likely enjoyed it was because I didn't stumble upon that idea immediately. If one manages to immediately get to it out, I can even more see how it would be not interesting at all.

          Or maybe I just liked the problem so much with no logical reasoning behind it.

          And by the way, congratulations with the new colour!

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

I tried to hack this solution generating the worst case for bubble sort, in which it should TLE, at least in my opinion. Am I wrong ?

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

Nice contest. Good joob elfus&iahub.

mlc

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

Does anyone has an idea why my program output for the first example test case in the problem B (Div 2) fails?

http://codeforces.net/contest/384/submission/5758977

It looks like as if it was correct..

  • »
    »
    11 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
    initial state :
    1 3 2 5 4
    1 4 3 2 5
    step 1 (pair 2 3):
    1 2 3 5 4
    1 3 4 2 5
    step 2 (pair 2 4):
    1 2 3 5 4 ( 5 > 2 no swap)
    1 2 4 3 5
    step 3 (pair 4 5):
    1 2 3 4 5 (sorted)
    1 2 4 3 5 ( 5 > 3 no swap)
    
    the second array is not sorted at the end !
    
  • »
    »
    11 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    for first index in output, your array becomes

    1 2 3 5 4 1 3 4 2 5

    for next index in output, your array becomes

    1 2 3 5 4 1 2 4 3 5

    for last index in output, your array becomes

    1 2 3 4 5 1 2 4 3 5

    Now see, second array is not sorted in ascending order. So it's wrong...

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

I didn't like Div2-B. But, C was an awesome problem.

And the pretests of A,B,C was strong enough. Technically The system test of Div2-D was the strongest I have ever seen!!!

Thanks to the authors for a nice contest. :)

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

I just study C about 3 months so I feel very worst :(( . Can you share code of Div 2 for me ? My email: [email protected]. Tks all :)

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

ratings are not updated yet :(

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

А когда разбор будет?

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

Who's the lucker here???)))

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

Yes! 266 Points added! Any way, I still think that Div2-D is too tricky to solve. And I feel lucky that I solved Problem E first. :)

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

nice contest !!!!

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

What a good luck! One Codeforces round that I didn't [have time to] participate in, and exactly in this one, most of my div 2 friends got >= +100!

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

O(sqrt(N)*N) get accepted for div1 C! 5762148

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

    Oh, if only you knew how many problems on trees I've solved in ...

    It's nothing rare, if the time limits aren't tight. Solutions in often have large constants, caused by the use of segment trees or some more complex operations. Simpler decompositions have worse complexity, but small constants, so they aren't much slower.

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

Where is the Tutorial?

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

Thanks

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

can someone explain a simple solution that everyone writes :) in Div2-C !