USACO January - Codeforces

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

Кто-нибудь может объяснить, зачем вообще во второй дается последовательность ходов? За 2 часа так и не удалось понять :(

→ Ответить

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

← Rev. 2 →

Просто чтобы "проэмулировать" какое-то развитие игры

→ Ответить

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

← Rev. 2 →

Там получается, что, когда мы думаем куда бы походить на первом шаге, мы не знаем куда будет ходить Бесси; когда мы думаем о втором ходе мы уже точно знаем первый шаг Бесси и никак не знаем последующих. Стратегия должна быть такая, чтобы Джон рассуждал именно исходя из этих знаний, и ходил в гарантированно выйгрышную позицию.

→ Ответить

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

Но при том, что "Note that even though Bessie's moves are provided to you in the input, you are to specify moves for FJ that would have worked no matter what Bessie chooses", разве это не одно и тоже что надо найти последовательность которая выигрывает в любом случае т.е. независимо от ходов Бесси?

→ Ответить

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

Да, но после того как она совершила ход мы уже кое что новое знаем об игровой позиции, и можем найти не просто решение которое всегдавсегда хорошое, а пойти по чуть более лексикографически меньшему пути :)

→ Ответить

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

Однако нам нужен лексикографически наименьший путь, который работает независимо от ходов коровы, а не такой, что в зависимости от ее ходов мы пойдем по нее или более меньшему

→ Ответить

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

Но все же, я полагаю, те ходы, которые мы сделаем (Джоном и Бесси), мы можем учитывать :)

Насколько я понимаю они хотели сделать задачу какбудто с библиотекой, но без библиотеки. То есть мы на каждом шагу знаем то что было до этого, но не знаем будущих ответов:)

→ Ответить

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

+16

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

А тесты влом переделывать было

→ Ответить

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

Сейчас, с товарищем paulik обсуждали эту задачу и он предложил такую идею на вторую задачу:

Делаем перебор всех состояний и считаем выйгрышное оно или нет. На каждом ходу у нас есть 4 варианта куда пойти (по два варианта хода на Джона и Бесси), однако, если мы посмотрели, что при любом ходе Бесси ход Джона Bottom хороший, то вариант Top даже не рассматриваем (итого рассмотрели только 2 варианта), а если это не так, то значит Джон обязательно ходит Top в силу обещаной корректности и мы рассматриваем только ветвь с известным ходом Бесси. Итого 3^n вместо 4^n.

→ Ответить

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

Не очень понятно, как можно гарантировать корректность для чего-то, кроме самого первого хода - мы же не знаем точно (и нам надо узнать), выигрышная позиция или нет.

→ Ответить

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

← Rev. 3 →

Можем, мы переходим в состояние которые либо мы проверили на корректность (случай bottom) либо потому что нам обещали корректность, а раз bottom не обязательно корректен, то top должен быть :)

P.S. Да, главной загвоздкой в этой задаче было понять условие так как автор, а как это именно - узнаем вскоре :)

→ Ответить

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

← Rev. 2 →

Но чтобы узнать, куда делать первый ход, мы для начала должны проверить на корректность bottom. Т.е. сделать 4^n - 1 раундов, нет? Или мы "предположим" корректность и что-нибудь случится?

→ Ответить

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

Я написал рандомизированное решение с запоминанием для первых 7 ходов. Вроде бы работает мгновенно на моих тестах. Но в худшем случае тоже должно быть 2²ⁿ. А вообще, условие как-то странно написано. Я только через час заметил, что дорожка круглая :)

→ Ответить

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

Условие написано просто великолепно, это да

→ Ответить

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

Я это заметил через 25 минут. Зато не заметил вообще, что надо лексикографически минимальный ответ. Видимо, будет eps.

→ Ответить

gojira

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

Облом, я тоже не заметил лексмин, и моё решение работает в точности наоборот.

→ Ответить

Sereja

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

Ребят, там в конце можно в обе стороны двигаться или только по направлению к концу? Ну то-есть я считал что конечная позиция хорошая если: (end<=k) or ((m-end)<=k), это правильно?

ПС. разумеется что решение как у Egor :)

→ Ответить

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

← Rev. 2 →

Я тоже так считал. Судя по ограничению K <= floor(M/2), это должно быть правильно, иначе зачем оно вообще нужно.

→ Ответить

krasnokutskiyAton

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

Может кто-нибудь кинуть ссылку на условия (на офф. сайте написано что соревнование закончено и все)

→ Ответить

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

Если зарегистрируешься, то наверное тебе будут доступны бронзовые условия. Я со своей стороны могу скопировать куда-нибудь золотые, если надо.

→ Ответить

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

Можно смотреть сразу все дивизионы: логинишься, открываешь любую задачу и в просто адресе http://usaco.org/index.php?page=viewproblem&cpid=1** меняешь цифры.

→ Ответить

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

← Rev. 2 →

О, спасибо, но для этого как минимум надо быть зарегистрированным :)

<offtopic> Серега это ты? Что у тебя с ником :) </offtopic>

→ Ответить

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

<offtopic> Ага. Нули, единицы и шестерки немного приелись, решил все чуть-чуть поменять :) </offtopic>

→ Ответить

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

И поэтому ты теперь маленькая девочка? :)

Ну и ладно

</offtopic>

→ Ответить

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

<offtopic>
o_O Cherry tree это маленькая девочка?
Пойду английский поучу, что ли :)
</offtopic>

→ Ответить

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

