Здравствуйте, друзья)
Рады приветствовать вас на очередном раунде Codeforces #123 для участников Div. 2. Традиционно, остальные могут поучаствовать в нем вне конкурса.
Задачи для вас были подготовлены группой авторов в составе: Иван Фефер (Fefer_Ivan), Игорь Кудряшов (Igor_Kudryashov), Павел Холкин (HolkinPV), а также Геральд Агапов (Gerald). Также говорим спасибо Кунявскому Павлу (PavelKunyavskiy) и Александру Куприну (Alex_KPR) за помощь в подготовке раунда. Традиционно хотим поблагодарить Михаила Мирзаянова (MikeMirzayanov) за систему Codeforces и Марию Белову (Delinur) за перевод условий.
Распределение баллов по задачам стандартное: 500, 1000, 1500, 2000, 2500.
Всем участникам желаем успехов и высокого рейтинга!
UPD: контест завершен, разбор задач появился здесь
Поздравляем победителей:
эх, время-то неудачное для раунда :(
Для тех, у кого положительная разница с Москвой, время с Вашей точки зрения всегда "неудачное". У меня обычные-то контесты начинаются в 21-00, а ведь кто-то живут во Владивостоке и при этом пишут КФ, и ничего.
Наверное имелось в виду что в 20.00 мск будет матч Испания — Италия на Евро, и многие предпочтут посмотреть его, а не написать контест =)
Именно!
А следующий, 124-ый раунд вроде бы в правильное время)
Судя по всему, футбольных фанатов на КФ намного больше, чем настоящих спортивных программистов :).
Почему настоящий спортивный программист не может быть футбольным фанатом? См. комментарий :)
Лучше качаться, пока Гена болеет
Поражен этим комментарием. По-вашему, настоящие спортивные программисты только и делают, что
задрятботают весь день?!ДА
черт.
А я поражен Вашим беспричинным грубым наездом на меня. Проясню смысл своего высказывания: я Ваш намек не сразу понял (т.к. сам футбольным болельщиком не являюсь и смотрю даже чемпионат Европы эпизодически), и поэтому написал то, что написал. А сравнение количества "настоящих спортивных программистов" с количеством "футбольных болельщиков" я сделал из-за неадекватно агрессивного заминусовывания моего поста.
понятно, я думал, что намек всем будет очевиден) извините, что грубо получилось.
А что мешает писать контест и смотреть матч одновременно?
Ну тут либо задачу завалишь, либо гол не увидишь!
ура, 124й раунд в 17-00!
I am students.
gl & hf
Исправьте ошибку в слове "жела**ни**ем". UPD: Исправлено
Рассылка о раунде почему-то у меня в списке спама (почта gmail).
Good luck to all. :-)
Ну вот : как голы пошли — сразу решать надоело...
Что ломали в А?
Меня сломали на бинпоиске. Недостаточное r поставил.
Бинпоиск в А (div 2), таяние льдов и прочие признаки апокалипсиса...
Что плохого в бинпоиске в А?
То, что перебор заходит. Да и за константу полно решений.
Только бинпоиск, только хардкор!
Ну, лень мне было думать. Бинпоиск по ответу как раз для таких случаев. К тому же, вопрос был про взломы.
Почему в С первый пример не "AE in line 5"?
Потому что throw не находится внутри данного блока try catch.
Блок с throw не лежит в последнем блоке.
I hate problem C.......
I hate string parsing. Problem C is just colateral damage :)
Seen at the last moment that the string can have '\t' in, and no time for correct it... Those kind of problem is not bad, because it teachs you to prevent all possible cases, but it's often very frustrating...
really frustrating... i used regular expression. i knew little about it before
I used %[\n )] in scanf to match the keyword. Forget \t should be my error :(
%*[^A-Za-z]%[A-Za-z]%*[^"]"%[^"]%*[^\n]\n
Test does not contain '\t' symbols as I know. Only ' '.
Классный контест. Очень понравились задачи, но ИМХО С была сложнее Д.
Надеюсь, вы не правы, и Дшки попадают.
Футбол? Не, не слышал.
Раунд получился великолепный! Авторам респект и конечно будем еще ждать от них подобного!
Благодарю.
Посмотрел несколько решений по D, почти все без double'ов. Интересно, мои пляски с double'ами и эпсилоном
1e-12пройдут?)Казалось бы можно добиться отличия в 10 - 18. Я вроде говорил Gerald проверить есть ли такие тесты. Не знаю чем закончилось.
судя по всему, есть
Видимо, есть. Упала.
У меня зашло вообще без eps. Даже сравнения.
Послала без eps. Испугалась. Перепослала с eps, из-за которого решение и упало ><
Если сделать
gcd(чтоб равные оказывались равными безо всяких эпсилонов) и далее тупо пихать вset<long double>— вроде бы, в случаеg++, от погрешностей не падает. По крайней мере, не падает на дробях вида i/(i+1) и (i-1)/i, а они вроде как худший случай.Если кто-то умеет такое валить — прошу научить.
раунд мне вообще не понравился:
С — какая-то задро реализация
D — >> Нетрудно показать, что в этом случае график s(x) является ломаной
ну так возьмите и покажите, хотя бы в одном примере для разъяснения
E — хрен поймешь условие, черт голову сломит...Раунд я, как всегда, не писал, но он мне всё равно не понравился.
Классный раунд, отличные задачи, вполне нормальное условие в E, а в D вполне очевидно, что s(x) ломаная, причем, несложно заметить и какие точки будут ее вершинами, что дает решение.
Доказать, что s(x) — ломаная я не смогу, но решение найти легко и правда.
Насчет D соглашусь. Чего-то явно там нехватало.
В E в условии написано дан DSU посчитайте то, что вас попросили. Термины вроде тоже стандартные. Только операция какая-то странная.
В D. Сумма кусочно-линейных, кусочно-линейная, кэп вам поможет.
С. Решение. 40 строк кода если убрать шаблон. Это с кучей
assert, и моим достаточно вертикально-вытянутым стилем написания. Обычный простой парсинг строк. sscanf как всегда всех спасает.E — да прям уж так и написано, ага.D — да я не прошу мне что-то объяснять, я говорю о том, что рисунок в этой задаче был бы не лишним, по крайней мере в этой и этой задаче, он нафиг не нужен, но он там есть, в этой задаче он помог бы разобраться с примерами — фигушки, а не рисунок
это не отменяет ее задротную реализацию, лучше бы дали бы какую-нибудь идейную задачу
Ну Е и D были чисто идейными.
Е — по мне так, если знать что такое DSU, то да.
D — Это все таки тоже часть задачи, понять как это устроено. Пояснение на сэмплах действительно было бы уместно наверное. Тем более тут практикуют очень подробное их описание.
С. у меня в упор не состыкуется прилагательное "задротную" и менее 150 строк. Причем не сильно насыщенных. То что это техника, и не совсем элементарная, если не подумать как писать, это да. Я знаю человека, который про все 5 задач сказал бы что это техники. Писать надо уметь и то и то. Тем более что Div-2 контесты еще и обучающие.
ну с Е я прямо скажем погорячился
у вас было много времени на обдумывание и оптимальное, красивое написание С, поэтому так коротко. у всех же участников строк по 100 кода. проблема таких задач в том, что они убивают время на их написание, а потом еще и поиск ошибки. мне никогда не нравились такие задачи, где нужно шезофренически учесть все случаи
и еще >>Я знаю человека, который про все 5 задач сказал бы что это техники
так и хочется добавить "и это я" ))
D. Сумма непрерывных функций есть непрерывная функция. А тут ещё и кусочно-линейная. Понятно, что ломаная.
Вот честное слово, условие перерабатывали много раз. Разобрали сэмпл по шагам. Написали все формально и четко. Мы правда очень старались, чтобы было предельно понятно.
Что именно вам кажется плохо сформулированным?
хм, перечитал, на самом деле все ок, видимо я был под веществами
Хотите знать, что такое действительно плохие условия? Завтра тренировка тут намечена, думаю, после ее прорешивания любые другие условия будут казаться идеально понятными.
у вас есть 12 часов, чтобы исправить это досадное упущение
Нет! Наша команда играла этот контест, и я не позволю, чтобы кто-то получил преимущество над нашим призраком!
Я их пишу. dalex их играет.
А что вы делаете в контестами?
Сливаю.
Блин, сначала не разобрал сообщение.
Я их еще иногда делаю)
я их решаю)
а кто-нибудь будет отвечать на сообщения во время контеста?
Автор текстов обещал быть на связи. Я тоже буду, но некоторые задачи я так и не распарсил :)
у меня 45 строчек кода без супер идеи в реализации. Просто в лоб. (на Java)
О, в матче сейчас опасный штрафной будет.
а как решать Е?
В условии задачи тебе дан снм. Ну он работает за логарифм и только со сжатием путей.
А, клево, то есть можно, сжимая путь, поддерживать длину пути до корня? Эх, что-то я не додумался =(
Просто при переподвешивании меняем длину ребра на сумму. Тогда расстояние не меняется.
Я уже пишу разбор. Дайте мне 5 минут )
я решал с помощью DSU с поддержкой расстояния до корня
Я не придумал как в снм операцию прилепить, сделал так:
найдем предков и явно построим дерево, теперь можно ко всем вершинам поддерева (у нас это величина пути к корню) добавлять все что нам нужно за лог(Н), например, деревом Фенвика.
Код:1778738
Надо мне меньше думать.
Я не понял почему в С не сказано двойные или одинарные кавычки ? Я обрабатывал только двойные. В итоге ACC. Интересно. Если бы взламывали на этом, что бы было ?
В самплах видно, что кавычки двойные.
Самплы не всегда хранят в себе все условие задачи.
Из этого не следует, что не бывает одинарных. Меня удивляет, почему находятся люди, которые спросят, "а дайте пожалуйста 6 тест", но такие вещи никто не спрашивает.
Жаль, что по задаче С, несмотря на "Это означает, что во входных данных могут встречаться пустые строки или строки, состоящие только из пробелов.", выдается "Некорректный тест", если в попытке взлома есть строка состоящая из одного или нескольких пробелов.
Это выдается не всегда, быть только пару инцидентов. Это баг системы, а не валидатора. Мы повторно перетестировали подобные взломы.
А можете глянуть мои взломы: 41753 и 41755.
Сейчас там "Некорректный тест", и через систему вопросов я получил ответ "К сожалению, взломы с такими данными на данный момент системой не поддерживаются."
я их перетестировал, у вас не хватает последнего перевода строки.
Написанно же
FAIL Expected EOLN (stdin). У вас не хватало перевода строки в конце файла скорее всего.Жаль, что сообщения "FAIL Expected EOLN (stdin)" не было во время раунда, а только "FAIL Input can't contain line starting with space, but line 5 (1-based)..."
Хм. Странно. Такое казалось бы могло произойти, если не убрать где-то галочку "Tests are well-formed". Но тогда бы он не провалидировал претесты даже.
у меня был такой же вердикт, взлом 41720
Мы убрали эту галку. У нас самплы были не well-formed. Есть мнение, что это баг и его исправят.
I spent about 30 min and 3 wrong answers on problem B ... because I thought (m + 1) / 2 is integer division not normal division ...
Will n log n time out in problem D? Mine nlog n timed out. Is there any o(n)?
nevermind
It was nlog n for sorting and then o(n) for counting non zero diff slopes.
Yes, they was o(n), you should find all X where line intersect OX axis, number of unique point — it's a answer)
Problem B. You should mention that if m is 6, for example, (m + 1) / 2 equals 3 or 3.5.
3.5
children in first grade are told what symbols '/' means
It's ambiguous as to programming languages.
the problem statement was in English language, not a programming one
Couldn't you ask it?
Problems are written in English language, not C++ : )
Usually,
. But 
.
Well. I see. Thx ;)
It doesn't really matter because even if you use integer division, you still take the basket with the lower number in case of a tie.
Counterexample:
Oops. You're right. Anyway, I used integer division, so I guess that was the intended meaning. Is there any other explanation why it worked? I can't find any.
You may have interpreted it as integer division, but your code skips the issue entirely by multiplying out both sides:
abs((M + 1) - 2 * a.second)Oh yeah, I totally forgot. At first, I wrote it abs((M + 1) / 2 — a.second) and then changed it. I had a bug, but then I realized that it was something else. It turns out that I was pretty lucky because I just tried it with the division and it fails "2 6". So we have our answer :)
А когда рейтинги обновят?
Спасибо ,друзья, за замечательнейший контест, мне он очень понравился!!! Создавайте контесты еще)))
Что за дела с рейтингом?...Даже 1-ое место (bmerry) не прошел в див.1, хотя до этого не участвовал ни разу.
Вообще 31 перешедший в Div1 участник это как-то мало. Что-то MikeMirzayanov странное с рейтингом сделал. Хотя бы показали формулы бы.
По скорее нужно удалить c.cpp пока комп не сломался :)
А что этот файл у вас такого делает, что комп может сломаться?
In problem C I used Scanner and it not even passed the first test case..Then I used BufferedReader and it got accepted..Could anyone explain why?? Scanner BufferedReader
I could be wrong, but you should use nextLine() for entire lines.
But I changed the Delimiter to
"\n"..So it is the same I guess..nextLine() reads characters until the end of a line, so after reading the first integer in the first line, you should put an extra nextLine(). Then a "carret" will be moved to the next line and you can read an input as expected. Otherwise the last line will be skipped. Here is the corrected solution that passes: 1781961
Can u please make it more clear for a dumb head like me.. I made a similar mistake on 1 more problem and I want to rectify it now ..plz..
Problem E,I can't understand "angle"...what is that?
It means parallel to the X axis ?
Angles are places where polyline has fracture.
But the fracture maybe discontinuous?
Oh! I get it,It must be continuous,thank you very much~~
In problem C:The program may have spaces at the beginning of a line, at the end of a line, before and after a bracket, a comma or a quote mark. But I got stuck in cin.getline(s,55,'\n'). I don't know why it reads more lines than you data gives.
The second
t.cha[len] = '\0';should bet.msg[len] = '\0';Oh, and maybe you should consider putting acin.getline(s,55,'\n');instead ofgetchar()after reading n too just to be safe.For problem A, I was looking at bmerry's solution but I don't understand why the formula he used is:
down_time = (c*a + b - 1) / bA lot of solutions I studied use this formula or some variation. I was trying to solve the problem using some kind of simulation but was unable to, but everybody's I've looked at uses some kind of formula.
The other thing he does is subtract c from downTime, and the answer is max of 0 or that difference.
Can someone explain how to come up with this formula? Thank you.
I simulated problem A. You can take a look at my code here
brute force solution here
What I'll tell is effectively the same solution.
If b ≥ a, then we can wait 0 seconds and still there will be no delays in the streaming.
Suppose that b < a. Consider the moment when the streaming has finished. By problem statement we must have (t + c)b ≥ ca (the amount of data received in t + c seconds is not less that the amount of data in c seconds of the video).
Lemma: If (t + c)b = tb + cb ≥ ca, then also for any 0 ≤ t0 < c it holds that tb + t0b ≥ t0a (the amount of data received in t + t0 seconds is enough to play t0 seconds of the video).
Proof:
because $0 \geq t_{0} < c$ and b < a.
Consequently, we only need to find such t that tb + cb ≥ ca is true, and the rest will follow. The smallest integer t that satisfies this inequality is
Finally, for integer division that is equal to
You can also take $c$ out of the numerator, which gives you bmerry's
Will there be an editorial ?