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

Автор dalex, 8 месяцев назад, По-русски,

Привет.

Некоторое время назад в Самарском университете состоялась ежегодная олимпиада по программированию, и мы снова выкладываем ее в тренировки Codeforces. Тренировка пройдет в субботу, 8 апреля, в 9:30 MSK. Сайт clist.by говорит, что пересечений с чем-то важным в это время нет.

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

Ну и как обычно,

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

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

Carry on!

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

А разбор задач будет?

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

    Разбор будет, когда контест напишет 300 участников. Грустно видеть, что все его проигнорили. (UPD: done)

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

      Я опоздал на час к началу, но всё равно решил поучаствовать, не смотря на то, что еще нужно было квалификацию Google Code Jam пройти (может с этим связано?). Понравились задачи, спасибо)

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

    Если нужно разобрать задачи — скажите, какие именно.

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

      Был бы благодарен за разбор первой

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

          Спасибо)

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

          Можешь помочь найти изъян в этом алгоритме?

          В каждой строке (если есть) уберем правильные скобочные последовательности. После этого останутся только последовательности такого вида

          (((...( 
          )))...) 
          )))...)(...(((
          

          и пустые (можно доказать, что останутся последовательности только такого вида). Потом просто записываем сначала все пустые, потом все первого типа, потом все третьего типа, потом второго. Что в этом алгоритме не так? Я получаю WA16

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

            В третьем блоке важен порядок "("+")(("+"))("+")" правильная последовательность, а "("+"))("+")(("+")" — неправильная

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

                Так наверху под спойлером же есть решение. Моё почти такое же.

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

                  Количество закрывающих в начале и минимальный баланс — это разные вещи, по чему из них ты сортируешь? Правильно по минимальному балансу.

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

                  Речь не идет об исходных строках. Я же отвечал на комментарий levonog, который из строк предлагал убрать все правильные скобочные последовательности. В этом случае минимальный баланс = количество закрывающих скобок.

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

            Решение правильное, только достаточно важно в каком порядке добавляешь последовательности третьего типа. В любом не пойдет.

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

              А как пойдет? Какая-то сортировка нужна?

              Я отсортировал лексикографически и получил WA44.

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

      Если не лень — разбирай все. Только под спойлерами и лучше на английском

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

      Интересует A F I L. Еще, примерно час после окончания, интересовала D, но потом я понял, что моё случайно написанное криворукое решение находит GCD — именно то, что и нужно было искать в задаче.

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

      Например, очень хотелось бы знать почему на 29 тесте задача B валится)

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

        Нет никакой пользы от того, что тесты смотришь. На настоящем контесте не посмотришь. Лучше научиться придумывать тесты самостоятельно.

        Так что не смотри. Кстати, после 29-ого еще, скорее всего, 64-ый предстоит пройти.

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

а будет ли межвузовская Самарская?

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

    Что значит будет? Давно прошла уже. Зайди на страничку Тренировки (http://codeforces.com/gyms), там она есть.

    Если ты про чемпионат Поволжья, то я не при делах, но я бы поставил, что ждать его придется долго.

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

      именно про него(

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

        Как понимаю, Вас интересует дорешать задачи. Их можно сдавать на нашем сервере, просто условий там пока нет.

        Когда выложим в тренировки — не знаю; скорее уже летом (во-первых, сейчас почти каждую неделю какие-то соревнования, во-вторых, может, все же переведем на английский)

        PS Вопросы по чемпионату Поволжья лучше все же здесь задавать (или мне в ЛС)

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

Как решать J и L ? dalex pitfall

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

Finally, I have some time to write an editorial.

A
B
C
D
E
F
G
H
I
J
K
L
M