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

Автор IlyaCk, история, 9 лет назад, По-русски

Месюра разослал, пока что полуофициально ввиду незавершённости оформления в министерстве, черновик приказа на новый сезон.

Как всегда, разорван между учебными годами (**І этап Сб 16.04.2016**, регистрация должна открыться завтра в Пт 18.03.2016).

На ІІ этап планируется дальнейшее дробление регионов:

Київська, Сумська, Чернігівська, Житомирська --- Північний
Донецька, Луганська, Харківська --- Східний
Дніпропетровська, Кіровоградська, Полтавська, Черкаська	--- Центральний
Запорізька, АР Крим, Миколаївська, Одеська, Херсонська --- Південний
Вінницька, Хмельницька, Тернопільська, Чернівецька --- Південно-західний
Волинська, Закарпатська, Івано-Франківська, Львівська, Рівненська --- Західний

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

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

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

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

Можете дать ссылку, где можно будет узнать резы / посмотреть за прошлые года?

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

У кого-то есть размороженные результаты?
Результаты

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

А где можно посмотреть условия?

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

    на еджаджах нигде нет, разве что, кто-нибудь печатные вынес

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

      и у вас не было условий? я думала только у нас проблема с загрузкой условий(сервер Южного региона), билась весь вечер перед основным туром, так и не подгрузила условия(((

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

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

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

        на сервере Западного региона тоже не было.

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

        я так понимаю, вы относитесь к числу организаторов.. можно тогда пользуясь случаем узнать 1) чем отличается time limit и real time limit? 2) будет ли дорешка?

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

          не считаю себя организатором, просто админила контест для Юга, точней два: в конкурсе, и внеконкурса; мне очень помогал MrDindows, его клары были очень полезными при проведении тура. Клары касались тестов, условий задач. И наводили на мысли, что у контеста есть проблемы.Также благодарю 977kai, который саппотил "женский" сервер Южного региона. 1) чем отличаются, time limit — это процессорное время, real time limit — это астрономическое время, гдето так, обычно задается процессорное время, real_time имеет смысл устанавливать примерно раза в два больше, чем процессорное время. Что нашла в инете. 2) дорешка, может будет вскоре, если разрешат тур внеконкурса открыть для дорешивания.

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

            процитирую ejudge wiki про real_time_limit:

            "Данная конфигурационная переменная задаёт ограничение на астрономическое время выполнения тестируемой программы на одном тесте. Ограничение астрономического времени выполнения программы должно быть больше ограничения виртуального процессорного времени (см. переменную time_limit). Оно должно учитывать время выполнения операций ввода-вывода и загруженность тестирующей машины."

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

          открыта дорешка:)см. тут логин, пароль по запросу( условия задач есть, нет условий только трех задач C, F, I, но до конца недели появятся)

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

      Вася, условия были. По крайне мере к концу контеста загружались в "statements".

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

    Очень надеюсь, что по этому проблемсету нет опенкапа и это не закрытая информация.

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

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

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

Если кому-то интересно — видео разбор большинства задач от меня находится тут (огромное спасибо заснявшему это все участнику).

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

    O(NMlogM) в задаче М? Круто) В южном регионе О(NM) у некоторых команд так и не прошло =)

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

      У меня есть подозрения, что мощность серверов отличалась по регионах.

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

Я прошу прощения за оффтоп, но меня всегда интересовал вопрос — почему на Украине сезон начинается еще до лета? Это же не очень удобно, какой-то большой разрыв в более чем три месяца. За это время с командой может что угодно произойти.

Если где-то уже обсуждалось, можно дать ссылку, я мог пропустить.

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

    Думаю, логика организаторов примерно такая. SEERC — это аж третий этап для украинских участников (есть 1/8-ая, которая вчера проходила, и 1/4-ая, проходящая в середине сентября). Сам SEERC проходит в середине октября. Летом все на каникулах, а за полтора месяца три этапа провести тяжеловато. Что мешает перенести первый этап на май — для меня загадка.

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

      а зачем вообще у нас 1/8 проводят? везде ж с 1/4 начинается?

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

        Вероятно, чтобы привлечь больше команд.

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

          И не дать шанс первокурсникам участвовать.

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

            Я не знаю как, но некоторые первокурсники таки участвуют

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

              Некоторые команды делают замену, вроде бы одну можно делать.

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

              я в каких-то правилах видел, что могут участвовать старшеклассники. Наверно они просто в 11 классе пишут 1/8 и уже на первом курсе 1/4.

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

                Ученики вроде как поза конкурсом участвуют.

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

    Когда я спрашивал об этом, то услышал довольно забавное объяснение. Если я правильно понял, то политика примерно такая:

    1) Чем раньше начать сезон, тем раньше команды начнут тренироваться, и тем лучше они подготовятся и прокачаются; условно говоря, если начинать сезон в сентябре, а заканчивать в октябре-ноябре, то остальные 9 месяцев никто не будет тренироваться :)

    2) 1/8 весной дает возможность узнать топовые команды в каждом универе (информация будет более актуальной, чем если взять результаты за прошлую осень), что упрощает выбор того, в кого вкладывать деньги в промежутке между 1/8 и осенью (кого отправлять на какие-нибудь тренировочные сборы, на KPI-Open и т.д.).

    Было бы круто, если бы кто-то из более официальных лиц прокомментировал — я не знаю, насколько правильно я все понял, и насколько публичны детали, которые мне сообщали тренеры/орги при личном общении.

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

      Насколько мне известно, чем больше команд на 1 этапе, при правильной/корректной регистрации на сайте бейлора, тем есть шанс увеличения квоты на финал мира для украинских команд, второе, что могу, сказать, это влияет на шанс того, что в скором времени Украина может принять финал мира ;) Популяризация движения АСМ в Украине, такой себе пиар Украины и правильный ход. По новым правилам 2016 года, команда может начать сезон и с 1/4 ;)

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

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

        При полуфинале в октябре получаются истории вроде — команды в Винницу приехали, на улице уже холодно, в общагах отопление еще не включили.

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

        "По новым правилам 2016 года, команда может начать сезон и с 1/4" то есть нет ограничения в 5 команд от университета?

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

