Topcoder SRM 550 = 2 * 5 * 5 * 11

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

+16

Кот педро, ага :)

→ Ответить

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

+31

По такому поводу будет три 550-ых задачи?

→ Ответить

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

только у меня время в арене неверное?

→ Ответить

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

← Rev. 2 →

+14

Они же уже разослали, что знают и фиксят.

UPD. Отлично пофиксили!

→ Ответить

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

← Rev. 2 →

Спасибо.

Ничего не приходило.

UPD: Вижу теперь

→ Ответить

gerasimovd

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

А что-таки произошло? На сайте ничего нет.

→ Ответить

ant.ermilov

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

Время топкодера стало на 5 часов меньше реального.
Для фикса вместо того, чтобы поправить время, сделали старт контеста на 5 часов раньше.

→ Ответить

gerasimovd

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

← Rev. 2 →

Э, то есть он уже прошел? o_O

→ Ответить

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

Нет. реально он будет в тоже время. Просто время на TC не совпадает с реальным.

→ Ответить

ant.ermilov

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

← Rev. 2 →

Ну из-за того, что время в арене всё ещё на 5 часов отстаёт -- всё будет как запланировано (в 20:10 Саратова)

→ Ответить

Vladyslav

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

← Rev. 2 →

Привет всем. Это будет мой первый контест на топкодере. И я, честно говоря, не совсем разобрался что там да как. Если кому не сложно, пожалуйста, опишите вкратце то, как проходят там контесты.

→ Ответить

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

+18

Почитайте вот это.

→ Ответить

Vladyslav

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

Большое спасибо)))

→ Ответить

Prestige

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

← Rev. 3 →

-19

Я понял)

→ Ответить

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

Как решать 850?

→ Ответить

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

+24

Вычисляем мин. стоимость, проверяем что maxCost на неё хватает, смотрим сколько раз можно ещё сделать цикл a->b->c->a , пусть минимальное число ходов это moves, и можно сделать cycles циклов.

От текущего слова нам нужно три параметра: сколько букв совпало, скольким нужна одна замена, скольким две. Итого состояний порядка N²т.к. их сумма это N.

Когда мы делаем замену, состояние меняется линейно. Берём соответствующую матрицу, добавляем туда строчку куда будем писать сумму для состояния (N, 0, 0), возводим в степень moves+cycles+1 и смотрим в клеточку соотв переходу из начального состояния в сумму, там будет ответ.

Осторожнее, сумма cost_i и минимальная стоимость может вылезти за int.

→ Ответить

Zlobober

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

← Rev. 2 →

Жадность фраера сгубила.

Расскажите, как третью делать? Свёл к умножению многочленов длины 10^9 / 3, узнал, у какой функции ряд Тейлора $\text{[math]}$ , но так задачу и не решил. В решении чувака из моей комнаты, которое я не смог завалить, было какое-то двоичное масштабирование.

→ Ответить

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

Смотри выше.

→ Ответить

ilona

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

+12

УГ раунд.

→ Ответить

dalex

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

А мне норм.

→ Ответить

Zlobober

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

Ну как, первая — ничем не примечательная реализация, вторая — "или ты увидишь C(n, k) и знаешь как его быстро считать по модулю два, или нет", а вот третья вызывает интерес.

→ Ответить

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

← Rev. 2 →

Эм, расскажи про цешку? Решал как-то кажется совсем по-другому

Упс, допер идею, ок.

→ Ответить

Zlobober

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

← Rev. 2 →

-6

У тебя получился красивенький фрактал. После некоторого афинного преобразования (кажется, прямую y=x надо перевести в прямую x = 0) получится треугольник серпинского, или, что то же самое, $\text{[math]}$ в точке (x, y). А дальше магия: C(n, k) чётно тогда и только тогда, когда (k | n) == n.

→ Ответить

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

Ага, спасибо. не заметил сходу Cшки, проверял шаманской рекурсией)

→ Ответить

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

Когда я решал вторую то я не заметил связь с Cⁿ_k). Просто понял что это фрактальчик. Хотя да, по формуле она сразу видна.

→ Ответить

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

+11

