Здравствуй, сообщество Codeforces!
Очередной раунд Codeforces #121 для вас сделали студенты ФИВТ МФТИ Александр Тимин (AlTimin) и Иван Смирнов (ifsmirnov). В своем первом раунде мы предложим вам хорошо провести время в старой доброй Берляндии: провести митинг, разогнать митинг, разобраться с главными берляндскими проблемами (обеими!) и многое другое.
За неоценимую помощь в подготовке контеста хочется сказать огромное спасибо Gerald. Он же является автором одной из задач. Кроме того, мы выражаем благодарность Delinur за перевод условий на английский язык, Aksenov239 за вычитку условий и MikeMirzayanov за возможность провести контест на замечательной платформе Codeforces.
Традиционно, раунд пройдет в обоих дивизионах на частично пересекающемся наборе задач. Информация о разбалловке будет опубликована позже.
Мы желаем вам успехов и надеемся, что раунд вам понравится!
UPD1: Разбалловка в обоих дивизионах стандартная, 500-1000-1500-2000-2500.
UPD2: Авторы контеста приносят участникам свои извинения за неточности в условии задачи B div 1 (D div 2). Так как проблема с условием была решена достаточно быстро, а неправильное понимание задачи не проходило претесты, раунд объявляется рейтинговым.
ifsmirnov, даешь гробовую геометрию!
И ведь даст ведь!
^3^я так понимаю аля AlTimin, аля продолжение задачи с заочки
Тсс...
Заблаговременно. Надеюсь, с разбором тоже никаких проблем не возникнет :)
Ваня, Саша, а как же сессия?)
До экзамена еще так-то два дня)
There is a bug in the registrations, I was able to register in both divisions.
Edit: Looks like anyone can register in both divisions.
Yes, you can. But you'll be rated only in the division you belong to.
sad
I think it is fixed now.
Давно ждал контеста от Саши. Теперь хоть что-то политическое, кроме моего заминусованного поста :)
is the problems sorted? what is the scorig system? dynamic or normal?
The scoring system is classic.
will the problems be sorted by thier complexities?
No, they will be sorted in lexicographical order...
I suppose it's better if you answer questions instead of laughing at it.
I'm sorry, but I think there is no need to change standart order of problems to some random. Also, there is no point to ask about order each new contest.
The scoring system is classic, as has said ifsmirnov: so we will know at the beginning whose problem is for 500/1000/1500...points. You don't need to know how will be sorted the problems in this case, and there isn't any reason for the problemsetters to put the problems randomly.
tnx. I got it when I noticed the scores in the post but forgot to update my comment. Thanks again.
I think contest will be normal, because when contest is dynamic they always write this.
А будет задача про ДП и задержания? =)
К сожалению, она не вошла в окончательную версию контеста.
А завтра егэ по информатике..))
Сдалось оно вам...Сдался он вам...
Пиши div2 A — тренируйся перед завтрашним C4 :)
In problem "A" I print "Yes" and "No",but I must print "YES" and "NO",and my solution is accepted. Is it ok?
Perhaps register doesn't matter. Or it's a bag.
I suppose that checker is not very strict, so
Yeswill be ok.But it is better to fit the format.
It can be checked if ans[0] == 'Y' then your solution should be accepted.
But then some challenges based on this inaccurate behavior may fail.
Challanger knows that solution passed pretests (including samples)
The solution passed pretests, so one shouldn't try these cases. However, it should be written in the problem on output format.
Условие B идиотское... Я впустую угробил на эту задачу больше часа. Один я считаю, что если условие нельзя понять без примеров и двух кларов — это ненормально?
Возможно, вы и не один такой, но я условие В(наша D) сразу понял. Хоть я ее и не сделал, но условие понял. :D
Наверное, он про Div-1 B (Div 2 — D).
Но и я про нее.
Пардон.
А я ее все-таки сдал, но на душе у меня исключительно непечатные слова.
Ну условие не идиотское — то есть там нельзя было понять как-то неоднозначно, просто у условии однозначно просили решить другую задачу. По этому считаю что будет странно, если раунд будет рейтинговым
Судя по тому, что кто-то сдал задачу до уточнений, то условие можно понимать неоднозначно, но явно нельзя считать, что в нем просят решить другую задачу.
P. S. Сам много времен убил, чтобы понять условие, забросил, решил С, только потом написал B.
Это решение быстро приходит в голову, просто кто-то его опровергает, а кто-то нет.
Кто-то сдал без уточнений, потому что сперва задача понимается нормально. То есть это как бы подводный камень которого нет :)
в задаче явно были указаны возможные действия, если кто-то дофантазировал возможность отзыва принятой заявки, это не делает условие корректным
*и обнуление денег у администрации тоже придумали
Конечно не делает. Причем больше повезло тем, кто не видит подводных камней. Даже как-то несправедливо получилось :(
Все зависит от того, на скольких участников это повлияло. Лично я тупо не отправлял правильное решение 15 минут (до правки) из-за того что перед сабмитом решил перечитать условие.
ну мне кажется что не количество важно, а его неотрицательность
Не согласен. Если большинство участников верно поняли задачу, то это проблемы тех, кто ее не понял.
Проблемы оказались у тех, кто НЕ придумал лишних условий, которые рассказали позже, т.е правильно понял
В данном случае большинство участников поняли неверно. Просто им повезло, что авторы поняли так же.
То есть, если в условии три раза написано A и два раза
, и, например, 60 участников поняли, что A, а 40 — что 
, то это проблемы этих 40?
Если условие хотя бы допускает неправильное понимание, то это проблема условия.
А если бы условие изначально было правильным, то все это большинство упало бы на взломах и систестах.
Месяц анрейта.
Прирост анрейт раундов увеличен.:(
Почему анрейт?
А с чего бы раунду быть анрейт? Казалось бы уточнения условия В ничего не изменили в условии. Просто они труднопонимаемы.
изменили.
На тест 5 4
8 1 7 7 7 7
ответ при новых условиях — 1
При старых — мы не могли занять площадь 1, т.к у мерии всегда были деньги.
Я, например, придумал решение с текущим пониманием, однако не сдавал(и не писал) его ибо завалил.
Может на других сильно и не влияло
PS: очевидно, я бы не писал такое, если бы считал, что ничего не поменялось.
Аналогичная ситуация..
Ага, я тоже решал не ту задачу, правда даже для нее не уверен что решал верно. В итоге вышло, что на Б потратил времени больше, чем на А, С и Е вместе взятые.
Во время 107 раунда поменяли условие задачи div2 E(div1 C), однако он был рейтинговым.
В том то и дело, что изменили до неузнаваемости
EDIT: факт, того что заявку можно отзывать после принятия всё меняет, а изначальное условие явно говорило, что этого делать нельзя
Давайте будем оптимистами. На CF все пока еще достаточно хорошо для того, чтоб не говорить о нерейтинговости раунда до того, как его огласят нерейтинговым.
Для div.2, думаю, нет смысла делать его unrated, потому что в div.2 большинство участников приступило к решению задачи D после уточнений.
Согласен.
Если на вас это не повлияло, или вы просто не хотите анрейт, то это не значит, что на других не повлияло.
Вы вообще не писали этот контест. Откуда вы можете знать, на кого что повлияло?
В E Div2 / C Div1 просто Heavy-Light?
Я писал Эйлерово представление графа.
уже много раз слышу это словосочетание. расскажите что это? гугл ничего такого не выдаёт
Это когда мы дерево записываем как последовательность ребер в процессе обхода в глубину, причем каждое ребро по 2 раза(прямое и обратное, обычно в два дерева). И тогда мы можем увеличивать какие-то параметры ребер на отрезке от корня к сыну, причем это должна быть обратимая функция(сумма, xor-сумма и тд). Дальше достаточно просто узнавать информацию на пути, зная LCA двух вершин.
Там можно без эйлерова. Просто одним ДФС-ом для каждой вершины подсчитать сумму детей.
О, точно. Чего-то не подумал :)
Я посчитал для каждого пути LCA концов и далее считал чем-то типа динамики.
Можно без нее. Во-первых, LCA. Теперь посчитаем, сколько путей начинаются и заканчиваются в каждой вершине. Теперь dfs(v, p — предок v): число на ребре (p, v) = сумма чисел на ребрах (v, to — потомок v) плюс сколько путей заканчиваются в v минус сколько путей начинаются в v.
Т.к. нас спрашивают результат только в самом конце (а не по ходу), то сделаем следующее. Подвесим дерево, теперь у каждой вершины есть предок. Когда делаем запрос (u, v) делаем ans[u]++, ans[v]++, ans[lca(u,v)]-=2, а ответ для ребра, входящего в вершину u, равен сумме этих чисел в поддереве.
Можно за O(E). Просто находим все LCA, после чего делаем пометки в вершинах: add[a]++, add[b]++, add[lca(a,b)]-=2. Эти пометки означают, что начиная с этой вершины, двигаясь к корню, мы будем прибавлять add[v] ко всем ребрам. После этого одним дфсом считаем значение на каждом ребре и выводим ответ.
А как искать LCA для всех пар за O(E)? Или имело ввиду offline за O(Eα)?
Ну да, я имел в виду в оффлайн за O(E*alpha). Хотя, существуют же алгоритмы, которые за О(N) делают препроцессинг и за O(1) отвечают на запросы в онлайне :)
Спасибо, оказывается всё просто и красиво :)
Можно, но не нужно.
Всё-таки решился написать HL первый раз и зашла сразу. Думал кода поменьше будет.
Вот, если кому интересно. :)
Клары по задаче B заставили второй дивизион перечитать условие дважды и всерьез задуматься.
[решено] Извините, но что такое "клар"?
UDP: всем чмоки
=^3^=Всплывающее сообщение от жюри для участников.
Как говорит гугл — "clarification" => "прояснение". От жюрей к непонятной задаче.
Не знаю как других, но меня неоднократные поправки к условию B окончательно запутали, я до сих пор не уверен, что правильно его понял...
In problem B (div1), in order to get day 1, there should exist an election of at most k-1 values among a2,...,an-1 such that its sum is between b-a1+1 and b inclusive. Is this true? Or I have missunderstood something? If it is, then this problem is NP-hard.
I think that there should exist at most k-1 values among a2,..,an-1 such that their sum+a1 > b.
counterexample: n=3, a1=1,a2=2,a3=1,b=1. a2 cannot be used to reduce b. Or I have missunderstood the statement? Perhaps this is the meaning of the author comment "then rest of administration's money spends and application is accepted", but this makes no sense. Why is administration spending this money used for nothing?
No, should exist an election of k — 1 values such that its sum is more or equel than b — a1 + 1
Да уж...
for (int i=0;i<st.size()-1;i++)
что так писать не желательно, в случае возможного наличия пустых строк, думаю, все знают. Ну и понятно, почему нельзя.
Но что по той же причине
st="A"; long ans=-100; cout<<ans+st.size()<<endl;
писать тоже нежелательно, я как-то не подумал.
Раньше не сталкивался с таким. А сегодня из-за этого весь раунд коту под хвост. 25 лишних минут потеряно на А, при этом после ее АС — полный упадок духа... Какой-то бред по В, который сомнительно пройдет... И С, написанная почти в самом конце тура, за которую баллов тоже не густо уже.
What kind of mocking in Div1 problem B ? If they dont know how to write statement in english , they should not write problem statement ..
The problem wasn't about the English version, it was about the problem statement in general: there were two clarifications regarding the Russian version too.
There's no reason for such words here, and to get angry. However, it's true that the original wording posed the coders with an NP-complete problem. And if someone didn't check the announcements regularly and instead spent the whole contest (or an hour) thinking about this problem, then they were really screwed. For this reason, I think that this round should be unrated.
No,I dont specificly mean for english , this problem statement is really weird ... I have to waste more than 1 hr to understand this problem statement , still dont got it ... rather I could've solve problem C without wastin time in B
In addition, the English version of the first clarification was really hard to understand.
I am also surprised the match is rated. I don't think pretests alone are a good justification. If you get WA, you are not supposed to assume that the statement is wrong. You are supposed to assume that there was a mistake in your code or in your algorithm...
Yeah , Im also surprised to see the match is rated , whereas anybody can waste a lot of time in understandin this problem ... on the other hand it is not good to have unrated matches in last few contests. So I think they could startup a poll to look up , who thinks he is not effected by the problem B and so make the contest rated just for them ...
Unrated!!! It is very very easy to understand B in a different way. I misunderstood twice. After the 2nd announcement, I finally understand what it means. From my point of view, previous description leads to NP-hard(perhaps?) problem.
Me too.
No way!
Yes, it can be reduced from the following particular (but still NP-complete) version of the snapsack problem: Input: Integer numbers C,c1,...,c_m. Question: Is there an election of c_1,...,c_m whose sum is C?
We can see problem B as a decisional problem if the question is whether we can get day 1.
The reduction to (missunderstood and decisional) problem B is simply n=m+2,a1=1,a2=c1,a3=c2,...,a_{n-1}=c_m,a_n=1,b=C,k=n.
I was not able to understand problem B propperly, because of its semantics: it makes no sense that the administration spends money in nothing. Well, perhaps, in the real world this happens frequently, but as a problem statement this is very missleading.
me two
Чувствую себя идиотом. Минут 20 убил на A Div2, в результате написал какой-то тяжёлый перебор с проверкой на треугольность. А полкомнаты сдали в первые десять минут. В чём там матемагия?
З.Ы. ее, Div1, жди меня!
перебираем первое число до корня и и проверяем разность n-i*(i+1)/2 на треугольность
Легко видеть, что всего чисел меньше корня из N.
Потом для каждого ri бинпоиском пытемся найти n - ri.
зачем бинпоиск — тупо найдём корень из 2*(n-i*(i+1)/2) и проверим за константу
Быстрее (в плане написания) и приятнее (без double' ов).
на вкус и цвет фломастеры разные
Я тоже, но у меня перебор еще и не зашел.
Ясно.. То есть такое решение и подразумевалось? Надо же.
Problem B in Div 1 is way too hard to understand! I read the rules multiple times and still didn't get it for nearly half an hour... :(
No, it's easy to understand, but in a different way (at least before the announcement). I want this contest unrated.
Yeah I agree, worse yet — after you understand it, it's easier than Problem A Div 1. (In my opinion.)
The time I needed to read and understand B was sufficient to solve both C and E.
Liked the tasks and the contest :)
Когда авторы притягивают за уши какую-то непонятную историю — всегда получается безумная и нечитаемая ерунда, которую сложно понять. Будьте проще!
Да и вообще, Codeforces не для политики, по-моему. Хотя непосредственно задачи мне очень понравились.
Имхо, вполне политическая задача G из Andrew Stankevich Contest 41 действительно классная и видно, что автор смог трансформировать формальное условие без потери понятности.
А тут какие-то дополнительные навороты, которые подталкивают дропнуть контест(что я и сделал).
А что за Andrew Stankeivh Contest?
Контест с Петрозаводских сборов. http://acm.math.spbu.ru/cgi-bin/monitor.pl/m120201.dat
Спасибо за задачи!
Но никому не показалось, что Е — боян?
E раньше не встречал, а вот С показалась баяном.
а как решать?)
Я решал так: пусть у нас есть массив префиксных сумм — sum[i] — сумма элементов 1..i, sum[0] = 0. Делаем бинпоиск по ответу (A), тогда нас будут удовлетворять подмассивы с суммами sum[r] — sum[l — 1] >= A, что можно переписать так: sum[r] — A >= sum[l — 1]. Тогдя для каждого r надо на префиксе искать количество чисел не больших, чем заданное — это уже дело техники (примерно таким же способом, как искать k-й элемент на отрезке).
Бин. поиск по ответу, а потом просто если А — частичные суммы, то ответ для определенного Х кол-во A[i]-A[j]>=X -> A[i]>=X+A[j], это уже просто деревом решается. В итоге O(N*Log^2N)
Мне показалась идея решения Е бояном (которая мне не сразу пришла в голову), но вроде такую задачу я не видел.
Были похожие на ЗКШ и на четвертьфинале Украины, вроде-бы.
Мне ничего не показалось бояном. В Е даже подумать пришлось.
После этой задачи С Вам бы все-таки показалась бояном.
Ну и память у тебя:) Всего год назад на тренировке решал задачу E, причем решил. Самое интересное, что и Гера тоже ее тогда сдал. А так она в самом деле была в ЗКШ-2011.
Ну было бы 5 часов, я бы успел. Я в одной строке кода набажил.
Диман сегодня на опенкапе была задача которую на одной из тренировок я решил , а Igor_Kudryashov не решил. Так вот на опенкапе я её не вспомнил, а Игорь вспомнил)))
Ну так это же и не задача. Это упражнение на бинпоиск и дерево отрезков.
Да даже если и не боян, не понимаю, почему ее надо было делать Е. Такие задачи почти всегда решаются одинаково, отличается только считывание и первые пару шагов в решении.
Обычно авторы недооценивают сложность задач, а здесь сильно переоценили. Я бы, например, предлагал ее на что-то между B и C.
Ну это уже перебор. Полноценная С. Ну или простая D, как допустимый вариант.
Ну не знаю, наверное это мне так показалось после сегодняшнего раунда, т.к. я ее придумал и накодил быстрее чем B или C. Если так посмотреть, то там используется бинпоиск, сортировка и дерево фенвика (или любой другой сумматор). Наверное, для B это перебор в плане теории, но для С уж точно в самый раз.
По-моему в С вообще думать не надо. Всё и так понятно. А в Е надо было немножко подумать.
Ну да, С тоже сразу ясно, но кода в Е меньше.
the contest was held verry well. it will e rated, isn't it? I want to know about second division.
I suppose you didn't have time to read D-Div2 at all.
i supose that you didn't have time to read the second task on div 1 but you have time to write stupid coments. :D
its hard to get rated contests now-a-days!
Я нашел баг! 0 и 1 по википедии, треугольные числа ! А значит для 1 будет ответ — YES (1 + 0). Что за ?!
из условия:
0 не представляется в таком виде
сам думал, что это баг, но в условии написано, что k должно быть положительным, а 0 как бы и не положительное и не отрицательное.
Задачи понравились. И B(D) понятная задача с самого начала была, хоть я и ен решил=) Должен быть рейтинговый. В контесте не решил ни 1 задачи, пока шло финальное тестирование, переписал все 3, и сдал сразу же, как открылась дорешка. Обидно, что не сдал на контесте(
Codeforces should really hire a single language reviewer for each contest, like misof in TopCoder to remove any potential ambiguity, because this is a serious aspect.
Some of CF problem statements are unnecessarily lengthy and irrelevant.
Yes
I have a problem with my picture(colors), who can I ask about that problem? dario-dsa
known problem with png pictures, try upload jpg
I tried all types, bmp,gif,jpg,jpeg and png. Same problem. Do you see that problem when you click on my profile?
I see, sorry, I don't know then. I always thought problem was in transparent images
I think it's better to make your picture smaller.
When people in div 2 reached this problem I believe there was already enough clarifications to understand it, at least it was easy for me when I read the problem after solving C (+- 50 minutes..)
В задаче А (Div.2) проходили решения за O(n). Люди сначала генерируют все треугольные числа до n (а их, логично, sqrt(n)), а потом перебирают за квадрат и проверяют сумму. Это решение проходит примерно за 1.9 + eps. Как-то неправильно все это... Ограничения надо было поставить побольше хотя бы. Или сделать мультитест...
Can someone give the idea behind div 1 c (the tree question)?
You can decompose a path into two paths that go from a node to an ancestor (use lca for this).
Now you can move from the leafs to the root counting how many people go through an edge.
I did the same but from the root to the leaves. =)
really? I thought about that, but couldn't how to divide quickly the total i have in the parent to the children. I solved this doing it in the other direction because i didn't have to divide anything, since everythin goes to the parent.
Preorder and postorder numbers + Fenwick Trees makes it possible. =) You can look at my solution or 1guangnian's for a reference implementation. I haven't seen any others that did the same.
Once you have the tree, for every node in the queries, the edge from these nodes to their parent belongs to the simple path, let's say that each node has a counter about how many edges belongs to simple paths coming from its children, you can carry this information to their parents and so on. Until you get to the LCA of every query.
Thanks MarioYC and Igarcia ^^ I will look up lca
lca, for every pair（a,b）, cnt[a]++， cnt[b]++, cnt[ lcp（a,b）]-=2, than dfs the tree, each edge's value is the last point's sub-tree sum. May be have better solution.
It is then,not than.>_<
ORZ```
Suppose you want to update the paths between u and v, we can find the LCA of u and v, call it p. Suppose f(x, y) is such that we add every edge from traversing the root of tree (you can pick any vertex as root) to x by y. Then adding in the path from u to v is equivalent to calling f(u, 1), f(v, 1), and f(p, - 2).
Next, you accumulate all invoked f(x, y) for all x, denoted by c(x). For every edge (u, v), suppose u is the root of v, its value is given by
, where i is any descendent of v. This can be done in O(N) time.
How do you import the math symbol(Sigma here)?
picture with the formula :D
% \sum_i{Hello, world} %
replace "%" with "$".
It can help.
UPD: Never mind, just did a bunch of other problems with LCA, makes sense now. Thanks for the insight!
Hey, sorry I'm replying to a comment so late, but why is it f(p, - 2)? Thanks
Does this lca trick appear a lot in contests? First time I see it , but a lot of people seems to know it :p
There's a tutorial at TC : http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor
I guess that made it well known.
LCA trick as in — how to compute the LCA of two given nodes in a tree (efficiently)?
Umm it's a well known thing : http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor
If you mean something else then sorry for spamming :).
Что-то долго не меняют рейтинг.. Неужто анрейт ?
Огоромное спасибо авторам за задачи и за то, что раунд все-таки рейтинговый.
"а неправильное понимание задачи не проходило претесты". А ничего что его хрен придумаешь? И наверное 50-ая минута правки условия для задачи B — все-таки не "достаточно быстро".
+1 — удивительный комментарий
Какая разница проходили ли претесты, если тесты из условия подходили под изначальную формулировку, а само решение изначальной задачи рюкзак с параметрами до 10^18.
Да вообще сама первоначальная задача — какой-то отстой. Вдруг мэрия может оплатить первую площадь, а вторую не может. В первоначальном понимании получается неведомый кромешный отстой
не сказал бы, что это прямо таки уж быстро. Условие пофиксили через 1:20 после начала, как я понимаю, при том, что A топы сдают за 10-20 минут
Да и насчет не прохождения претестов:
Если бы условие было, посчитайте по двум какую-то неведомую фигню, которую не посчитаешь за полчаса, а тесты на A+B, с последущей заменой условия на A+B, текущее объяснение тоже бы проходило. (Не все люди придумав неправильное решение, сдают его, что узнать, вдруг авторы, как раз это придумали)
Еще спасибо Codeforces за что что соревнования иногда проводят по воскресеньям. А то в будни на работу и вечером так ничего не хочется.
Меня огорчило, что нельзя послать решение, в котором есть символы %lld. Даже если они встречаются только в такой строчке (особое внимание следует обратить на два первых символа):
workaround:
можно сделать что-то в духе "..%l""ld.."
Можно даже удалить строчку, но и это не вернёт 20 секунд моей жизни.
Ещё веселее, когда в таком коде.
К счастью, там есть теперь какая-то галочка, после которой 20 секунд тратятся всего один раз.
Мне бы эта проверка пригодилась, если бы игнорировала комментарии. Я предпочитаю не уродовать свой код музейными define'ами для поддержки ископаемых систем.
Да-да, после этого твои задачи очень удобно ставить на тренировках.
(Если уж разводить спор.)
Примерно как задачи с решениями на delphi и cmd-скриптами для генерации тестов? Этим, насколько я помню, любит баловаться ИТМО-шная часть жюри ВКОШП'а.
То, что кто-то делает неудобно — не очень хороший аргумент для того, чтобы самому делать неудобно.
Согласен. Я провожу различие между «неудобно, потому что сделано по устаревшей схеме» и «неудобно, потому что не работает по устаревшей схеме». Твой вариант — «неудобно, потому что куча всяких проверок и разборов случаев», конечно, выгодно отличается (работает чаще).
I solved two questions.. and both have got accepted.. but i have got score for only one.. http://mirror.codeforces.com/submissions/nikunj165 The verdict is saying "Running on test 1" There is a bug and my rating has gone down.. what is happening???
I also see "Running on Test 1" and i also think that there is some bug in the system since it says accepted here. http://mirror.codeforces.com/contest/192/submission/1728200
there is a serious glitch in the contest.. my rating which should;ve gone up has gone down.. my solution for the second problem was not counted as accepted when the ratings were calculated.. it has got ACCEPTED after the ratings were calculated and my rating has been calculated without considering the score for the second problem... CODEFORCES SUCKS!
Try contacting the admin MikeMirzayanov with a private message.
Кто-нибудь знает, в чем прикол 54ого теста в C(div-1)? Поймал runtime error, никак не могу найти ошибку.
Так как проблема с условием была решена достаточно быстро
Это было издевательской усмешкой над теми, кто не имеют талант оракула и по этой причине слили контест?
Интересный факт: процент красных на Codeforces после этого раунда равен 0.89%. Аналогичный показатель на Topcoder равен 3.02%, что в 3.4 раза больше. По-моему, мы наблюдаем ситуацию, обратную к той, которая была до "революции цветов и званий" — красных стало слишком мало. Да и вообще, по моим субьективным ощущениям, рейтинг стал зарабатываться тяжелее.
Сумма рейтингов ощутимо убывает после каждого раунда. В обоих дивах. Видимо недавно поменяли формулы.
А я как-то сегодня(уже вчера) легко в пердив шагнул при не сильно хорошем выступлении и не будучи на ленточке. По ощущениям, месяц назад было потяжелее. Может, что изменили уже?
Ну, 20-е место при 953 участниках — это не то что бы "не сильно хорошее выступление"
ну, помню контесты, в которых из первых пяти только один выходил в кандидаты. ИМХО, в первую пятерку попасть на порядок труднее, чем в 20-30, а на деле, кажется, не такая большая разница получаемых очков.
no editorial for this round?
There is an editorial in Russian, the translation will be posted soon.
I don't think the mistake in problem B is a misunderstanding. There is no statement mentioned the admin can spend part of money.
I guess 90% of the contestants get the wrong understanding.
I thought the writer made a mistake and codeforces fixed the statement to cover it.
I misunderstood problem B and I didn't solve it. It's cost us too much time for it and I think it affected the result as well.
Problemset was great specially problem E div 2. thanks for this problems ifsmimov
Жалко что не смог поучаствовать, задачи были интиресными !!!
The statement was fixed soon enough and the incorrect understanding of the problem didn’t pass pretests
Soon enough? Laugh!
Incorrect understanding of the problem didn’t pass pretests? You cannot submit when you have no idea of solving this problem!
Disappointed with your decision...
It's not hard too prove, that the problem with not fixed statement is NP(it's not easyer than this one), so it can't be solved with such big input. So It's obvious there was an error. I just reported it to authors and went to next problems. It's more darkly to me, how more then 70 people got the statement as authors mean.
I am also disappointed with admin's decision to rate this match.
For problem B, even after the clarifications, I think the statement was still hard to understand, so for me it's like "guess-what-the-author-really-meant" problem... (I am sure many coders abandoned the statement and tried to guess from the example cases.)
Contest start: 7:30pm
The first announcement: 8:18pm (+48 mins, 40% of the contest duration)
The last announcement: 8:50pm (+1 hr, 20 mins, 2/3 of the contest duration)
I think most of us overestimated the meaning of soon enough.
Even though I'm ranked 2nd, which is my best rank ever, I'm disappointed with the decision to make the contest rated. Problem B clarification time was far from soon enough: I was in the middle of solving D when this happened. I was just lucky (and stupid) enough to understand B incorrectly (which later turned out to be correctly) and have no doubt, which gave me second place in div 1, which is clearly unfair.
I'm also disappointed (and very surprised) by the decision to rate this match. I think that the problem with task B affected the results in a fundamental way.
I myself lost about 30 minutes trying to solve the original statement, but I had no idea how to even decide (in the given time limit), for example, whether the answer is 1 or not. Then I moved on to problem C, and finally noticed the announcement after about an hour into the contest. If not for the wasted half hour, I would have solved E during the contest; I had TLE on pretest 15, made a fix to binary search the interval [-10^14, 10^14] rather than [-10^18, 10^18] (this fix, as I later found out, was enough to pass systests), and watched the screen go dim with the round ending just as I was about to resubmit. I actually have it screencasted, I might upload it somewhere later. It's pretty dramatic ;)
If someone didn't refresh the announcements or the problem statement frequently enough, but instead decided to power through the problem until it's solved, they could easily spend the entire contest thinking about the NP-hard problem. For such people, I think that there should at least be an option to be unrated (like there was one time).
In a recent TC round, it was strongly considered to unrate the round just because the challenge phase had ended 3 minutes early. And here we are at CF, rating a round like this. I personally prefer CF a lot — partly because somehow I rarely do well in SRMs and make lots of stupid mistakes, because the input size isn't always 50 at CF which allows for many more kinds of problems, and because it feels somehow nicer and more welcoming here — but I think that this situation in a way shows the difference in professionalism and level of preparation of contests between the two platforms. Just my three cents.
кто умудрился посчитать раунд рейтинговым? мы же полчаса решали нерешаемую задачу ))
A 30 line solution for Div1 E: 1734471 :) Just for fun
With this amount of packing you can as well make it a one line solution.
no
You forgot writing "return 0" whith "printf" in one line:)
return printf("%I64d\n",end+1), 0;return !printf("%I64d\n",end+1);Actually, you can omit calling "return 0". I never do it in the main() function and didn't have any troubles with that so far.
PCMS2 server sometimes threat program without "return 0" as Run-Time Error
In C99 and C++ reaching the end of
main()is equivalent to returning 0. An explicit return is only required in C89.Modern compilers automatically insert "return 0" statement to the end of the main function, as it's required by the C++ standard.
There is no English editorial yet or I just can't find it? :)
[off] Пожалуйста помогите. Как зарегистрироваться на div2 №122, куда нажимать?? В чаво так и не нашел ответа на вопрос. [/off]
До начала регистрации ещё 36 часов.
А так можно на главной справа (там где "Обратите внимание") или во вкладке "Соревнования" будет.
Скажите как понимать "standart input/ouput" ? Нужно считывать информацию из input.txt и записывать в output.txt что ли?
Нет, это stdin и stdout, консолька вообщем.