Как узнавать, пересекает ли отрезок не выпуклый многоугольник без самопересечений? Если отрезок лежит на многоугольнике, то считать, что он не пересекает. (Задача К)

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

    Возможно, я чего-то не учитываю, но почему бы не так: 1) Если отрезок не имеет общих точек ни с одной из сторон многоугольника, то не пересекает. 2) Если отрезок целиком лежит на некоторой стороне многоугольника, то также не пересекает. 3) Если отрезок пересекается хотя бы с одной стороной (то есть имеет с ней ровно одну общую точку, отличную от вершины многоугольника), то, очевидно, пересекает. 4) Таким образом, отрезок содержит некоторые вершины многоугольника. Рассматриваем все вершины, соседние с данными — если все они находятся по одну сторону от прямой, содержащей отрезок (некоторые из них могут лежать на этой прямой), то не пересекает, иначе пересекает.

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


      A = (1, 1)
      B = (3, 3)
      Если правильно понял, что имеется ввиду под соседними точками.

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

        Да, но это ведь случай 4.1 — вершины (1,1) и (3,3) лежат на отрезке. Рассматриваем соседние вершины (то есть соединенные ребром хотя бы с одной из них) — это точки (1,0), (3,0) и (4.2). Все они лежат по одну сторону (справа снизу) от прямой, соединяющей точки (1,1) и (3,3), значит, не пересекает... P.S. Да, по идее, вершины, совпадающие с концами отрезка, не должны влиять на ответ — тогда, если исключить концы отрезка, то это вообще случай 1.

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

          Если исключить концы отрезка тогда на этом тесте не будет работать:

          A(-1, -1)
          B(1, 1)
          1 скажет что не пересекает

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

            Так он же действительно не пересекает, он внутри полностью... Но я уже придумал другой тест, где такое не будет работать.

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

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

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

      Еще необходимо распознавать случай, когда отрезок лежит полностью внутри многоугольника

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

        Ну если уметь определять, пересекает ли отрезок многоугольник или нет, это должно быть легко: - если пересекает, то очевидно нет; - если отрезок полностью содержится в некоторой стороне многоугольника, то также не лежит; - иначе находим точку на отрезке, которая не принадлежит границе многоугольника, и проводим из нее луч в случайном направлении (так, чтобы луч не содержал ни одной вершины многоугольника). Если пересечений четное число, то отрезок снаружи, иначе внутри. P.S. Кстати, а почему бы так не решать исходную задачу? Наш отрезок разбивается вершинами многоугольника на подотрезки, и для каждого подотрезка таким образом можно проверить, лежит он внутри или снаружи. Подотрезки, полностью содержащиеся в сторонах многоугольника, можно игнорировать.

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

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

          Это будет работать за O(N4) в худшем случае

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

            Так ведь вершин всего 100? Или там такой суровый TL? Если такое не проходит, можно делать то же самое с помощью сканирующей прямой — тогда это должно быть N^3 * log(N). В этом случае для каждого подотрезка мы можем определить, пересекает ли он многоугольник, бинпоиском по уже отсортированным кускам ребер.

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

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

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

Когда можно ожидать возможность порешать контест виртуально где-нибудь на opentrains или в тренировках СF?

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

Кто знает расписание или мейл организаторов на 1/4 асм(запад)? Я написал Ярошку еще 3 сентября и никаких ответов не получил до сегодня.

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

    Попередня програма олімпіади

    16 вересня з 9:00 Реєстрація учасників, поселення.

    14:00 Урочисте відкриття Олімпіади.

    16:00–18:00 Ознайомлення із системою проведення Олімпіади, пробний тур.

    17 вересня 9:30–15:00 Командний тур, визначення переможців.

    18 вересня Підведення підсумків Олімпіади, нагородження переможців. Екскурсії.

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

У кого то есть ссылки на борды регионов/общий борд?

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

Какая-то муть: Месюра пишет, что icpc.baylor.edu не_продвигает команды в собственно SEERC автоматически, и тем, кто туда (на SEERC, он же первая (высшая) группа финала Украины) прошёл, надо регистрироваться (точнее говоря, собирать команду из существующих людей) заново. Причём, срочно (до завтра Ср 21.09.2016).

Кого касается -- перепроверяйте почту (именно ту, которая указана на бейлоре) и/или уточняйте у Месюры.

Кто-то ещё слышал о проблемах с продвижением команд? Это только у нас, или глобально по всему сайту для всего мира?

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

Он-лайн результаты полуфинала http://test-essuir.sumdu.edu.ua/