За пределами Самары мало кто знает, что в Самаре 18 марта прошло межвузовское первенство по спортивному программированию. Это одно из двух первенств, проводимых ежегодно в Самаре.
В общем, все желающие потренироваться, кто не был на этой олимпиаде, могут принять участие в соответствующей тренировке на Codeforces. Тренировка будет по правилам ACM, задачи будут на русском языке и, почти наверное, на английском языке.
Задания были подготовлены Алексеем Дергуновым (dalex), Никитой Глащенко (Hohol), Павлом Семушиным (craus) и Андреем Гайделем (Shlakoblock). Тестировали комплект я (I_love_natalia) и Наталья Бондаренко (natalia).
Тренировка будет наиболее интересной для участников фиолетового и начального оранжевого уровня (сложность ***). Красный участник, видимо, закончит контест сильно заранее (каждому из тестеров понадобилось порядка трех часов). В комплекте есть задачи различного уровня простоты.
Пройдет тренировка 24 марта в 16:00 по московскому времени, участвовать приглашаем всех желающих.
Просим при участии не использовать prewritten код и вообще материалы в интернете в знак уважения к призракам участников олимпиады, которые будут участвовать с вами ;)
Upd. Время поменяли на 16:00.
Upd2. Для ввода-вывода используйте файлы input.txt и output.txt!
Upd3. Не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.
fail, Таганрог в это время:(. Ну ладно, виртуально напишем.
Что за Таганрог? Время проведения пока точно не установлено — обсуждаем.
http://sites.google.com/site/contestsfedu
Таганрог = Опенкап для всех остальных.
24-го личный турнир ТТИ ЮФУ в Таганроге...
жуть какая.. всё со всем пересекается... :(
Может перенести на пятницу?
Ибо в воскресение полная жесть: опенкап, нирка, кодфорсес(2 раунд) друг за другом.
хм, а в пятницу обычный кф. Ну если ставить в пятницу, то тогда днем. Но,имхо, лучше растягивать удовольствие и решать на кф 2 дня вподряд=)
тогда может быть лучше на четверг?
есть еще вариант в субботу но позже, после Таганрога? часов в 5. Как раз нормально будет
А личный турнир Таганрога будет на КФ? И если да, то во сколько?
Просто я не думаю, что так много участников будет очно писать Таганрог.
Если мы будем проводить зеркало на CF (пока ещё не решили), то точно не в эти выходные.
А вот и телевизионщики, как всегда, в своем репертуаре: http://www.guberniatv.ru/material/9945.html
Особое внимание на момент 1:26! (да-да, соревноваться вы в нашей тренировке будете в том числе и с профессионалами своего дела)
Что ж, про всякие там биатлоны тоже сначала бред писали. Авось и наш вид спорта начнут нормально комментировать. Лет эдак через 128.
Мне больше всего понравилось название.
Похоже, им забыли рассказать, что правильная командная олимпиада — это тонна развлекухи для участников, не зря же втроем играют!)
Not a rated contest?
It's a training, not even a contest (created with Codeforces::Gyms). And yes, it'll be unrated.
Handlers of 2 testers look alike :)
I just wonder...Who is the girl in the photo of your profile? She is so cute...
His younger sister, I guess... Yours is also cute :x
Пользуясь случаем, хочу от лица команды сказать большое спасибо за хороший набор задач. Если бы не заминка с компьютером нашей команды, то вышло бы совсем замечательно)
interesting to see natalia and i_love_natalia to be tester team :D
Registration is opened.
Please note that you must read from file input.txt, not from stdin, and write to file output.txt, not to stdout.
If you use GNU C/C++ compiler, don't use
%lldto read or write 64-bit integers. Use%I64dorcin/cout.Регистрация не закрывается с началом тренировки. Вы можете принять участие, даже опоздав к началу.
Будет ли разбор задач?
P.S. Расскажите, пожалуйста, решение A, I, J.
J-бин.поиск по ответу, проверка дейкстрой
Да, была такая идея, но слишком поздно.
Там же можно и тупую дейкстру за квадрат писать?
вроде да, ну вершин 1000, видимо можно
Можно-можно. Зашло без проблем :) А не расскажете, как K решать?
Ну, например, так:
Это доказывается и является правильным решением.
А вот самое простое решение, что можно было придумать. Ясно, что в конце строка будет выглядеть как 33..3311..11 (сначала все тройки, потом все единицы). Переберем все позиции исходной строки, на которых стоит тройка. Тогда для получения ответа надо удалить все единицы левее и все тройки правее. Выбираем минимум из всех таких вариантов.
А — факторизуем k на множители до 105. Если не получилось (есть множители больше) — нет решения. При этом множители будем учитывать в тех степенях, в которых они содержатся в числе k. Наша задача — сделать перестановку с циклами длинной, равной степеням множителей. Т.е. для числа 12 надо сделать перестановку с циклами 4 и 3. Если сумма всех множителей больше 105 — снова нет ответа.
Так и делал, WA72, видно накосячил в реализации.
Я не понял про длину, равную степеням множителей. Можешь объяснить поподробнее?
UPD: int operator+ (int a, int b){return a*b;}
12 = 22 + 3 — следовательно нужна перестановка с двумя циклами: длинны 22 = 4 и 3 соответственно. Я просто написал криво %)
12 = 22 + 3 — следовательно существуют ведьмы.+=*
Спрашивали не у меня, но отвечу, вдруг пока буду писать ответ, найду ошибку в рассуждениях из-за которой у меня задача падает аж на 72м тесте.
12 = 2^2*3^1 Соответственно, наша шаффл машина будет работать для 2^2+3^1=7 карт и реализовывать два непересекающихся цикла с длинами 4 и 3, то есть ответ будет, например, "2 3 4 1 6 7 5". Первые 4 карты возвращаются на свои места каждые 4 перемешивания, вторые три карты — каждые три перемешивания, вся система возвращается в исходное положение за НОК(4, 3)=12 шагов, что и требовалось построить.
а вы смогли строго доказать, что минимальная сумма будет достигаться когда циклы будут длины степени простого? (а то у меня как-то не очень получилось)
бессмысленно брать меньшие степени, т.к. тогда нужный НОК не получится, а то, что эти множители друг на друга перемножать не надо, вроде очевидно.
вы не поняли меня, я о том, что почему не выгодно набор множителей: 2 2 2 3 3 разбить не как 2*2*2 и 3*3, а 2*2*3 и 2*3?
Цикл перестановки с циклами 2*2*3 и 2*3 равен 12, а с циклами 2*2*2 и 3*3 — 72
я понимаю, ну я имел ввиду, конечно же домножив числа на нужные простые, чтобы НОК стал равным 72
потому что во втором случае начальная ситуация повторится раньше, а именно через 2*2*3 шагов (НОК всех длин циклов)
Пусть какой-то цикл имеет непростую длинну a*b. Если мы сделаем два цикла длинны a и b (a и b — взаимно простые), то a+b<a*b (т.к.2<=a<b) и данная перестановка будет переходить в себя с периодом НОК(a,b) = a*b итераций. Поэтому выгодно разбить на простые.
ну да, видимо я просто не хотел доказать(
I — динамика на дереве. Храним для каждого поддерева 3 ответа:
1) если в корне стоит полк
2) полк не стоит в корне, но корень покрыт каким-то другим полком из сыновей
3) корень не покрыт никаким полком, но все остальное поддерево корректное
Кажется еще можно было как-то жадно решать.
Это задача I.
Да, перепутал. Исправлено
к слову, более общий случай был на одной neerc, задача Д
Я тоже так решил ее, динамикой.
Есть и другое решение. Понятно, что в листья ставить никогда не бывает выгодно. Поэтому поставим в предков листьев, и удалим их из графа.
Однако это не удается четко написать. Иногда там что-то не то удаляется и возникает какая-то фигня. Оказывается, корректно на каждом шаге удалять предка самого глубокого листа.
Можно написать вполне аккуратно. Посортим вершины по их глубине и начнем обрабатывать в порядке ее уменьшения. Заметим, что вершина на которую мы сейчас смотрим, если она не покрашена, будет яляться листом. И тогда покрасим ее предка(если он есть)
In problem K, Does the problem ask "Deleting the minimal number of digits such that the string "13" won't appear as a substring?" If so, I suggest a better problem description next time, especially for non-Russian readers like me. I really hate figuring out what to do in such kind of problems.
> Does the problem ask “Deleting the minimal number of digits such that the string ”13“ won’t appear as a substring?”
Yes, it does. It was clearly written in the output format. Many people, and non-Russians too, understood the statement and solved it — I don't know why you couldn't do the same.
Could you point out which sentence including this? I was confused at the beginning, then decided to search the problem's title on Google and got its meaning.
Well, it doesn't explicitly say it, but it says that Kostya is afraid of the page's number, and it is written on the page between 12 and 14, labeled "!#". This is what made it clear to me.
Legend:
he is afraid of this page's number
Output format:
minimal number of symbols that should be removed from the text such that Kostya's unpleasant number will not occur in it as a substring
"Kostya is sick of triskaidekaphobia , i.e. he is afraid of this page’s number." This is what I can read from English statement and I still can't recognize any "13" in it.
It's not a big deal to me, yet making the statement clearer would be better I think :)
Any PDF reader says that the page's number is 13 :)
Sorry, that was entirely my fault. However, I'm not sure if Kostya had nightmare in his dream or not, but I'm sure I had nightmare for wasting 3.5 hours just reading this problem and didn't know what to do until I looked up at the page number (only now did I know that the page number was abnormal :( )
And my Foxit PDF reader doesn't show the page number until I drag to the end of the page, which I have never done before :(. I always use my keyboard to scroll up/down or turn the page, which doesn't show the page number. Maybe next time I should prepare against Russian joke.
Hm, my Foxit Reader shows "13/14" at the bottom panel. Anyway, it is not so hard to calculate the page's number by yourself.
Вот что значит, первый раз пишу тренировку... Пришел счерез полчаса после начала — посмотрел, что все сдают В. Скачал условие, написал, минут 10 пытался сдать — оказывается, номер задачи в поле для отправки надо отмечать вручную, а не автоматически как обычно. Отправил — получил WA 1. перечитал условие — обнаружил, что это задача А О_о. Отправил, получил WA 4, исправил, сдал. Скачал задачу В — там снова задача А О_о долго тупил, пока не понял, что тут все задачи в одном файле. Дальше пошло лучше, только D проверялась минуты две. Дошел до F, понял, что умею решать её хешами, огорчился, бросил =(
А вообще задачи клёвые, спасибо, Teddy Bears & Ko за контест!
Задачи были не посорчены по сложности, если что.
Да, я понял, но почему бы не порешать подряд. А хеши просто повергают меня в депрессию после этой задачи. Встретив хеши, уже не могу ничего решать,
Ее можно и без хешей довольно просто решить (см. ниже)
Увы — я не умею бор. =(
Ну я тоже не умею бор, за исключением вот этой тупейшей конструкции, которая решает задачу F.
F же без хешей за O(N*26*10) пишется?
а как вы будете проверять наличие такой строки?
Точно, что-то не подумал.. Ну ладно, напишу бор. Обидно, что во время тренировки вообще на неё не посмотрел.
в задаче F были тесты, которые валили хэши?
Если и были, то случайно. Мы никаких подстав не делали. А кое-где даже можно было фигню запихать...
Запихал фигню с хешами. Как надо было по-нормальному решать?
У меня решение за O(n*26*10*10). Для каждой строки перебираем все варианты замены символа и ищем получившуюся строку в боре. Вроде просто пишется.
Фигней с хешами.
Длины слов до 10, полиномиальный хеш такого слова порядка 10^15, что прекрасно влезает в 64 бита. Потому там коллизий быть просто не может.
А я не поверил в это и поленился проверить на калькуляторе...
ну это еще логарифм на поиск хэша, не? и это вроде тле, так как
long longискать — это вообще бедаможно было в хэш-таблицу хэши складывать.
ну против ничего не имею (так и делал), просто я о том, что как хэши без модуля (или можно как то без модуля и хэш таблицей?)
можно для хэш таблицы и хэшей брать разные модули и в хэш таблице хэши, которые нужно положить в одну и туже ячейку ложить в список.
Судя по тому, что по E есть решения со временем работы ~980мс и ~150мс, там должен быть какой-нибудь хитрый способ избежать перебора, не подскажете какой?
у меня перебор 160мс, видимо перебор можно сократить, если для каждой задачи хранить маску — тесты, которая она не проходит, и тогда решение получится за m*2^n, а не m*n*2^n
Это n*2^n. А m*n*2^n проходили, да, если нормально написать. Плюс там вообще какая-то хрень проходила, тесты слабоваты.
да вроде все таки m*2^n — m тестов, n задач, перебираем маску и смотрим для каждой из m задач, что все хорошо
P.S. жирный текст, что-то не отображается
Для каждой задачи храним маску тестов. Перебираем биты в маске задач (их n), для тех, что на месте, or-им маску тестов. Так что n*2^n
Я пробовал каждый тест представить в виде числа, в двоичной записи которого 1 стоят на местах с номерами задач, которые он валит (возможно это и имелось в виду под хранением маски, не силен в терминах). Тогда для каждого из 2^n наборов тестов можно просто посчитать побитовое "или" для тех тестов, которые мы берем (если оно равно 2^m-1, то такой набор тестов нас устраивает). Получается n*2^n. Но на python, судя по всему, у меня не было шансов с любым перебором.
Is there an editorial of the problems that we can read somewhere for the ones we didn't solve?
We didn't write the editorial, especially in English; maybe you better ask your questions here? I think many people can answer.
And if someone writes the editorial, we will very grateful to him :)
Thanks, I just didn't want to bother everyone with too many questions. What was the intended solution for A? I know you would need cycles that would have an LCM of k, but I couldn't figure out how to factor k since it could be so large.
Usually, when you factor a number, you check all divisors up to square root of this number. In this problem you need only check divisors not greater than 105 — because if factorization of K contains prime number greater than 105, sum of numbers in factorization is surely too large.
Ahh of course, thank you! It seems so obvious now.. Any hints on L?
It is obvious that the best amount to donate is some b[i]. Lets sort a and b and precalc sums a[i]+...+a[n-1]. Then for every b[i] we find with binsearch number Ab — how many a[j] are bigger than b[i]. Let Bl be the number of b[j] less than b[i]. So the number of money we get is precalc[n — Ab]+b[i]*(n-Ab-Bl).
Why is the best amount to donate some
b[i]? I had to assume that when I solved the problem, but really didn't get that fully. Any hint? :)If p is not one of b[i], increase it by 1, and sum will not become less than before.
D'oh. You are right! Thank you all, guys!
If p ≠ bi, we can increment p by 1 and the total sum doesn't decrease.
too late :(
If not, we can always increase p until it reaches the first b[i] and this surely gives a more optimal result.
Edit: too too late :((
Let
xbe the best amount to donate. Ifxis not someb[i]lets look atx+1. We cannot get less money then we got atxbecause no interval ends atx. So we can get the same amount if there is noisuch asa[i]<=x<=b[i]and more money otherwise. Sob[i]is the best choice.too too too late =)
Obviously, optimal value of p is equal to one of bi. So let's find answer for all of them and get maximum.
Solution is sweep line. Sort all events (ends of segments) in increasing order and process them in this order. In any position X you should know two values: cnt — number of currently opened segments, and curSum — sum of ai which are greater then X. Initialization: cnt = 0, curSum = sum of all ai. In any event update this values: if this is start point:
cnt++, curSum -= X. If end point:cnt--and find answer for X — it equals tocnt*X + curSum.You can also implement the solution with 2 fenwick trees.
One of them you will know how many intervals are open at each point, and on the other how much money you get from intervals that start above that point. pretty simple to update and read.. and for the answer you just go through every data read and get the best !
ops: don't forget to compress coordenates because 10^9 is too big for memory..
Интересно, а почему в I не проходило минимальное контролирующее множество? Вроде логичное решение.
Я даже не могу найти в интернете, что это такое (в английской википедии не нашел почему-то) :(
Если это то, что требуется в задаче, то это должно проходить :) Впрочем, ты уже решил ее, можешь посмотреть тесты. Если надо большой тест, я пришлю.
Леша, стыдно.
http://acm.mipt.ru/twiki/bin/view/Algorithms/BipartiteControllingSet
Блин, как ты это нашел?! Дай мне свой гугл!
держи
Блин, я оказывается в яндексе искал :) Он только вторую ссылку дает из первых двух гугловских, как раз в которой исходник.
Контрпример — цепочка из 6 вершин.
Более простой контрпример — одна вершина.
Ожидается ли выход "2011-2012 Самарский Международный Аэрокосмический Лицей, тренировка №3" на Blu-Ray? С бонусами типа: расширенный набор тестов, разбор в формате pdf, авторские решения с комментариями, фигурка natalia в масштабе 1/6.
Да.
Уже вышло.
у меня возникли небольшие проблемы с задачей L. Может кто-нибудь помочь? Делаю бин.поиск по ответу. код (надеюсь код видно)
Функция не монотонна, бинпоиск некорректен.
Точнее сказать она не строго монотонна.
Что значит не строго монотонна?
Это значит, что бывают приращения равные нулю.
Да нет, она вообще не монотонна. Хотя бы во втором семпле: [5,10] и [20,25].
При p = 9, 10, 11 прибыли равны соответственно 29, 30 и 20.
да забыл условие, думал он будет платить y, если цена превышает y. upd, тогда задача в фигню какую то превращается)
Бинпоиск здесь не корректен. Указание к решению : попробуйте выделить только те цены, которые могут быть ответом, их будет O(N), и придумайте как можно эффективно вычислять f(p,n) используя предыдущие значения этой функции.