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

Автор try_kuhn, история, 4 года назад, По-русски

Привет, Codeforces!

В среду, 10 июня 2020 г. в 17:35 (UTC + 3) состоится End of the learning — Beginning of the tour contest (Div 3).

Это мой первый раунд (мэшап, так как даже для тренировок рейтинга нет, потому что надо прекращать писать контесты с телефона) с полностью моими задачами. Соревнование будет проводиться по правилам ICPC. По стандарту, штраф за каждую неверную посылку до посылки, являющейся полным решением, равен 20 минутам. За 20 минут до конца контеста таблица будет заморожена.

Вам будет предложено 6 задач на 2 часа. Я надеюсь, что они покажутся интересными для вас. Особые надежды возлагаю на задачу E. Как по мне — это самая интересная из них.

Задачи вместе со мной тестировали Ahmad Ahmadsm2005 Said, Ahmed ahmedfouadnew Fouad, Матвей Irpacci Кулинич и Максим Xennon Карпук. Также большое спасибо Михаилу MikeMirzayanov Мирзаянову за системы Polygon и Codeforces!

Удачи в раунде! Успешных решений!

И чуть не забыл, вот ссылка:

https://codeforces.com/contestInvitation/4036ec99932a47484351d57a812de34c7a4fbb2c

А вот и разбор

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

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

Good luck!

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

А $$$5 \times 3$$$ можно? А если я сделаю список массивов размера 5, размеры массивов соответственно 5, 4, 3, 2, 1? А если я сделаю трехмерный массив размера $$$3 \times 3 \times 3$$$? А одномерный размера $$$10^6$$$ можно? А если я сделал таблицу $$$4 \times 4$$$, содержащую в себе long long, но из-за особенностей хранения типа могу использовать ее как таблицу $$$4 \times 8$$$, содержащую int или $$$4 \times 32$$$, содержащую char? Можно поподробнее, чего нельзя делать, а то у меня еще парочка идей есть.

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

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

    Я тут немного подумал, разобрался. Там скорее всего я сделаю ans % (1e9+7)

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

    Из-за первого вопроса, я подумал, что контест уже прошел и я профукал его. Не пугай так больше!

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

Is the time UTC+9?

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

Чтобы писать красиво $$$10^5$$$ достаточно написать такое выражение между долларами: $$$10^5$$$ (я не знаю, почему доллар заменяется на три доллара, администрация сайта меня по этому вопросу игнорирует)

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

    Ок, буду иметь ввиду на следующих контестах. Спасибо большое!

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

Isn't the penalty set to 20 minutes (in the contest)?

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

Первый контест от l-_-l был лучше

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

    Кому как. Я же ещё во время составления и экзамены писал

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

How to solve F?

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

Кто пишет на С++ и получил по задаче А вердикт "Неправильный ответ на тесте 15" — попробуйте отослать без функции trunc().

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

    Или (int)trunk(a/b), потому что нужно вывести целое число, а trunk() возвращает double

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

    А кто пишет на питоне — пишите на плюсах, а то взятие по модулю работает не так) Вообще такая задачка хорошо проверяет навыки проблемсеттинга)

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

      Спасибо большое! Только я не пойму: это хорошо или плохо?

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

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

        Хорошо, что есть про использование trunc() — это определяет округление отрицательных чисел, которое тоже не очень очевидно само по себе.

        Меня еще поначалу смутило, что числа до $$$10^{18}$$$, а запрашивается их произведение. Решил написать на питоне, чтобы не заморачиваться в int128, ну и столкнулся с этой проблемой) А потом вообще оказалось, что тесты слабые и такого не происходит)

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

          Я кстати тоже удивился насчёт тестов. Я похоже при тестировании задачи в генераторе поставил 1е9, а потом забыл вернуть)

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

            Но генератор на testlib — классная штука!

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

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

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

    Да. Я сейчас немного занят, поэтому позже я его опубликую

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

try_kuhn, is it okay if I post a brief editorial here for everyone (since submissions are public now)?

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

Slight editorial (with author permission):

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

    Hello! How you did these opening triangles?

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

    You can public it in your blog, I will add link

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

    I will do editorial on russian lenguage then

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

    For F when you turn right you go to another tunnel.So for p1 shoudn't it be 100-a1 for ending in that tunnel and then advancing for 2nd tunnel you should have a1 chance for that ? Or I have misunderstood the question

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

      The statement's not the clearest, but I interpreted "turn right" from On every turn person can turn right with probability a [i] as "end at that tunnel with probability $$$a_i$$$" and "go straight" as "continue to the next tunnel"

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

    Why did you took the path from (1,1) to (i,j) ?I mean what's the reason or intuition behind this.Thanks in advance

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

      Unfortunately, there isn't much intuition. The best I can say is "I've seen this problem before, so I recognized it quickly."

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

Thanks for the contest! Looking for more contest like this one.

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

I think you meant editorial here too instead of parse.

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

Some suggestions:

  1. Try to use MathJax format. For example, something like 1<=n<=1e5 should be $$$1 \le n \le 10^5$$$(use single dollar sign, but not 3 dollar signs) which will be displayed as $$$1 \le n \le 10^5$$$

  2. Try to spell key words correctly. ( guaranteed but not garanted)

Hope you can make better contests next time :D