Всем привет!
Сегодня, 30 июля в 19:30 MSK состоится Codeforces Round #131, автором которого являюсь я(Сергей Нагин). Это мой первый раунд на Codeforces и надеюсь, что не последний.
Спасибо Фурко Роману(Furko) и Геральду Агапову(Gerald) за помощь в подготовке задач, а Марии Беловой(Delinur) за перевод условий. Также выражаю благодарность создателю Codeforces Михаилу Мирзаянову (MikeMirzayanov) за прекрасную систему.
Удачи на раунде!
Разбалловка в первом дивизионе: 1000-1000-1500-2000-2500. Разбалловка во втором дивизионе: 500-1000-2000-2000-2500. Настоятельно рекомендую прочитать условия ВСЕХ задач.
Контест завершен! Поздравляю победителей!
1й дивизион:
1 место: Egor
2 место: Petr
3 место: tourist
2й дивизион:
1 место: antimatter
2 место: c175353
3 место: takaramono
Надеюсь, задачи вам понравились.
Немного личной информации.
В этом году я закончил школу и буду поступать в университет. Программированием занимаюсь почти 5 лет (с 7го класса). Помимо информатики, любительски увлекаюсь спортом: пауэрлифтинг, армрестлинг и плаванье.
Раунды от школьников всегда интересные!
so, we are gonna have some sports flavored problems!!
And everyone is in the olympics mood too!!
А какое будет распределение балов стандартное или динамическое ?
скорее всего стандартное(из слов Sereja).
Хотелось бы услышать точный вариант от автора здесь.
will the scoring be as usually or dynamic ?
Dynamic scoring is nearer and nearer to become 'usual & default' :)
UPD: not this time :D
Well usually when the contest only for DIV 2, it's using dynamic, and for both Division they usually use normal scorring IMO
I disagree..If you browse thorough the contests after Round #113(after dynamic scoring was introduced) you will find that apart from rounds #115 and #126 and all rounds from the trio NALP- Gerald-HolkinPV (which have dynamic scoring systems) ,,the scoring system has been traditional in other rounds. So I think they leave it on the authors to decide ..
Good Luck And Have Fun! :)
hacked by hackers
What said bad(he has -4)?
Don't try to understand negative votes on codeforces.
if comments have negative votes it is bad but lashabuxo-s comment i think is not bad.
If comment have negative votes — then somebody thinks it is bad.
Спасибо автору за возможность посоревноваться, с нетерпением жду начала раунда
Джигурда?
или сразу Литвинков
Или сразу Петросян (судя по проф.ориентации фразы "А я Никита")
Он Никита , у него 2 папы...
UPD Я угадал:)
:D
How to run my program at local machine? Above is quickly enough?
g++ xx -o exe
exe < in.txtg++ code.cpp -O2 -o exe
g++ name.cpp && a.exe <in.txt ( in windows )
g++ name.cpp && ./a.out <in ( in linux )
Что с разбалловкой в div2?
Почему в задаче В написано что запрещено использовать лидирующие нули, хотя в первом семпле ответ с нулем в начале?И еще написано что можно использовать не все цифры из набора, следовательно для третего семпла есть ответ, убрав одну двойку!
Нужно, чтобы одновременно делилось на все 3 числа, читайте внимательно условие
Связь с жюри в помощь
что там за 11 тест в б
Контест кончился, теперь скажите какой 11 тест.
Сори, не та задача
UPD опечатка уничтожена.
Мне же не одному кажется, что это был ужасный гробовой контест?
Либо я тупой и у меня сейчас все попадает, либо первые 4 задачи ну совсем простые
Ну.. Я же не о вас, уважаемые гроссмейстеры, а о простых смертных =)
Просто не было очевидных реализаций.
Это ты о задаче D ? :)
У меня вот как раз сложилось впечатление, что это я идиот, а задачи вполне решабельные)
D самая простая.
Забавный раунд, давно я B не оставлял. Хочется посмотреть, что же там.
Задача D порадовала. Интересно, это авторское: поставить пятиугольники рядом и начать с проведения длинной прямой линии?
В В, казалось бы, перебираем первую цифру, а дальше рюкзак для каждой цифры. Итого 10^2 * n^2
Честно говоря не понятно, хотя я может и торможу
Надеюсь, с кодом понятнее
Авторы, спасибо за отличные задачи! Попробовал все и не пожалел.
Почему в С настолько маленький МЛ?
Потому что можно за O(N^2) памяти сделать.
Красота :(. Ну что же, в очередной раз получаю по халявной задаче плохой вердикт.
Гораздо печальнее то, что не хватает по-видимому совсем немного. По подсчетам вполне должно укладываться, возможно на С++ так и будет.
Лично мне не хватает очень даже много (я потом послал в "Запуск", и ТАМ получил МЛЕ — превысил 512МБ). В следующий раз буду думать, прежде чем писать всякую такую бодягу с гигантскими массивами.
Ну суть проблемы в том что есть множество прошедших решений на С++ с трехмерными массивами, поскольку там они занимают памяти столько, сколько должны, в отличие от Java, где хранится побочная информация.
Very interesting B question in Div-2..It made me so involved that I did'nt have the time to read C,D,E..But I am happy I managed to pass th pretest finally after 11 WA..
Some test example from Hacker.
Input:
3
0 0 0
Output:
000
Answer:
0
Надеюсь, у меня в B какая-нибудь страшная математическая ошибка, а не дурацкая опечатка, которую я не нашёл за последние полчаса о_О Вот же обидно будет =Ъ
Спасибо за интереснейший контест! Наконец-то контест без очевидных реализационных задач
В D случаем не нужно разбить наш прямоугольник на пятиугольники, провести ребра (диагонали) и найти эйлеров цикл?
Можно куда проще, напишу в разборе.
Действительно D вышла простоватая, было бы круче, если "прямой цепочкой" размещать не влазило бы, решения были бы немного сложнее, а рисунки красивее.
Остальными задачами очень доволен.
Свинство все-таки получилось с задачей D, по поводу того, что требовалось выводить хотя бы 9 знаков после точки.
1) " с точностью не менее 9 и не более 100 знаков после десятичной точки." Если бы не было слова "точностью", то эта фраза бы означала то, что задумывали авторы. А так, как мне кажется, написано "с абсолютной погрешностью не более 10^{-9}". Непонятно правда, что значит не более 100 в такой интерпретации.
2) Мне кажется в целом тупо давать WA (ладно бы еще PE) за то, что число выведено абсолютно точно (0.0), но не " с точностью не менее 9 и не более 100 знаков после десятичной точки."
3) В целом вроде как на нормальных контестах всегда можно вещественные числа выводить как угодно, и проверяется отклонение от правильного ответа того, что выведено.
Жду комментариев "сам себе злобный буратино" :)
Создатель сайта не сторонник РЕ. пункт 3
Я в курсе, это был как раз камень в его огород :)
Все чудесатее и чудесатее: оказывается, целые числа можно было выводить, а вещественные но с 1 знаком после точки нет? Хотелось бы официальных разъяснений на эту тему :)
Кстати, из математического формализма следует, что чекер работает идеально правильно. Если десятичной точки нет, то утверждение "не менее 9 и не более 100 знаков после десятичной точки" выполняется, так как содержит неверную предпосылку "десятичная точка есть".
Действительно, [все] вещественные корни уравнения x^2+1=0 участвовали в этом контесте.
А больше 100 знаков после десятичной точки правда нельзя? :)
Долго пытался сейчас понять, как вообще интерпритировать слова "точность не менее 9 знаков". Пока самое разумное — с верными первыми 9 знаками. Жалко, что это означает не абсолютную погрешность 10^{-9}, а нечто необъяснимое — ответ (1-eps) неверен при правильном ответе 1.
На чем ломали В (Div 2)?
На выводе лидирующих нулей и неправильном разборе случаев.
3 1 0 0 или 2 0 0
3 1 0 0
У меня не проходило типа:
7 4 2 1 1 5 0
Выводил 75210, но так и не придумал как исправить.
how can This Submission Pass the preetest but got compile error while Systest ?
Compilation Error на 10-м тесте facepalm
How is that even possible?
The discription of the problem is quite clear.
Мое решение (1959817) получило "Ошибка компиляции" на тестах, однако сразу же после тестирования, на дорешивании оно же (1960480) прошло все тесты.. просьба разобраться.
Great contest, thanks to all of you.
It seems java needs more space than C++. In div1-C I initialize a 3-D array and get MLE.
I did not look at your code but it may be the case of how you declared the array.
Arrays are objects in Java, so a[1000][1000][2] creates one million objects and a[2][1000][1000] creates only 2000. There is an overhead for each object.
If space is an issue, use a 1D array instead.
Печалька((( у компилятора на сайте vector :: erase не работает((( Из-за него ВА получал на 2 тесте. Не подозревал что такая ошибка будет
Эм, может пример покажете? Ссылки на отправки, все такое.
Возможно очередная бага g++.
Простейшие примеры в запуске работают
Советую создать минимальный пример, который демонстрировал бы неправильное поведение
vector<>::erase. С очень высокой вероятностью окажется, что баг не вerase, а в самой программе.1956309 вот номер посылки. На компе моем (mingw) выводит как в сэмпле. (3 четверки посередине), а здесь — 4. (через запуск тоже самое((()
Переменная
sumне инициализирована. Чтобы получить предупреждение об этом, надо компилировать хотя бы с параметрами-Wall -O2.In the contest, I got many wrong answer on pretest 1 of problem D,.. After the contest, I found out the mistake, only one mistake: 10.0 => 1.0. And I got AC after fixing it... So sad!! :(
For div2 B, can someone confirm test 13 is the same with test 14, i.e. the input is ten thousand 0s? My solution passed 13 but failed on 14, quite weird.
your solution didn't pass test 13. you got wrong answer on test 13.
The solution I meant is below, not the one during the contest.
test 13 and 14 are not identical. I suppose there is a difference between them and since we can't see the whole test case we can't see the difference.
The wrong solution is here. Please give me some hints.
Input can be like this
(100000) zero for test 13
(99999) zero + 1 for test 14
both of them have same answer but, because is too long, it will cut.
input 5 0 0 0 0 5 what answer?
0
Thanks you guys who replied. I find the bug and get it fixed. This is the correct solution. It turns out case 13 and 14 are indeed different.
very nice problem set!
The problemsets are nice, thank you, Sereja.
Problem B was very confusing.. as in the problem statement, it was written: Each digit is allowed to occur in the number the same number of times it occurs in the set.
Then how the ans for second test case is: 5554443330 since in input set 4 is occurring 4 times but in output integer it is occurring 3 times only.
It is permitted to use not all digits from the set
They said: " It is permitted to use not all digits from the set"
I took it as.. if i am not taking any digit then i am not supposed to use that digit in the output at all. Means that digit's count would be made 0. I tried other way also, but because of a very silly mistake my solution got hacked.
May be you missed this -> '**It is permitted to use not all digits from the set**'
I Think It Would be better to increase Contest Time for some contests like this To let People have more Fun !
The comment is hidden because of too negative feedback, click here to view it
It's interesting to see how many downvotes that comment will get, because it'll mean that some people actually care about comments that downvoted a lot.
One of the advantages of being Petr is that you can make such troll-jokes without throwing your reputation towards S = {x : x < 0} where x belongs to R.
When I try to click "here" the page scrolls to the top and the comment doesn't show up.
I don't get how you don't get it. And I'm the "blue" one here.
Does the intended solution for div1 E use hashes? I saw only hash solutions and wonder if they can be hacked using ideas from recent anti-hash articles.
I think that this is the reason why people submited this problem in last minutes of the competition — not to be hacked...
I'm quite sure it can be solved with something similar to KMP.
Assume we can, after preprocessing, quickly compute functions prev(k, i) and next(k, i) for a permutation P, which give the first element j in [i, k — 1] preceding / succeeding k in P.
Let suf[k] be the minimum j > 1 such that the part of A composed of elements [j, k] is (EDIT) the same permutation as the part of A composed of elements [1, k — j + 1]. We can compute suf[] using a linear number of calls to prev() and next() on A.
Later we can use suf[] like a KMP table to compute all shifts that match with a linear number of calls to prev() and next() on A and B. :)
How can I know number of 1's in testcase number 12 in div2 problem B ?
There is no way to do this.
But... You can count them, and guess counter by binary search. (For example, if cnt < 4000 then cause TLE, otherwise get WA)
I found a better way compared to this. print out number of 1's for this particular case . number of 1's are 49898 . :D
anyway thanks for your help.
Когда рейтинг обновят?
One Does Not Simply
Update the rating quickly
i am new on codeforces.com and how add friend???
hacked by hackers
lashabuxo tell me why you made multiple accounts? http://mirror.codeforces.com/blog/entry/4924#comment-100414
i believe it's a way to get upvotes on his comments
Is there any rational reason to do this? :P
don't ask me :)
open someone's page and click the star on the right of the name
tourist lost his Codeforces Red Target :(
When will the editorials be available for this contest's problemset? Thanks in advance
As soon as it gets posted.
Задачи клевые автору спасибо
Кому не трудно не могли бы сказать как в Задаче Е (див. 2) в этом тесте получилось 508?
первый идет по пути 4-47-47-26-39-33-7-26-47 второй по пути 47-36-23-40-39-23-38-32-4
Wrong answer on test 65 on problem B, div 2. Don't you know what it is?
div 2,problem B: your submissions status and test 65:
Да, как показала практика, у меня проходило и без ресабмита
when the Problem's Analysis will be placed ?
Пинг. Sereja/Gerald/MikeMirzayanov: не объясните официальную позицию по поводу цифр после запятой в задаче D (см. мои комментарии выше в этом треде)? Она существенно повлияла на мой контест.
Я лишь напомню прецедент с прошлого контеста, что неверное условие задачи в течение всего контеста — основание в лучшем случае отменить минус к рейтингу для участников, которые эту задачу посабмитили.
Рекомендую писать в личку или на почту MikeMirzayanov (если вы знаете его e-mail ;) ).
Ну дело не в том, чтобы отменить плюс/минус к рейтингу, а скорее в том, стоит ли и дальше ждать на Codeforces подобных наколок, или все же это была ошибка и будут приняты усилия больше так не делать.
Насколько я помню, из последних контестов проблемы были примерно в половине. О сделанных выводах — вопрос.
Добрый день.
Когда Вы после нескольких попыток по первому семплу задали нам вопрос, мы указали Вам на вашу ошибку. На мой взгляд, в этой ситуации (в сумме с вышесказанным) мы поступили совершенно честно по отношению к Вам.
Что касается менее формальных рассуждений, конечно же, впредь такие моменты в условиях будут выделяться болдом, да и вообще, при возможности избегаться (почему в этой задаче от такого вывода нельзя уйти, я объяснил ниже). Понятно, что такой вывод не является стандартным.
По поводу того, зачем так было сделано. Задача достаточно специфичная, чекер в ней не стандартный, а в условии, в 2х строчках не объяснишь как конкретно он работает (сохраняя при этом всю формальность). Здесь очень сложно отличить точные решения от неточных, чтобы формально все было честно.
Привет,
со мной можно на "ты", я еще не старый! :)
Спасибо за объяснения. К сожалению, не совсем их понял.
Почему пропускание целых чисел формально правильно? Они же с 0 знаками после точки?
Про чекер: фраза "Обратите внимание, что правильность ответа проверяется не абсолютно точно. Постарайтесь получить как можно более точное решение. Все вычисления в проверяющей программе выполняются в предположении, что абсолютная погрешность ответа участника не более 10 - 8." как раз по-моему отлично объясняет (в той мере, в какой это можно объяснить в 2 строчках), как работает чекер. А как этому помогает запрет выводить мало цифр после запятой?
И еще — можно ли было выводить числа в экспоненциальной форме?
Я предлагаю не обсуждать это здесь. А поговорить лично, например в GTalk. Насколько я понимаю, проблемы с точностью коснулись только тебя.
My first submit was on 1:42, and last one (change cout for printf and replace "0 0" with "0.000000000000000 0.0000000000000000") on 1:59. So it's not only Petr.
P.S. Sorry for english, but my written russian is horrible.
Судя по количеству плюсиков, вопрос "почему 0.0 нельзя писать, а 0 можно" много кому интересен. Мне, например. (Мне как раз случайно повезло написать "0", но в чем разница все равно хотелось бы знать.)
Извиняюсь, какой-то я очень негативный сегодня.
Спасибо огромное, что указали мне на ошибку! И вообще спасибо за контест, в остальном все было круто.
Я правда хочу понять, чем это ограничение помогало чекеру :) Может быть, имелось в виду, что число "0.0" означает "0.0+-0.05", как иногда учат в школе про вычисления с приближенными числами?
Although I liked the problems, I think problem C was a bit of a fiasco. On one hand the exact same problem has been given before in TopCoder, SPOJ, one Bulgarian competition (okay, no way to know that) and God knows where else. Thus many people had the chance to solve it in several minutes (I for one needed 9 minutes, and other people even less). Anyway, this happens (I know from bitter experience).
I also was happy to see the negative numbers (which means negative results are possible). This is another TopCoder trick I've felt for before — if you use memoization and you initialize your array with -1 (which is valid number in this case) you have a correct, but possibly too slow solution. For those of you who don't know it — if the answer to the problem is -1, then some of the states will be calculated over and over again and it can turn really slow. So I was looking for such solutions in my room, however most were using standard iterative dp (which is okay with that) and didn't have the chance to challenge anyone.
However, such a test was not present in the system tests, so some (possibly plenty) of wrong solutions passed.
The test is rather simple to create:
But, is there a way to use a smaller state (not 598x300x300) so that you don't get memory limit exceeded? Because if that can't be done then I guess that could justify the absence of such cases
Yes, sure. See my solution, it uses twice smaller state (if I initialize my dyn[][][] array with -INF instead of using additional array).
When I click the tutorial link, I can see a tutorial, but not in English. Why? The English tutorial has been released, I think.
You may change '.ru' to '.com' in link. http://mirror.codeforces.com/blog/entry/4982
Hello! I don't know where to post my problem so i'll post it here. I apologize if posting this here is wrong.
Well i have tried the problem Numbers(D div2, B div1) and i finally solved it. The source code is here http://mirror.codeforces.com/contest/214/submission/1974583
I get WA on test 10 (100 0 0 0 0 0 0 0 0 0 0). The strange thing is that when i run the code it prints the right answer on my computer. Here when i submit it, the answer on the same test is different and i don't get it why it does that.
Please help me to see what is wrong :(
In your code,
lencan be 0, so inComb[len - 1][j]index goes -1 and so you get weird numbers from uninitialized memory, instead of expected 0 value.Thank you very much :) I finally got AC. I guess i missed that -1 index.