На аватарку-то глянь ;)

→ Ответить

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

А, я как-раз это аниме пересматривал. :)

→ Ответить

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

А как вторую делать за 2²ⁿ? Я только n*2²ⁿ знаю.

→ Ответить

Sereja

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

Скорее всего именно это имели ввиду.

→ Ответить

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

Просто ~3*10^8 еще может пройти на их машине, а вот ~3.8*10^9 вряд ли.

→ Ответить

Sereja

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

Мне кажется что такого никогда не будет. Там либо ответ быстро будет найден, либо быстро будет вылетать вторая подзадача(если у тебя такое-же решение как у меня), то есть будет находиться ход Бесси который сделает комбинацию проигрышной.

→ Ответить

gojira

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

Можно заранее посчитать пройденное расстояние при всех возможных выборах FJ и Бесси на первых n/2 ходах, а для второй половины ходов заранее посчитать для всех возможных выборов числа A и B, где A - коэффициент, на который помножится пройденное коровами расстояние за первую половину ходов после пройдения этой второй половины, а B - свободный член, который к A*расстоянию прибавится. Используя эти величины, можно потом каждый из 2^(2n) возможных выборов за O(1) оценивать.

→ Ответить

kb.

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

А кто решал серебряный? Я первую задачу решил сжатием координат + дейкстрой, получилось довольно много писанины, может проще решалась как-нибудь? Вторая - перебор с отсечениями? А в третьей жадник на 15 строк, или я неправильно условие понял?

→ Ответить

sdryapko

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

← Rev. 2 →

Во второй dp[i][j]...это можем ли мы собрать сумму i в 1-ый ангар, и сумму j во 2-ой ангар...Дальше вроде понятно, как делать :)

→ Ответить

kb.

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

Классно! Я вечно дп не вижу :/

Ну мое решение порядка 1-1.5 секунд работало на рандомных макстестах, так что буду надеяться на мощь забугорных компов :)

→ Ответить

sdryapko

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

Насколько я знаю, на usaco медленные серваки.

→ Ответить

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

"The judging computer is a 3Ghz Intel machine running Linux."
Ну не знаю, может у нас разные понимания слова "медленный".

→ Ответить

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

Во второй силвера N = 20, там и перебор 2^N*N пройдет.

→ Ответить

kb.

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

А это как? У меня-то перебор просто 3^N, только отсечения по уже найденному лучшему ответу + в начале перемешиваю входные данные, чтобы каких-нибудь гадостей не подкинули + первое разбиение делаю жадно, чтобы больше отсекло

→ Ответить

sdryapko

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

Объясни, как за 2^n*n решать :)...я знаю, только как за O(3^n) и за O(2000^2*n)

→ Ответить

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

nevermind
Я неправильно понял условие :(

→ Ответить

KF2017

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

← Rev. 3 →

Не знаю правильно или нет . результатов ещё нет . Но я решал 2 задачу так :

находил все возможные суммы и брал первую большую (s/3), если нацело не делится то добавлял 1.

Третью то-же жадным, а первую не придумал.

→ Ответить

KF2017

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

← Rev. 2 →

А кто знает когда результаты будут. Я на новом их сайте первый раз участвую. Раньше в среду уже на почту присылали , а в пятницу на сайте было. Сейчас зашел, ничего нет.

→ Ответить

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

Вроде в районе выходных результаты открывают, на почту вообще ничего не приходит

→ Ответить

P___

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

← Rev. 7 →

Ask msg555 - it's his task.

Edit: ~~Writing handles doesn't work...~~

Edit2: Ok, thx

→ Ответить

Saken

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

msg555

I think it works ;)

You must just type by yourself

→ Ответить

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

← Rev. 2 →

Первый раз участвую в обновленной usaco и она мне явно уже не нравится :) Фишка с подсвечиванием условий цветом дивизиона, помоему была отличной, хотя это мелочи.

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

А ранжировка задач по сдаваемости тоже исчезла или просто в этом раунде такое совпадение?

P.S. Отсылка резов на мыло заранее тоже было хорошо ;)

P.S.S Пишем письменную петицию ~~Колстаду~~ какому-то новому чуваку с подписями, пускай Гена на IOI передаст ему лично и пожурит за урезаный функционал ;)

→ Ответить

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

Это еще что, в первом контесте оно даже не компилило и не проверяло на семплах :) Надеюсь, со временем старый функционал перекочует в новую систему.

→ Ответить

Zlobober

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

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

→ Ответить

Kh.Madi

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

Судя по результатам многие неправильно поняли задачу B. Кто понял, объясните пожалуйста. И как решать остальные задачи? =)

→ Ответить

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

1. Ахо-Корасик + ДП, вроде стандартная задача.
2. Последовательность ходов Бесси не важна, надо сгенерировать лексикографически минимальную последовательность ходов фермера, которая выигрывает в любом случае.
3. Ответ = произведение ответов по каждой связной компоненте: если компонента дерево, то ответ количество вершин в ней (я этого не заметил и писал ДП, мне после контеста сказали), если в компоненте ровно один цикл - то ответ для нее равен двум, иначе ответ равен нулю.
Как-то так.

→ Ответить

Kh.Madi

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

Спасибо. В задаче Б вроде так и делал, но прошел только 1 тест как у многих. За O(N*2^2N)

Вот код

→ Ответить

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

← Rev. 2 →

У меня похожая идея, может у вас опечатка где-то, так как это набирает несколько больше.

→ Ответить