Автор математик. 300 — реализация как реализация. Туповатая слегка, но вполне жизнеспособная. А дальше надо думать. Тут это почему-то не любят. Хотя давать 500-ку на "либо ты умеешь проверять Сшку на четность магическим выражением (n&k) == k либо убиваешься любым доступным тебе способом это действительно не очень хорошо.

→ Ответить

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

+22

Вау, а я всегда делал это рекурсивно по треугольнику Серпинского за логарифм.

→ Ответить

dalex

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

Офигеть, эта штука еще как-то называется! Я когда вывел правильные формулы, время уже кончилось...

→ Ответить

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

← Rev. 2 →

Кстати, треугольник Серпинского за логарифм хорош тем, что обобщается на произвольный модуль вместо двойки. Вот даже задача об этом http://projecteuler.net/problem=148 .

→ Ответить

KADR

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

Я хоть и подозревал, что простая формула за О(1) должна следовать из теоремы Люка, но на контесте кодил за логарифм методом, который всегда использовал. Возможно, это и есть решение по треугольнику Серпинского.

Идея состоит в том, чтобы найти степень вхождения в числитель и знаменатель формулы подсчета C(N, K). Если степени равны, то оно не делится на 2, иначе — делится. А проверить степень вхождения числа p в N! можно одним циклом:

while (n /= p) ans += n;

→ Ответить

SkyHawk

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

← Rev. 2 →

А можно, в таком случае, объяснить решение 500?

UPD: Спасибо

→ Ответить

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

Можно.
0. Клетки с нечетным (x+y) и x < y пустые. Это очевидно из формул.
1. Оставвшиеся клетки представляют собой треугольник. У клетки есть две предыдущих — как раз описанные в условии.
2. Клетка либо пустая, либо ее цвет зависит от чего-то вроде $\text{[math]}$ .
3. Из формул в клетке записан ксор предков. Что тоже самое $\text{[math]}$ .
4. По простому модулю цешка равна произведению цешек по разрядам в p-ичной системе счисления. Это проверяется явным вычислением. По модулю 2, это значит, что она 1, только когда все биты в k не больше чем соответствующие в n. Что тоже самое (n&k) == k.

→ Ответить

SkyHawk

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

Спасибо!

→ Ответить

tyamgin

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

Не совсем понятен пункт 3. Почему ксор понятно, но откуда берётся переход к C((x+y)/2, y). Можете обьяснить?

→ Ответить

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

Получающаяся конструкция соответствует треугольнику Паскаля по модулю 2 (т.к. каждый слой на 1 длиннее предыдущего, и значение определяется как сумма двух предков в предыдущем слое по модулю 2).

→ Ответить

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

В момент t заполняются только клетки x+y = t*2 , доказывать индукцией.
Приняв 1. за правило можно считать что все фишки одного цвета.
если D[x][y] = 1 если в x,y есть фишка, то условие состоит в следующем: D[x][y] = (D[x-2][y] + D[x-1][y-1]) mod 2
оно очень похоже на C[n][m] = C[n-1][m-1] + C[n-1][m]
делаем очевидную замену, получаем эти C-шки.

→ Ответить

tyamgin

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

Вот! То что надо. Теперь понятно, спасибо.

→ Ответить

Gassa

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

Из комментариев, в общем, видно, что это далеко не единственное решение 500-й. Можно уметь узнавать и считать $\text{[math]}$ , можно просто по картинке рекурсию делать, можно, наверное, погуглить треугольник...

→ Ответить

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

Я это и назвал убиться любым доступным тебе способом. Это все представляет собой в той или иной форме проверку остатка цешки.

→ Ответить

Gassa

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

Ну не знаю... я гораздо больше очков слил на ресабмит int -> int64 в одном месте, чем на придумывание этой рекурсии. А красивую формулу за O(1) только в этом обсуждении узнал.

→ Ответить

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

Я хотел на зимние сборы это дать. Мне сказали что баян :)

→ Ответить

Sammarize

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

Не понравилось, что третья задача была 850 (первый раз вы жизни вижу на ТС, чтобы третья задача стоила меньше 900) — то есть, очень простая для третьей. А реально она по сложности была не проще обычных.

→ Ответить