The USACO 2012 US Open contest is available April 6 through April 9. The contest is available in three divisions: bronze, silver, and gold. The contest is 5 contiguous hours in length. Предлагаю после окончания обсуждать тут задачи, всем удачи!
→ Обратите внимание
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | ecnerwala | 3649 |
| 2 | Benq | 3581 |
| 3 | orzdevinwang | 3570 |
| 4 | Geothermal | 3569 |
| 4 | cnnfls_csy | 3569 |
| 6 | tourist | 3565 |
| 7 | maroonrk | 3531 |
| 8 | Radewoosh | 3521 |
| 9 | Um_nik | 3482 |
| 10 | jiangly | 3468 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 162 |
| 4 | TheScrasse | 159 |
| 5 | nor | 158 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 151 |
| 8 | SecondThread | 147 |
| 9 | orz | 146 |
| 10 | pajenegod | 145 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 25.04.2024 08:39:10 (k1).
Десктопная версия, переключиться на мобильную.
При поддержке
The problems were good :)
I hope the results will be soon.
Я так понимаю, контест уже закончен. Кто как решал задачу про веревку (Gold)?
Я сделал там O((2^n)*m). Для каждой маски искал, зацепиться ли за нее или нет (при этом учитывал все точки маски вместе), а также зацепиться ли за какую-то из подмасок данной маски (тогда и за текущую точно зацепится).
Тогда нужно для вертикального "отрезка" проверять, убежит ли Бесси или нет. Для этого я искал сколько переходов слева от "отрезка" было сделано сверху вниз, а сколько снизу вверх, если оно ровно — значить убежит, иначе — нет.
Под "отрезком" имеется ввиду набор точек из маски, так как рассматривать как полный отрезок из точке маски (и относительно него проверять) не совсем верно.
А ты?
У меня вообще шаманство, которое я не доказывал. Я для каждой фиксированной маски проверял, можно ли убежать, следующим образом. Рассмотрим все тройки последовательных точек. Если в треугольнике с вершинами в этих точках не лежит ни одного столба из маски, то удаляем центральную точку из трех. Повторяем это упрощение до тех пор, пока можем. Если осталось 2 точки, то убежать можно, иначе — нет. Если аккуратно писать, то можно за O(2^N * M) реализовать.
Вывел N/2. И решал 2-3ю :)
Я думал, я один так решал :D
У меня еще один знакомый, не долго думая, вывел рандом приближенный к этому числу(по идеи такое могут вообще на 0 поставить если будет 2 раза прогоняться на тестах) :)
Как по мне, эта задача самая необычная. Я даже представить не смог, как оно должно распутываться. Немного порисовал на бумажке, на тесте из условия проверил свое решение, сдал и даже не тестил.
Мне просто показалось, что следующие задачи должны быть на порядок интереснее, а эту мало кто порешает, и вероятность неправильно что-то сделать или набажить очень велика.
Вот статья про это http://arxiv.org/pdf/1203.3602v1.pdf , но как перевести картинку в это самое слово я так и не придумал =(
Кто как писал 3ю? У меня 3^N с кучей отсечений, пару тестов должно затаймить(например, когда все числа равные).
У меня 3^N, но я не смог придумать как его сломать. Мое решение. На 20-ти равных четных не ТЛ-ит.
20 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288 1048576На ideone на таком тесте работает 3.7 секунд.Ну у меня решение за O(3^k * 2^(N-k) + 3^(n-k)). Для N = 20 выбирал k = 7. Решение следующее: разделим всех коров на 2 группы, в первой группе k коров, во второй N-k. Для обеих групп переберем все пары (маска, подмаска) и найдем суммарный баланс между коровами, попавшими в подмаску и коровами, попавшими в маску, но не попавшими в подмаску. После этого запомним пары (маска, баланс). Затем отсортируем и сделаем unique, т.е. уберем повторы. Переберем все пары (маска, баланс) из меньшей группы. Для каждой пары переберем все пары из второй группы, для которых баланс в сумме с нашим дает 0. Ясно, что таких пар не более 2^(N — k).
Классная идея, я думал что-то похожее не контесте, но не дошел до того что можно не поровну брать.
Такое же решение, правда долго не думал, k взял равное половине N.
Просто для каждой маски смотрел, сколько у неё подмасок и сколько существует масок с суммой равной её половине. Ну и потом пробегал по тому, чего меньше.
А не валится на тесте 20 2, 2, 2 .. 2 ?
Ну это не очень хитрый тест — для всех масок нечетного размера сразу найдется, что подходящих подмасок нет, а если размер четный, то первая же проверенная подмаска подойдет.
У меня решение такое — посчитаем все суммы, а так же отсортируем соответствующие подмножества в порядке возрастания сумм. Теперь обойдем все множества и будем искать все множества с суммой половина от данного. Если хоть одно из них полностью лежит в нашем множестве — профит
I whish this discussion was not only in russian. I have a solution to divide set X into A (N/2 cows) and B (N-N/2) cows. For each subset C of A (the same for B) I count each possible value of any subset of C. Then for each subset E of N cows I divide it into A1 and B1 such that A1+B1 = E and A1 is the subset of A and B1 is the subset of B. I check each value for A1 and look for the appropriate value in B1 — if I find it, it means that E can be equally divided.
I'll repeat mine in English omiting technical details — basically for each subset A I iterate through all subsets B so that sum(A) = 2 * sum(B) and if
then A is good
Meet in the middle — this is the key, I got the same solution as described in analysis :)
А оно без никаких дополнительных эвристик успевает? Можно код глянуть?
Не совсем понятно. Локально работает 2 с небольшим секунды, на сервере ТЛ 4 для Java. Посмотрим
2 таймлимита в итоге