Напоминаю, что завтра (27.10.2012) на acm.timus.ru пройдет этот контест в 11.00 мск. Предлагаю здесь обсудить контест после его окончания.
Хотелось бы узнать, задачи будут впервые, или они уже были в каких-то контестах (типа опенкапа)?
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3821 |
3 | Benq | 3736 |
4 | Radewoosh | 3631 |
5 | jqdai0815 | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | ksun48 | 3388 |
10 | gamegame | 3386 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 161 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
Напоминаю, что завтра (27.10.2012) на acm.timus.ru пройдет этот контест в 11.00 мск. Предлагаю здесь обсудить контест после его окончания.
Хотелось бы узнать, задачи будут впервые, или они уже были в каких-то контестах (типа опенкапа)?
Название |
---|
впервые конечно, это же, как я понимаю, отбор на ВКОШП для уральских школьников
я так и понял, ну мало ли
Я и не знал. Вставили бы в название слово "школьная".
Контест уже завершился, так что можно обсуждать задачи. Как решалась G?
Храним остаток от деления данного числа на каждое простое не большее 47, восстановление ответа по КТО.
Можно поподробнее про КТО?
Вам в помощь статья на е-максе и Кормен (страница 979).
Я эту КТО не знаю. Хотя прочитав задачу, открыл статью на википедии, хотя мне это никак не помогло. Там для каждого простого множителя можно линейное модулярное уравнение решить и тогда тоже получается. А как делать через китайцев?
Пусть мы знаем, что искомое число дает остаток mi от деления на простое число pi. Тогда найти число можно так:
Вау. У тебя ведь выходит то же самое, что и у меня. Надо найти такой коэффициент при произведении всех предыдущих простых (чтобы для них остаток не изменился), что и на данное число будет нужный остаток.
Эта теорема говорит, что такое у нас всегда получится?:)
Эта теорема говорит, что всё однозначно по модулю произведения pi(в общем случае, по модулю их НОК).
спасибо, круто:)
Нужно было китайцам пересчитать свою армию. А народу куча. Тогда они и решили: выстроить всех в шеренгу по два, по три, по пять и т. д. И каждый раз посчитать остаток. Так и сосчитали.
Можно совсем просто: поддерживаем остаток от деления на произведение всех простых до 47. Оно влезает в 64 бита. Теперь, если мы хотим узнать ответ по другому модулю, который, очевидно, будет являться делителем нашего, просто выведем наш остаток от деления на произведение, взятый по новому модулю.
Читаю и думаю: "Какой же я идиот, писал восстановление по КТО при наличии такого простого и при этом очевидного(!) решения".
P.S. Поздравляю с выигранным контестом.
Есть ссылка на результаты официальных участников?
http://acm.timus.ru/monitor.aspx?id=125
А что в H на 23 тесте? Это там где две полоски пересечь надо.
Насчет непосредственно 23 теста не знаю, но если Вы скинете код — может быть, я пойму, где у Вас баг.
просто ранодомный тест, даже без параллельных отрезков...
А до этого были рандомные? Ведь до 23 дошло как-то...
Попробуйте устранить дробную арифметику из своего решения там, где это возможно. Мне кажется, все проблемы из-за нее.
P.S. Я в своем решении использовал дробную арифметику только при подсчете ответа, и то я его считал без пересечений прямых (ниже я про это уже писал).
J решалась комбинаторикой?
Тупо перебираем все тройки, в которые входит Холден, получается чистый квадрат.
Можно и за константу: разобрать случаи, когда m == n/3, m — n/3 == 1 и m — n/3 > 1. Для каждого случая смотрим: teddyhater ли Холден; плюс случай, когда m < n/3. Получаем 7 вариантов ответа, которые довольно легко считаются. Код: http://pastebin.com/N16dDbMr
Понятно, что можно. Вот только зачем?)
Мне почему-то в голову пришло это решение :) Разобрать случаи тоже несложно, в общем-то, так что оно имеет право на жизнь.
Осмелюсь возразить. Посмотри на монитор: сколько времени у тебя заняло решение за константу и сколько у меня — за квадрат. Плюс с какой попытки ты это решение запихал. В контесте из 12 халяв это решает.
Я решал контест слегка не серьезно, насчет времени — там имелись отвлекающие факторы. Попытки это да, я последний случай криво разобрал и получил Wa12, например. В целом, не буду спорить, что решение перебором придумать и написать проще.
Урал, ты ли это? такой халявный контест, чем это вызвано?
Это был школьный контест.
Обычно на УРКОПах есть над чем подумать. Вспомнить хотя бы прошлый-позапрошлый год. Сегодня я даже пожалел, что командой сели решать.
для каких-то неполноценных школьников. в прошлом году этот же контест был куда интереснее
У них на контесте только одна команда все решила, я бы на месте организаторов по поводу баланса не расстраивался.
Как задачи B и I решались?
В B разбирал случаи, l-1 > max(m, n) — неудача, k = 1 легко, при k >= 4 ответ всегда есть (квадратики размера (l-1)x(l-1)), иначе l = 2 возможно только при n > 1 и m > 1; если же l > 2, то хватит двух букв (шахматное замощение с клеткой 1x(l-1) или (l-1)x1).
I делал динамикой по размеру госбюджета, переход за k, сложность O(nk).
Спасибо!
А можно чуть подробнее про пересчёт динамики?
Храним пары dp1[i] и dp2[i] — сколько бюджета удастся распилить соответственно первому и второму игроку. Перебираем ход первого от 1 до k, пусть j. Если i — j < 0, то первый выгадывает m миллиардов, а второй ничего. Иначе первый получает j + dp2[i — j], а второй — dp1[i — j]. Максимизируем по всем j выигрыш первого, при равенстве минимизируем выигрыш второго. Ответ — dp1[n].
У меня было две динамики: dp1[i] — количество денег, которое получит игрок, делающий ход первым, при том, что размен бюджета равен i, dp2[i] — количество денег, которое получит игрок, делающий ход вторым. Соответственно, мы максимизируем первую динамику и по возможности минимизируем вторую. Выбираем базу динамики как dp1[0] = dp2[0] = 0 (если в бюджете денег нет, то никто ничего не получит). Далее проходим i в порядке возрастания и перебираем j. Для фиксированного i и фиксированного j имеем: если j > i, то dp1[i] = m, dp2[i] = 0 (мы запросили больше денег, чем есть в бюджете), в противном случае — dp1[i] = dp2[i — j] + j, dp2[i] = dp1[i — j] (мы взяли j миллиардов из бюджета и передали ход оппоненту).
UPD. Опоздал :).
Как же решалась задача H? Может кто поделится мыслями. Спасибо.
Если отрезки параллельны, то ответ или 0, или -1. Нужно аккуратно посмотреть на проекции концов одного отрезка на прямую, содержащую другой отрезок, и наоборот. Иначе проводим через концы отрезков четыре прямые, пересекаем, считаем площадь четырёхугольника.
А ответ 0 когда они совпадают? А -1 когда на параллельных прямых? И зачем нам смотреть на проекции? Если можно поподробнее расскажите. Спасибо.
Когда они совпадают, ответ как раз -1.
Если проекция левого конца первого отрезка попадает либо внутрь, либо в левый конец второго, то ответ -1. Если проекция правого конца первого отрезка попадает либо внутрь, либо в правый конец второго, то ответ -1. То же самое наоборот. Иначе 0.
Можно было не пересекать прямые, а заметить, что площадь пересечения полосок равна произведению длин заданных отрезков, поделенному на синус угла между ними :).
http://acm.timus.ru/problem.aspx?space=126&num=10
O_o_0