CodeChef invites you to participate in the February 2012 CookOff.
Time: 2130 hrs 19th February 2012 to 0000 hrs, 20th February 2012 (Indian Standard Time — +5:30 GMT) — Check your timezone.
Details: COOK19
Registration: Just need to have a CodeChef user id to participate. New users please register here
Problem Setter: Короткевич Геннадий (tourist)
Problem Tester: Tolstikov Aleksey
It promises to deliver on an interesting set of algorithmic problems with something for all.
The contest is open for all and those, who are interested, are requested to have a CodeChef userid, in order to participate.
Bump :)
The contest starts in 7 hours. Good luck all!
It's Minsk time or Moscow?
"In 7 hours" mean, that 7 hours left until start
"in 7 hours" means "after 7 hours". It's
18:0019:00 Minsk time and 20:00 Moscow time.Thanks
It's 19:00 Minsk time, not 18:00.
Sorry, I've mixed it with Kyiv. These DST laws' changes confuse me.
Всем успехов!
топ сколько получают футболки?
10 вроде
не видать мне ее :(
как решать Careful Calculation?
UPD а, ок, editorials же появились)
Воспользуемся тем, что fi(N) = (p1 — 1) * (p2 — 1) * ... * (pn — 1) * p1 ^ (d1 — 1) * ... Рассмотрим это выражение. Если pi = 2, то тогда у нас каждый ход его степень будет уменьшаться. Если же pi != 2, то тогда через некоторое число шагов мы сведем его к 2^x (т.к. только из 2ки делитель может перейти в 1). При этом заметим, что каждая степень нечетного числа будет давать сомножитель 2ку в какой-то после каждой операции. А тогда посчитаем для каждого простого числа, следующую величину: если мы будет к нему применять phi(p) до тех по пока он не станет 1, сколько степеней 2ки мы при этом получим. А тогда в силу того что делитель 2 исчезнет последним, и мы может без труда в какой степени войдет 2 после всех операций, то уже нетрудно посчитать ответ. Возможно не совсем хорошо объяснил, но я думаю идею понять можно.
Как разобрать случай a = 0 в задаче про уравнение. Или же есть способ, который забивает на все это.
тогда произведение, деленное на НОД, должно быть делителем с
Не понял. Произведение чего?
x*y
x*y, деленное на НОК — НОД. Но с может не делится на НОД. (a, b, c) = (0, 2, 3) (x, y) = (5, 5) или я где-то тупанул?
эм, ты спросил, как разбираться со случаем a=0. отвечаю: нужно перебрать все делители с — это будут возможные произведения x*y/((x, y)^2)
UPD я сначала ошибся, именно НОК/НОД должно быть делителем с
задачу Bears and Bees пришлось пихать руками и ногами
А как её решать? Просто по моим оценкам у G3 может быть очень большое число вершин и рёбер, а как считать не зная число вершин и ребер не зная ребер текущего графа я так и не смог придумать.
Легко посчитать количество вершин и рёбер в G2 за O(M). Легко видеть, что в G1 не больше 499500 рёбер. Объединив, получим, казалось бы, простое решение.
я явно строил G1, а потом считал степени вершин в G2. с помощью этой информации нетрудно восстановить количество вершин и ребер в G3
Вершины G2 — это пары смежных ребер G0. Ребра G2 — это пути длины 3 в G0. Количество вершин G3 = количество ребер G2. Количество ребер G3 — сумма Deg * (Deg — 1) / 2 для всех вершин G2. (Это вообще верно для любой пары Gi, Gi + 1).
"Ребра G2 — это пути длины 3 в G0." — вроде кроме путей длины 3 есть ещё деревья вида (1, 2) (1, 3) (1, 4) и они будут представлять 3 ребра.
Да, точно, я имел в виду — пары соседних ребер с одним общим.
В каких случаях в Equation Solver ответ -1? Понял что при a = 0, b = 0, c = 1 и при a = 0, b = 1, c = 0. Есть ещё какие-нибудь?
При a=b=0 c=1, ответ 1.
Ответ -1, когда a=0, b>0, c=0.
a = c = 0, b > 0. В случае a = b = 0, c = 1 подходит x = y = 1