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

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

6 апреля в Самарском государственном университете прошел III (XIV) открытый командный студенческий чемпионат Поволжья по спортивному программированию. Теперь мы приглашаем всех желающих, кто не был на чемпионате, принять участие в соответствующей тренировке 28 апреля с 11:00 до 16:00 по московскому времени . Мы полагаем, что участники любого уровня смогут найти интересные для себя задачи, однако наибольший интерес тренировка будет представлять для участников фиолетового и оранжевого уровня (сложность ****).

Тренировка пройдет по правилам ACM, задачи будут на русском и на английском языках. Для ввода и вывода используйте файлы input.txt и output.txt.

Также просим не использовать интернет, prewritten код и иные материалы — участникам чемпионата это было недоступно.

Контест готовили: Дмитрий Матов (Nerevar), Константин Дроздов (I_love_natalia), Андрей Гайдель (Shlakoblock), Елена Рогачева (elena), Сергей Штейнер (steiner), Дмитрий Новиков, Александр Ефимов и Геннадий Натанович Гутман.

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

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

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

    Ванга снова ошиблась — вместо кларов были некорректные тесты и слабые тесты :D

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

Will the problem be in English or Russian?

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

I wonder why there is 2 extra minutes

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

    At the contest (in Samara) technical hitch occured, and the jury decided to add 2 minutes.

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

This 2 minutes can be useful to the Samara's contestents.

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

Knowing where to start reading the problem is a good skill used today :)

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

    I totally agree with you. Stories don't make much sense but the problems are good. I really enjoyed the contest :)

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

Задача D. Валидаторы? Не, не слышали. Лучше мусор в конец файла дописать.

Задача F. Подумать над хорошими тестами? Это для нубов. Участники pva701 и mexmans, ваши решения этой задачи неверные, в дорешке они будут получать WA.

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

pva701 and mexmans, your solutions of F are incorrect. Both of them fail on this test:

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

    I still don't clearly understand the task in F. Do we start with the letter z or a random letter of the latin alphabet. At each step are we allowed to replace only the letter 'z' or any letter in the text?

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

А в J должно было заходить?

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

    Похоже, что нет. Быстрейшее из авторских за n*log(n) работает полсекунды.

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

Как решалась K?

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

    Нужно было закодить то, что написано в условии. То есть проверить каждую область. Если она на всех цифрах включена, то 1, если на всех выключена, то -1. Объяснение такое: не существует такой области, которая бы была всегда включена либо всегда выключена (КЭП какбы). Если порисовать эти циферки на бумажке, то будет видно уж точно

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

      спс

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

        А как I решается?

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

          Генеришь всевозможные маски, выбираешь те, которые подходят по условию. Затем идёшь по изначальной строки и смотришь префикс. Если найдётся префикс, который отличается с позициии I, то к ответу прибавляешь 1

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

как решалась задача G ?

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

    Отсортировать массив и проверить пары соседних элементов.

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

      А что-нибудь типа разбора есть (с более менее строгими объяснениями)?

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

      как можно доказать это ?

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

        Возьмем три числа a,b,c (a < b < c). Докажем, что min(a xor b, b xor c) < (a xor c).

        Рассмотрим первый бит, где эти числа различаются.
        1. В a этот бит равен нулю, в b и c — единице. Тогда (b xor c) < min(a xor b, a xor c).
        2. В a и b этот бит равен нулю, в c — единице. Тогда (a xor b) < min(a xor c, b xor c).

        Ну и отсюда следует, что надо рассматривать только соседние элементы.

        Мы на контесте ничего не доказывали, просто было интуитивно это понятно.

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

          спасибо :) я не смог доказать по этому не написал :(

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

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

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

Как C решать?

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

    Насколько я помню, бинпоиск по ответу, а потом динамика d[i][j] — минимальное количество цветов, которое надо посетить, чтобы добраться до клетки (i,j).

    UPD. Похоже, я все-таки не помню задачу (писал ее Hohol) Только помню, что были бинпоиск и динамика. Пусть кто-нибудь еще расскажет)

    UPD 2. Решение тут: http://codeforces.me/blog/entry/7493#comment-131742

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

      Вы про ту же задачу, что и я? Там вроде цветов не было... Если да, то расскажите, пожалуйста, подробнее

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

        Я буковки в матрице называю цветами.

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

      Блин!
      Тесты в C тоже слабые.
      Прошло решение работающее за сумму квадратов сторон всех прямоугольников на каждом шаге дихотомии. Валится очевидным тестом вида:

      .aaaaaaaa.
      .bbbbbbbb.
      .aaaaaaaa.
      .bbbbbbbb.
      .aaaaaaaa.
      .bbbbbbbb.
      .aaaaaaaa.
      .bbbbbbbb.

      Только 1000 на 1000.
      Я даже заслал решение, которое генерит этот тест внутри себя, а не считывает из файла, и получил законный TL.

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

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

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

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

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

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

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

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

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

        Я придумал решение, придумал этот тест. Потом решил проверить, работоспособность того, что я написал, и был удивлен когда вместо ТЛ получил АС :)

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

        На нашем сервере этот сабмит получает WA-1, а не TL-1.

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

      d[i][j] — минимальное количество клеток из того же прямоугольника, что и (i, j) на конце пути (1, 1) — (i, j)

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

    Бинпоиск по ответу.

    Внутри бинпоиска нужно проверять, существует ли путь, ни для какой области не посещающий более k ее клеток. Заведем такую динамику: dp[i][j] — наименьшее возможное число посещенных клеток, принадлежащих той же области, что и клетка (i,j). При этом, если получилось, что для клетки значение динамики равно k, значит из нее уже нельзя делать переход на клетку той же области.

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

Can anyone explain the sample of Problem B?

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

    I think the answer of the sample is 19 as the problem describes

    • »
      »
      »
      12 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится
      At the beginning:      00000 00000 00000
      After query 1 (1 6):   11111 10000 00000 (+6)
      After query 2 (4 8):   11122 22200 00000 (+5)
      After query 3 (2 7):   13322 22200 00000 (+2)
      After query 4 (10 12): 13322 22204 44000 (+3)
      After query 5 (7 13):  13322 25554 44500 (+4)
      6+5+2+3+4 = 20
      
»
12 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

No offense. The statement in english is quite confuse.

  1. In problem D, all the number should be 'non-negative' not 'positive'. And in input description, M should be the number of 'portions' not 'days'.

  2. In problem J, the range of U,

    Unable to parse markup [type=CF_TEX]

    is wrong.

Especially for D, the confusion and rejudgement drove me crazy for quite a long time.

Anyway, preparing contest is a huge and tough job, we can never ask for a perfect contest. Thanks for this contest. These two gyms really delighted my weekend. :)

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

Как решать B?

How to solve B?