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

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

Доброе время суток!

Через несколько часов начнется очередной Codeforces Round #147 для участников Div.2, но традиционно остальные могут поучаствовать вне конкурса. Он был подготовлен небольшой командой авторов: я (NALP), Игорь Кудряшов (Igor_Kudryashov), Павлик Холкин (HolkinPV), Геральд Агапов (Gerald), Мария Белова (Delinur) и Михаил Мирзаянов (MikeMirzayanov).

Традиционно всем удачи, полных решений и удачных взломов!

В раунде будет использована стандарная разбалловка: 500-1000-1500-2000-2500

UPD: Соревнование завершено, поздравляем победителей:

  1. try_skycn

  2. AntiKismet

  3. dianbei_03

  4. Uncia

  5. Bigsophie

UPD: Разбор уже опубликован тут.

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

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

:-W

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

Gerald always gives a hand to prepare the problems in recent contests :D

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

Надеюсь что контест будет решаемым для обоих дивизионов. Всем удачи!

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

sorry for posting here but,My contribution is -69,I do not know what to do :(

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

Надеюсь сегодняшний контест будет не хуже предыдущего.

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

Have a good contest everyone! :)

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

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

PS. да почему этот вопрос игнорируют? или не царское это дело администрации отвечать на вопросы пользователей

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

Ничего себе "чуть позже" :)

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

What advantages does the stardand scoring system have over the dynamic one?

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

Стандартная разбалловка, класс !

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

seems, there is huge change for me to be hacked today.... :P

»
12 лет назад, # |
Rev. 2   Проголосовать: нравится -20 Проголосовать: не нравится
Заплывший мужчина

Заплывший мужчина

Заплывший такой

В заплывшей кровати

Лежит никакой.

Автор : Ионас Пакальнишкис

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

2730 -это случайно не рекорд !???

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

Не пойму, что надо курить, чтобы сделать задачу D? Ее тут кто-нибудь понял вообще?

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

    Подвешиваем исходное дерево за лист, тогда вершины — пары (x, parent(x)), , тогда рёбра есть между (x,parent(x)), (parent(x),parent(parent(x))). Все баллы чисто за условие.

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

5, ведь решалась mincost-maxflow?

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    for(int i = 0; i < n; i++)
    {
    	читаем строку, достраиваем граф;
    	обычныйMaxFlow();
    }
    

    Работает, так как граф хороший.

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

      Граф называется хорошим, если на нем всякая фигня работает.

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

        А почему не проходит решение: 1) Построить весь граф 2) Запустить MaxFlow? Точнее, работает до первого max теста

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

          Обычный, не mincost? Он же на всем подряд валится:

          a
          2
          a 1
          a 1
          

          Что мешает ему выбрать вторую строку? (Ну, кроме порядка обхода вершин)

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

      Отличная идея)

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

Возникли проблемы с окном (страницей) взломов. Вот скриншот. В лисе 16.0.1 под win7, если пытаешь проскролить до кнопки "Взломать", то скролл просто уменьшается и страница увеличивается. Получается можно только с помощью клавиши Tab изменить фокус на кнопку "Взломать" и потом нажать Enter.

Исправьте пожалуйста этот косяк.

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

Thanks for the good contest

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

Хороший контест. Сложность задач порадовала.

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

Расскажите, что нужно было сделать в C. Условие замудренное (.__.)

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

    Найти минимальное l, чтобы все подотрезки длины l содержали не менее k простых чисел

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

    По-моему самая понятная задача контеста :-D Нужно было найти такую длину отрезка, что если идти им по участку от a до b, то в отрезке будет не менее k простых чисел

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

    расскажите решение а то мои решето, дерево отрезков и бинпоиск не проходят по времени.

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

      Решето Эратосфена + бинпоиск + 2 указателя. Upd. Всего 78 мс на макс.тесте.

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

        Расскажите, как вы два указателя использовали? Я не могу понять, куда их воткнуть :( Я считал количество простых на префиксе, потом для отрезка совсем легко пересчитывать.

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

          Вместо префиксных сумм(двигаем отрезок, если (left — 1) — простое, то уменьшаем сумму, если right — простое, то увеличиваем(отрезок [left..right]).

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

      Решение С за решето + О(n) — без бинпоиска: Соберем все простые числа из нашего отрезка в массив р. Найдем максимальную разность (p[i+k]-p[i]) — это наименьшее L, покрывающее k подряд идущих простых чисел. Очевидно, ответ будет не меньше. Это L по сути подходит для любого внутреннего подотрезка. Значит, осталось проверить только "слева" и "справа". Найдем наименьшее x такое, что x>=a+L-1 и на отрезке [a,x] не менее k простых. Заменяем L на x-a, если нужно. Аналогично с другой стороны. Код, 46 мс.

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

        Хороший подход)

        Правда с бинпоиском тоже 46 мс)

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

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

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

