Прям сейчас начался четвертьфинал в Саратове. Болеть можно по ссылке результаты.
В понедельник можно будет принять участие в зеркале на http://acm.sgu.ru/. Время начала зеркала 22 октября (понедельник), 2012, 16:00. В ранклист зеркала будут интегрированы результаты официальных участников. Позже появится тренировка и на Codeforces.
Из особенностей нашего четвертьфинала хочется упомянуть:
- CodeGame Challenge,
- участники сами выбирают писать под Windows или Linux — да, тестируем тоже в двух режимах,
- набор задач, интересный разным по уровню командам,
- в этом году поддержали интерактивные задачи — есть такая в проблемсете.
Надеюсь, что участникам понравится контест!
Пофикшенная ссылка
Пожалуй, один из самых интересных четвертьфиналов для просмотра наравне с Северным и Московским. Удивительное что-то там происходит. Команда Samara SAU, которую я считаю одним из кандидатов на место в тройке, за более, чем пол часа не сдала ни одной задачи. Зато команда Samara SAU 2 сдала задачу, которая за первые пол часа не была обозначена, как "халява".
Было бы классно, если задачи в тренировках на codeforces будут перемешаны :) Для тех. кто следил за результатами и будет писать контест позже.
Саратов традиционно так и делает. Давным-давно, когда я об этом еще не знал, меня очень удивляло, как на четвертьфинале не сдают такие простые задачи :)
Ааа ну тогда хорошо :)
JKeeJ1e30 вперед!
Мы слили. Нам стыдно:(
По-моему все вопросы о победителе за 2 часа до конца соревнований Saratov SU #1 уже сняли. Таблица приняла более-менее ожидаемые очертания, и теперь остается только узнать, кто займет второе и третье места. Хотя два явных кандидата на эти места уже тоже известны.
А вдруг, Saratov SU #2 быстро добили C и в конце сдали B, а Saratov SU #1 поймали тупняк и не сдали ничего? :)
Не верю! Кстати, взываю к участникам онсайта. Расскажите что там, да как: кто победил, кто сколько сдал, кто прошел на полуфинал. Интересно же :)
Ну мы сдали еще одну задачу K, и не успели додебажить C.
Я поспрашивал, вроде 7ю никто не сдал, из тех у кого было 6ть в заморозку.
Стоит отметить, что задача К как раз и была интерактивной и предполагалась одной из самых сложных в контесте. Saratov SU #1 сдали по ней решение, отличающееся от решения жюри.
Вместо монитора "Got error 28 from storage engine".
Ну хоть замороженный бы оставили.
"Traditionally thanks to Michael Mirzayanov (MikeMirzayanov) for perfect Codeforces system and Polygon system"
WIN
Problem Tree Queries Online is really great. (spoiler in the first revision)
Any one can be solve it by link-cut tree ? .. .
Can you tell me how to solve the problem Tree Queries Online?
is there any site related to this contest and has analysis of the problems ?
I'm still stuck at problem K(database optimization). any hint?
Save all submasks of the first part of input (15*N strings or, better, their hashes, in total) in the hashmap. Then you can answer to each query very fast. Also, all submasks and queries should be sorted, this guarantees the correct comparison.
Thanks :) I got accepted :)
Может кто-нибудь багу в геометрии найти?
Where can I find solutions for this contest, there were a lot of interesting problems.
А какая последняя команда из прошедших?
Самарский ГУ (Samara SU #1)
Samara SU #1, занявшие 19 место.
А можно где-нибудь посмотреть фотки/видео оттуда? :)
P.S. Очень запомнился момент во время CGC, когда оператор назойливо пихал камеру нам в лицо :D
Did anyone solve problem Sultan's Pearls using two pointers method? It has been mentioned on the problem analysis, but now I think that it's wrong because the number of pearls stolen from the table does not always decrease with increasing the number of pearls stolen from the hanging part.
I have a test: n = 10, m = 3, weights are {1000, 1, 1, 1, 1, 1, 1, 1, 3, 1}.
If we steal no pearls from the hanging part, we can steal two pearls from the table:
{1000, 1, 1, 1, 1, 1, 1} + {1, 3, 1} -> {1, 1, 1, 1, 1} + {1, 3, 1}
Then, if we steal one pearl from the hanging part, we can steal only one pearl from the table:
{1000, 1, 1, 1, 1, 1, 1} + {1, 3, 1} -> {1, 1, 1, 1, 1} + {1, 1, 3}
And if we steal two pearls from the hanging part, we can steal two pearls from the table again:
{1000, 1, 1, 1, 1, 1, 1} + {1, 3, 1} -> {1, 1, 1} + {1, 1, 1}
So how to use two pointers method in this problem? Or it doesn't work here?
I modified it a bit, so that the second pointer can move in both directions and it passed (the worst case seems to be n^2, doesn't it?). Instead of two pointers method, we can use binary search to find the position of second pointer.
By the way, can you share the problem analysis?
That's funny, I think there must be O(n^2) test (what if we make right part like "1 1000 1 ... 1 1000 1")?
Maybe it's something like 1000*n in worst case?
I know about binary search, I wonder if there is O(n) solution.
Problem analysis that I have is in Russian only, recorded with the mobile phone camera, if you still want to watch it, check this link (there also are funny videos from Code Game Challenge on this channel).
You can use binary search to find the rightmost position of the second pointer.
Imagine that we decrease the number of pearls stolen from the hanging end. Greedy order is optimal, so after some math, we're left with queries for the largest prefix sum ≤ x.
Now, if the weight w of the last m pearls left on the hanging end after stealing decreases, x inreases and we can use the obvious 2 pointers to answer queries.
If, in some step, w increases, then x (and the prefix we're looking for) decreases, so the cost of all pearls that can be stolen from the lying end doesn't increase. But in every step, the cost of all pearls stolen from the hanging end decreases as well, so this can't be the best solution. We just skip and wait until the prefix pointed 2 by our 2nd pointer is ≤ x sometime later, and resume moving the 2nd pointer.
А фотки с контеста и награждения будут?
А где можно найти тесты и авторские решения?
Нигде в инете не нашел. У Михаила Мирзаянова попросить, что ли. Он же вроде председателем жюри там был.
В тренировках можно и тесты, и решения достать)
Как? Насколько я знаю, только тренеры могут.
Ну да, просто попросите знакомых
Нет таких(