Блог пользователя goo.gl_SsAhv

Автор goo.gl_SsAhv, 14 лет назад, По-русски

Открытое личное первенство Уральского Государственного Университета, г. Екатеринбург.

Начну рассказ задачей, в духе некоторых авторов:

Problem I

Input

2
E
C

Output

Case #1: О
Case #2: З

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

Для начала о задачах

A. "Книжная полка" - Геометрия, тернарный поиск.
B. "Взрыв в пирамиде" - Геометрия, расстояние от точки о плоскости.
C. "Торт" - Решение системы линейных уравнений, по сути геометрия, провести прямую пересекающую прямоугольник и максимизировать функцию F(x, y) в вершинах одной из половинок. Можно было сдать тернарным поиском, что избавляет от рассмотрения кучи граничных случаев, у меня их было 6, и потому сдал с +7.
D. "Полтора землекопа" - Не сложный ребус на / и %, к моему удивлению множество людей искали остаток от деления одного числа на другое с помощью перебора в цикле.
E. "Золотые слитки" - Ничего так задача, интересная, можно свести к простой геометрической задаче на бинпоиск. (не сдал)
F. "К вопросу о лысине 2" - Перебор с извратом
G. "Долгожители" - Посчитать число дней между двумя датами, кто писал на яве и шарпе сразу акцептили, а я набажил в 6 строчках 3 раза. (+4)
H. "Адская работа" 1000 решений сводящихся к циклу со всякими движениями
I. "Двоичный палиндром" - А ну-ка догадайся, что есть закономерность (не сдал)
J. "Поиски тайника Геометрия" - Даже не знаю как описать, можно комбинаторно подходить, можно хитро проэмулировать с использованием несложной геометрии, но решение не очень то простое как мне показалось (не сдал)

Итогом 5 задач на геометрию, одна на тернарный поиск (или 2, если C включить сюда),  бинарный поиск, перебор с извратом, закономерность, и ещё что-то. В общем-то есть некая не сбалансированность. Одну задачу в общем-то можно назвать задачей на графы - F про перебор. Но из графов там только граф на 50 вершин a[i][j] = i % j == 0 || j % i == 0

Задачи в общем-то не сложные, можно решить их все часа за 3 даже мне. Но я увяз в багах, в тупеже, и не поверил что задача у которой в инпуте число порядка 2^1000000 является задачей на формулу.
Контест вышел очень динамичным на мой взгляд, рассмешил Павел, не сделавший ни одного сабмита до заморозки, и сдавший в итоге 5. Алексей выбрал неверную тактику - он не сабмитил халяву до заморозки, в итоге  сдав все задачи проиграл 250 минут штрафу.



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

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Интересно получилось - на первенстве задачу F решили практически все, а на тимусе только 4 участника.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    В этой задаче были разные ограничения для тимуса и для очного первенства. В результате в первом варианте она оказалась самой сложной, во втором - одной из самых простых.
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Наша команда почти весь тимусовский контест недоумевала, как задачу F сдало так много людей на онсайте :) А разгадка оказалась такой простой...

      А можно узнать ограничения на онсайте?

14 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Некая несбалансированность, подмеченная автором поста, как всегда считала наша команда, характерна почти для любого "уральского" контеста.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
У нас на онсайте были ограничения n <= 30, так что любой перебор подходил на прекальк)
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
По I, сразу видно что есть закономерность, ибо с ограничениями 2^1000000 трудно придумать другое решение)))