Первая индивидуальная олимпиада 2012/2013

11 лет назад, # ^ |

Думаю, что нет. Они обычно появляются на контестах перед Всероссом, а в преддверии регионального этапа их нету.

→ Ответить

11 лет назад, # |

← Rev. 2 →

У кого-то фидбэк пашет? У меня просто пишет "Unknown, Scored".

→ Ответить

Lelby

11 лет назад, # |

Монитора и не предполагается?

→ Ответить

11 лет назад, # ^ |

Нет.

→ Ответить

11 лет назад, # |

в первой задаче "любое" == каждое или хотя бы один?

→ Ответить

11 лет назад, # ^ |

Думаю, что каждое.

→ Ответить

11 лет назад, # ^ |

-9

это уныло, так писать условия =/

→ Ответить

_dangerous_

11 лет назад, # ^ |

да вроде понятно...

→ Ответить

11 лет назад, # ^ |

слово "любое" можно понять двусмысленно.

→ Ответить

_dangerous_

11 лет назад, # ^ |

ну да, лучше было написать "каждое"

→ Ответить

11 лет назад, # ^ |

-11

да, голубчик, намного лучше.

→ Ответить

BLIZZARD

11 лет назад, # ^ |

Слово "любое" абсолютно понятно, не нужно придумывать ему второй смысл.

→ Ответить

Hohol

11 лет назад, # ^ |

К сожалению, слово "любой" несет в русском языке одновременно два противоположных смысла. Например, в словаре Lingvo:

Любой
...
II. Какой угодно (на выбор).
III. Каждый из себе подобных; всякий.

→ Ответить

11 лет назад, # ^ |

Для меня, конечно, русский не родной, но думаю, что "любой"=="каждый".

→ Ответить

pavelfomin

11 лет назад, # ^ |

+15

Контрпример: "если оптимальных ответов несколько, выведите любой".

→ Ответить

11 лет назад, # ^ |

Контекст разный.

→ Ответить

Odeen

11 лет назад, # ^ |

-6

У меня времени на прочтение задачи, ушло больше чем на решение;)

→ Ответить

Vlad_Zhukov

11 лет назад, # ^ |

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

→ Ответить

11 лет назад, # |

Интересно получилось у меня: два жадника и два двоичных подъема:) Хотя на третью есть решение за N+М, я писал тупое N log N+M log M.

Больше всего за первую боюсь:) Там же выгодно либо за 1 штуку платить, либо только за 2 максимальных, да?

→ Ответить

Perlik

11 лет назад, # ^ |

Вроде да. Я боюсь за heavy-light в D :)

→ Ответить

11 лет назад, # ^ |

Я делал фенвиком. Типа как на емаксе написано про покраску ребер. Хэви-лайт — для такого количества вершин и запросов слегка сурово, хотя может они поэтому такой ТЛ/МЛ и поставили.

→ Ответить

Odeen

11 лет назад, # ^ |

Да.

→ Ответить

pva701

11 лет назад, # ^ |

← Rev. 2 →

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

→ Ответить

11 лет назад, # |

Ололо, я правильно понимаю, что засчитывалось последнее решение, даже если ты вручную выбрал засчитывать другое? :D

→ Ответить

11 лет назад, # |

Вторая задача....втф?!

→ Ответить

Logvinov_Leon

11 лет назад, # |

А где можно увидеть результаты?

→ Ответить

11 лет назад, # ^ |

тут

→ Ответить

warrior_c

11 лет назад, # |

-6

Тот неловкий момент, когда ты забываешь поставить used и твое решение вместо 100 получает 2..

→ Ответить

11 лет назад, # ^ |

Я писал хешсет на вторую руками. Для пары (x,y) брал хеш-функцию, как их произведение. Почему-то долго работает... Поменял, и прошло :(

В общем, я тебя понимаю.

→ Ответить

11 лет назад, # ^ |

← Rev. 2 →

Хеш-фунция равная произведению числителя на знаменатель падала по ТЛ? А можешь код показать? У нее же коллизий быть в принципе не может (если дробь несократимая, а знаменатель — степень двойки)...

→ Ответить

Perlik

11 лет назад, # ^ |

У меня шех-функция (x*13+y), т.к я испугался, что произведение за long long выйдет. Тоже упало. Наверное, потому что куб :D

→ Ответить

11 лет назад, # ^ |

Ну куб заходить и не должен, авторское решение N^2 logN — оно хранит точки в TreeSet'e, и не беспокоится по поводу коллизий :)

→ Ответить

Perlik

11 лет назад, # ^ |

я хотел быстрый куб сделать :)

→ Ответить

11 лет назад, # ^ |

Вот...

Код корявый, но найти должен :)

→ Ответить

11 лет назад, # ^ |

← Rev. 2 →

А... Ну так ты умножаешь на степень двойки (которая в знаменателе), а потом берешь по модулю 2 в степени 22. Понятно, что коллизий будет много. Если бы модуль был бы простым, то работало значительно быстрее.

→ Ответить

11 лет назад, # ^ |

Спасибо, что помог разобраться. Я всегда беру по такому модулю, чтобы не использовать остаток... Соптимизировал, называется..:)

→ Ответить

11 лет назад, # ^ |

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

→ Ответить

11 лет назад, # ^ |

Там даже если поставить h=(x+1)*(y+1), то проходит. Получается, что нулей много... Хз откуда они берутся.

→ Ответить

GameR

11 лет назад, # ^ |

у меня тоже такая ситуация

→ Ответить

y.kemaev

11 лет назад, # |

← Rev. 2 →

Ребята, какая главная идея в решении А ?

UPD Извиняюсь, перечитал условие и понял, что все было раз в 500 проще...

→ Ответить

11 лет назад, # ^ |

Очевидно, что число равное максимуму по первому параметру мы заплатим, ведь никуда мы от него не денемся. Это же утверждение верно и для второго параметра. Зато после этого по каждому параметру уже платить не придется. Если максимум и там, и там лежит в одном задании, то его делаем первым, за остальное не платим. Иначе смотрим как нам выгодно — макс по первому, а потом по второму, или наоборот.

→ Ответить

Mediocrity

11 лет назад, # |

У кого есть права, залейте пожалуйста в тренировки.

→ Ответить

warrior_c

11 лет назад, # |

Вопрос по задаче С. Правильное ли такое решение за n+m: читаем все запросы. Для каждой вершины сделаем список запросов, на которые нужно ответить, чтобы эта вершина была r(то есть в нее нужно попасть). Подвесим дерево за первую вершину. Для запросов, где l не является предком r ответ очевиден: первый предок l. Теперь для запросов, где l выше r: запустим дфс, для каждой вершины в массиве cur будем хранить вершину, в которую мы пошли из нее при обходе. Теперь если мы находимся в какой-то вершине, пройдемся по всем запросам для этой вершины и ответом на очередной запрос будет cur[l]. То есть идея такая, что мы запоминаем в какое поддерево идем и оно и будет ответом. Вроде понятно объяснил но правильно ли(:

→ Ответить

11 лет назад, # ^ |

Да, конечно правильно. напоминает алгоритм Тарьяна. Я минут 10 думал над красивым решением, но потом сел двоичный подъем писать. Пока писал, в голову это пришло, но решил не изобретать велосипед.

→ Ответить

Edvard

11 лет назад, # |

Соревнование добавлено в тренировки. Удачи в дорешивании!

→ Ответить

11 лет назад, # ^ |

Спасибо!

На вторую 6 секунд поставил, чтобы у меня хотя бы тут прошло?:)

→ Ответить

Edvard

11 лет назад, # ^ |

Там авторские решение достаточно медленные

→ Ответить