6 апреля в Самарском государственном университете прошел III (XIV) открытый командный студенческий чемпионат Поволжья по спортивному программированию. Теперь мы приглашаем всех желающих, кто не был на чемпионате, принять участие в соответствующей тренировке 28 апреля с 11:00 до 16:00 по московскому времени . Мы полагаем, что участники любого уровня смогут найти интересные для себя задачи, однако наибольший интерес тренировка будет представлять для участников фиолетового и оранжевого уровня (сложность ****).
Тренировка пройдет по правилам ACM, задачи будут на русском и на английском языках. Для ввода и вывода используйте файлы input.txt и output.txt.
Также просим не использовать интернет, prewritten код и иные материалы — участникам чемпионата это было недоступно.
Контест готовили: Дмитрий Матов (Nerevar), Константин Дроздов (I_love_natalia), Андрей Гайдель (Shlakoblock), Елена Рогачева (elena), Сергей Штейнер (steiner), Дмитрий Новиков, Александр Ефимов и Геннадий Натанович Гутман.
Ванга снова ошиблась — вместо кларов были некорректные тесты и слабые тесты :D
Will the problem be in English or Russian？
both
I wonder why there is 2 extra minutes
At the contest (in Samara) technical hitch occured, and the jury decided to add 2 minutes.
This 2 minutes can be useful to the Samara's contestents.
Actually, last Accepted in Samara was at 4:59:48.
Knowing where to start reading the problem is a good skill used today :)
I totally agree with you. Stories don't make much sense but the problems are good. I really enjoyed the contest :)
Задача D. Валидаторы? Не, не слышали. Лучше мусор в конец файла дописать.
Задача F. Подумать над хорошими тестами? Это для нубов. Участники pva701 и mexmans, ваши решения этой задачи неверные, в дорешке они будут получать WA.
pva701 and mexmans, your solutions of F are incorrect. Both of them fail on this test:
I still don't clearly understand the task in F. Do we start with the letter z or a random letter of the latin alphabet. At each step are we allowed to replace only the letter 'z' or any letter in the text?
We start with letter 'z' and each step we replace any letter 'z' in the text with the pattern.
Thanks a lot :-)
А в J
должно было заходить?
Похоже, что нет. Быстрейшее из авторских за n*log(n) работает полсекунды.
Как решалась K?
Нужно было закодить то, что написано в условии. То есть проверить каждую область. Если она на всех цифрах включена, то 1, если на всех выключена, то -1. Объяснение такое: не существует такой области, которая бы была всегда включена либо всегда выключена (КЭП какбы). Если порисовать эти циферки на бумажке, то будет видно уж точно
спс
А как I решается?
Генеришь всевозможные маски, выбираешь те, которые подходят по условию. Затем идёшь по изначальной строки и смотришь префикс. Если найдётся префикс, который отличается с позициии I, то к ответу прибавляешь 1
как решалась задача G ?
Отсортировать массив и проверить пары соседних элементов.
А что-нибудь типа разбора есть (с более менее строгими объяснениями)?
как можно доказать это ?
Возьмем три числа a,b,c (a < b < c). Докажем, что min(a xor b, b xor c) < (a xor c).
Рассмотрим первый бит, где эти числа различаются.
1. В a этот бит равен нулю, в b и c — единице. Тогда (b xor c) < min(a xor b, a xor c).
2. В a и b этот бит равен нулю, в c — единице. Тогда (a xor b) < min(a xor c, b xor c).
Ну и отсюда следует, что надо рассматривать только соседние элементы.
Мы на контесте ничего не доказывали, просто было интуитивно это понятно.
спасибо :) я не смог доказать по этому не написал :(
Сортишь и выбираешь максимальный ксор из подряд идущих чисел
Как C решать?
Насколько я помню, бинпоиск по ответу, а потом динамика d[i][j] — минимальное количество цветов, которое надо посетить, чтобы добраться до клетки (i,j).UPD. Похоже, я все-таки не помню задачу (писал ее Hohol) Только помню, что были бинпоиск и динамика. Пусть кто-нибудь еще расскажет)
UPD 2. Решение тут: http://codeforces.com/blog/entry/7493#comment-131742
Вы про ту же задачу, что и я? Там вроде цветов не было... Если да, то расскажите, пожалуйста, подробнее
Я буковки в матрице называю цветами.
Блин!
Тесты в C тоже слабые.
Прошло решение работающее за сумму квадратов сторон всех прямоугольников на каждом шаге дихотомии. Валится очевидным тестом вида:
Только 1000 на 1000.
Я даже заслал решение, которое генерит этот тест внутри себя, а не считывает из файла, и получил законный TL.
В условии сказано Каждому землевладельцу принадлежит только одна связная прямоугольная область, разные буквы служат лишь для разграничения связных областей, касающихся друг друга.
Правильно. Это как раз и означает, что разные прямоугольники с одной и той же буквой принадлежат разным землевладельцам.
Поэтому тест корректен.
Видимо я не понимаю, но ведь сказано, что Каждому землевладельцу принадлежит только одна связная прямоугольная область Значит у него не может быть больше связных областей
Буквы нужны только, чтоб разграничить прямоугольники, и никак не связаны с землевладельцами. В тесте N разных прямоугольников, и каждый принадлжежит отдельному землевладельцу.
ясно
Я придумал решение, придумал этот тест. Потом решил проверить, работоспособность того, что я написал, и был удивлен когда вместо ТЛ получил АС :)
На нашем сервере этот сабмит получает WA-1, а не TL-1.
d[i][j] — минимальное количество клеток из того же прямоугольника, что и (i, j) на конце пути (1, 1) — (i, j)
Бинпоиск по ответу.
Внутри бинпоиска нужно проверять, существует ли путь, ни для какой области не посещающий более k ее клеток. Заведем такую динамику: dp[i][j] — наименьшее возможное число посещенных клеток, принадлежащих той же области, что и клетка (i,j). При этом, если получилось, что для клетки значение динамики равно k, значит из нее уже нельзя делать переход на клетку той же области.
Can anyone explain the sample of Problem B?
I think the answer of the sample is 19 as the problem describes
No offense. The statement in english is quite confuse.
In problem D, all the number should be 'non-negative' not 'positive'. And in input description, M should be the number of 'portions' not 'days'.
In problem J, the range of U, 1 ≤ U ≤ N is wrong.
Especially for D, the confusion and rejudgement drove me crazy for quite a long time.
Anyway, preparing contest is a huge and tough job, we can never ask for a perfect contest. Thanks for this contest. These two gyms really delighted my weekend. :)
Как решать B?
How to solve B?
edit , wrong place