check out my output here http://ideone.com/aCIGH7

when i run it as a custom test here i get this output instead

6
2 2 1 1
3 1 1 2
1 2 1 3
1 1 2 1
1 3 2 2
2 1 3 1

if I change the 2d arrays to maps instead i get the desired output. Any idea why this happens?

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

Как ломали А7

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

    У меня четверо(!) на:

    3 10 15 10 15 10 15

    Многие писали что-то такое:

    if (prevtime != newtime) {current_casses_needed++;}
    else {if (current_casses_needed > max_casses_needed) ...}
    

    Что приводило к грустным для них последствиям :)

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

    кроме перечисленных, был один написавший А за квадрат.

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

Wow , very fast judging :D

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

System test is really fast !!!

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

Как решать E?

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

Wow, what a fast judge!

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

Отличный контест! :)

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

Really enjoyed the contest. And it also helped me identify a bug in our ACM team's notebook. Many thanks to the author :D

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

скажите а почему в задаче С нельзя было хранить минимальную длину для каждого х между a,b такую что в этом отрезке k простых чисел? и потом просто идя от начала до n- l обновлять наш l как максимум из t[x] и l?

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

    мда( обидно крайний случай не учёл когда а = в и упала таска :(

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

Кто нибудь сдавал С за n*log^2 ?

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

    Такая асимптотика не должна заходить, так что сомневаюсь.

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

      у меня зашла с такой асимптотикой)

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

        Значит, можно было спокойно писать обычное решето Эратосфена?

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

          Не понял. Ассимптотике решета ой как далеко до n * log^2(n)

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

            Разве его асимптотика не O(n* log (log n) )?

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

              Именно. Только теперь я не вижу связи в ваших комментариях. При чем было это?

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

                Я увидел, что у людей заходит O (n* log^2(n)), и мне стало интересно, можно ли было писать обычое решето вмето решета за O(n), ведь O(n* log(log n) + n * log^2(n) ) = O(n*log^2(n)).

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

            Находим обычным решетом все простые числа, сохраняем их в массиве prime. Потом бинпоиском подбираем l. внутри бинпоиска пробегаемся по числам, смотрим, сколько простых чисел умещается на текущем отрезке (x, x+l-1). для этого, аккуратно используя в моем случае upper_bound и lower_bound над массивом prime, ставим первое и последнее простые числа в отрезке. ну и находим между ними расстояние. итого асимптотика получается n*log^2(n).

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

              А что, окном пробегаться трудно?

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

не самый лучший раунд: А и Б можно было сделать поинтеллектуальнее, С — в некоторых раундах это 4мерная дп или бешеные хэши (раунд 141), а в некоторых вот такая халявка, Д — не понимаю, зачем такие задачи давать, просто надо понять укуренное условие, и она сразу переходит в разряд уровня B/C, Е — безыдейная, знаешь потоки (таких в див2 мало) — сдаешь, нет — без шансов

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

Спасибо, отличный раунд, очень все понравилось )

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

i am from China i am sorry i can't use English well i only wrote A problem and C problem The B problem can make a right answer and check with read by computer i don‘t know how to do D AND E who can help me

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

    Problem D was difficult to understand even for those who know English. Can someone explain Problem D with an example.

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

      I think the question had it well explained. The reason for not putting a bit complicated example is that it would be too easy to guess the answer, rather than getting the information from the problem itself :)

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

        Yes, the description was quite clear. The main thing here to understand is the the minimum weight will always be 2. Now just try to think of a way to connect the nodes.

        Problem E is Standard Min Cost Max Flow problem.

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

Тест 11 к задаче А корректен??? 10 человек приходят в один момент и их обслужит одна касса? По-моему, нужно 10 касс =)

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

    Ответ как раз 10, а Ваша программа выводит 1.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Test: #11, время: 62 мс., память: 0 КБ, код возврата: 0, код возврата чекера: 0, вердикт: OK
    Ввод
    10
    1 30
    1 30
    1 30
    1 30
    1 30
    1 30
    1 30
    1 30
    1 30
    1 30
    Вывод
    10
    Ответ
    10
    Протокол тестирования
    ok 1 number(s): "10"
    

    С чего вы взяли что там одна?

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

    Спасибо, неправильно протокол понял.

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

Today is my unlucky day I save my solution for problem C in file B.cpp but I upload C.cpp to judge

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

I don't knw why I am getting "Idleness limit exceeded on test 8"....... for Problem B. Seems mysterious for me..... plz help...

