Приветствую всех на Codeforces Beta Round #17, который состоится 10-го июня (четверг) 2010, 19:00 (UTC +4, Московское время). Этот контест буду представлять я.
Хочется сказать отдельное спасибо Михаилу Мирзаянову, который сделал проведение контеста возможным, Артёма Рахова за помощь в тестировании авторских решений и Юлии Сатушиной за качественный перевод задач на английский. Большое спасибо Гене Короткевичу за составление условий, написание авторских решений и красивых идей. Надеюсь, задачи вам понравятся.
Желаю чтобы число 17 оказалось для вас интересным!
Обсуждение задач предлагаю проводить здесь в комментариях после конца контеста.
UPD: Контест закончился, всем спасибо за участие!
- Задачи
- Результаты
- Победитель: winger
- Разбор задач здесь.
Лучше оставь перекрёстные ссылки на темы с подписью:
Просьба отписываться тут (ссылка)
Я правильно понял, что автором задач и решений по сути выступает Гена Коротевич?
Тогда сразу вопрос - почему автор контеста не он, а Вы? Он на столько скромный ? :)
Но возможно я слишком оптимистичен, и brainail всего лишь представляет контест, хотя это было бы странным.
http://codeforces.me/profile/MikeMirzayanov
There you can send a personal message if you want, ofc.
Also, there were a link on the contest page to publish a question.
using map in c++?
what about this?
3
3 2 13
1 2 400
1 3 100
2 3 100
How do you handle that? I was going to write
3
3 2 1
3
1 2 400
1 3 200
2 3 100
I think it should do better with Prim's.
The problem assure us that the input is well formed (q[j]>q[i]). So we don't need to process the q value and the name of the employee that made the offer.
At the end we only need to check if at most one employee is without a boss.
For some reason during all the contest I thought that the string could contain any characters from 'a' to 'z' . I just realized that the only allowed characters are 'a','b' and 'c' =(
I will try to solve it using DP as you suggested =)
a^b % c == (a % c) ^ (b % phi(c)) % c
где phi(c) - функция Эйлера.
Правда, есть одна тонкость - если a^b %c = 0, то этот метод может спалиться (даст не ноль). Можно понять, что это происходит, когда (a % c) ^ (phi(c)) = 0 и b >= phi(c). Поэтому в случае b >= phi(c) надо ещё взять (a % c) ^ (phi(c)) и посмотреть, не ноль ли он. Ну или может есть какой-то другой хак, не знаю.
P.S. Do you know Russian or you use Google translate? :)
If n is quite small (say, less than 5 digits), then you can simply calculate
bn - 1(b - 1) modulo c.
Otherwise, let c = c1c2 with c1 and c2 coprime, and c1 consisting of primes dividing b. Then bn - 1 = 0(modc1) (because n-1 is very large), and bn - 1 = b(n - 1)modφ(c2)(modc2) (because b and c2 are coprime).
And if we know the remainders modulo c1 and c2, then we can calculate the remainder modulo c, using the GCD representation kc1 + lc2 = 1.
if n is less than 1000 then n1 = n;
else n1 = n mod phi(c) + 10 * phi( c );
answer is b1^n1 mod C
Instead of dividing the bignum by 2 directly I multiply it by 5 and divide it by 10, and just keep a variable to point the first number before the decimal point.
let n = 10^k,
my solution is O(klogk) and k is at most 1 million. Most problemas I've done it's enough to pass.
So can someone please explain the problem with this approach? Or the idea it was intented to pass and the implementation was bad?
Thank you in advance.
So in the end you have an O(d2) algorithm which is too slow when d~106 as in this problem.
а квалификацию я использовал для определения главного начальника=)
Decide = принять решение
Solve = решить (задачу)
К сожалению прпоустил контест (проснулся за три минуты до начала. регистрация была закрыта :о( )
Почитал задачи. Очень понравились D и E, особенно Е - действительно клевые задачи. Не понравилась С :о)
Опять же, поощрительные должны быть проще :о)
Недавно я изучал решение одного очень уважаемого программиста задачи Е с этого контеста и случайно обратил внимание на 45-й тест:
Казалось бы, что в этом такого? Но вот если загуглить число 731, то можно обнаружить ссылки на японский нацистский концлагерь! Таким образом, автор тестов явно хотел вставить оскорбление светлой даты победы "1945" этим гнусным числом.
В какой-то другой день, я, возможно, не стал бы обращать на это внимание, но сегодня день особенный и я не мог просто пройти мимо. Мне кажется, что автора контеста нужно, как минимум, дисквалифицировать навеки, а как максимум — полностью откатить результаты контеста, чтобы преступление пятилетней данности никому не сошло с рук. Как думаете вы, завсегдатаи ресурса?