http://www.codeforces.com/contest/237/submission/2434517

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

    Maybe its because the declaration co place[mo]; where mo is only 101. But it should be 100² + 1 because the number s can be at most 100²

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

      Oh thx..... now it is accepted...... I thought I would get RTE for these.... anyway good experience without any penalties...... thx again....

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

      There is no reason to vote negative at this comment, he has the good answer. place[i] is used for store the position on the array of the cell who has number i on it. So, 1<=i<=s, 1<=s<=n*max(ci), 1<=n<=50 and 1<=ci<=50.

      Edit: oups, too late: the comment has received new positives votes before I post my comment

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

        You are right cup_of_tea....... this definately help me in future contest.... Thx god it was not rated for me... gdisastery really deserves positive feedback... But I cannot vote twice... maybe I have to try from different ID..... :D

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

Omg, really fast judge!

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

Ожидается ли разбор? А то моё решение B, абсолютно наивное и лобовое (бегаем по строкам снизу вверх, каждый раз ищем максимум всего нерассмотренного, кладём в конец строки, укорачиваем строку) как ни странно, зашло, но я видел чьи-то решения, судя по количеству вложенных циклов, куда более быстрые; было бы полезно увидеть их в текстовой форме.

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

I am facing a strange problem in the practice session . My solution for problem C is returning -1 for the first test case when i submit my .cpp file but it returns the correct value ( 3 ) when running in my pc.

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

Контест классный!!!!!!!!!!!!!!

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

I'm looking to be on top10 contributors, could you help me ? =/

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

    Post funny comments with memes (or not) will not suffice for become top contributor. If you really want to progress, you should make interesting posts on your blog, or give interesting answers.

    Anyway, Good Luck!

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

Is it rated?

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

Testing is fast — very good.

Rating update is slow — not very good.

Just joking

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

Sucks that I kept getting WA on C because I put == as opposed to >=. On the bright side, you can do C in linear time as opposed to using a binary search.

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

Judging was too fast but rating dont provide yet...I thing something is going WA...:D

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

Here is a screencast of me solving this round: youtube To watch comfortably (and see clear text), choose 1080p and watch full-screen on a 1920x1080 resolution or higher. I will also provide a file in 1680x1050 for download later if you prefer.

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

Here are the cheaters! wangyedong CHFB_oXbT 389804652 jionghehe Their E Codes are the same!

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

waiting for editorial! thanks already

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

in problem E. Build String , we should write min cost flow algorithm , but what will be in the role of nodes ? From which node to which are we finding flow ?

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

    As I see it, you need n+26+2 nodes: a node for each given string, a node for each distinct letter in t and source and sink. The edges will be:

    a) source -> string i, with capacity ai and cost i (no more than ai characters can be erased from the i-th string and each operation costs i).

    b) string i -> letter c, with capacity [the number of times c occurs in the i-th string] and cost 0 (to erase at most as many letters as there are in the i-th string).

    c) letter c -> sink, with capacity [the number of times c occurs in t] and cost 0 (we shouldn't erase more c-s than there are in t overall).

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

      thanks , i found out now . Firstly i thought flow was going from each string to the main source. :)

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

Problem E is Standard Min Cost Max Flow problem. China's NOIP don't test it, I think i need not do it now; i also want to know what the problem 4 mear

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

We are waiting for the editorial.

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

In the problem C I am using binary search to find the minimum value of l.prime[i] stores the number of prime numbers upto i.I am using the following code to return true or false.

bool check(int l) { for(int x=a;x<=b-l+1;x++) { if(prime[x+l-1]-prime[x-1]>=k) return true; }

return false; } and I am getting the wrong answer. Please tell what is wrong in my approach.

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

    It should be this : bool check(int l) { for(int x=a;x<=b-l+1;x++) { if(prime[x+l-1]-prime[x-1]<k) return false; } return true; }

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

@problem setter : Editorial ??

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

Hi NALP,is there any editorial for this round?

UPD:Could anyone tell me how to solve prob D T-decomposition?

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

can anbody plzz tell me wats wrong with the following code..its giving wrong ans on pretext 10

include

using namespace std;

define MAX 11111

int a[MAX][2]; int main() { int t; cin>>t; for(int i=0;i<t;i++) cin>>a[i][0]>>a[i][1]; int cash=1; int maxcash=1; for(int i=0;i<(t-1);i++) { if(a[i+1][0]==a[i][0]) { if(a[i+1][1]==a[i][1]) cash++; else { if(maxcash<cash) maxcash=cash; cash=1; } } else { if(maxcash<cash) maxcash=cash; cash=1; } } if(maxcash<cash) maxcash=cash; cout<<maxcash<<endl; return 0; }

plz reply

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

    You are not getting Wrong Answer but Run Time Error. Increase the size of your array : change #define MAX 11111 to #define MAX 111111.

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

will we have an editorial for this round?I am not able to solve the young table problem,could someone give a hint?

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

    My approach:sorting

    for any young table,like

    a1 a2 a3 a4 a5 a6

    a7 a8 a9 a10

    a11 a12 a13 a14

    a15 a16

    the following satisified: a(i)>a(i+1)