Всем привет!
Совсем скоро, 21 мая в 19:30 MSK, состоится очередной раунд Codeforces #247 для участников Div. 2. Как всегда, участники Div. 1 могут поучаствовать вне конкурса.
Подготовкой задач занимались Кирилл Щетинин(KaiZeR) и Вася Антонюк(Antoniuk). Это наш первый раунд на Codeforces и мы надеемся, что задачи вам понравятся.
Выражаем свою благодарность Gerald и Delinur за помощь в подготовке раунда и MikeMirzayanov за Codeforces и Polygon.
UPD: Распределение баллов по задачам будет таким — 500-1500-1500-2000-2500.
UPD2: Соревнование завершилось, спасибо за участие)
UPD3: Разбор задач.
UPD4: Статистика.
Поздравляем победителей!
1) hzjsxxy
2) azariamuh
3) tonkosi
4) inutard
5) c.u.c.u.m.b.e.r
Всем удачи и высокого рейтинга)
Ukrainian contests are always special , hope it will be a special one too
Надеюсь легенда будет интересной)
Antoniuk , your chart is quite interesting after you become yellow you drooped to gray then you backed again to yellow , can you tell what is the reason behind this?
I think he just share the feelings with gray coders :)
He's gray-friendly :D
He tried to draw a heart cardiogram.
He didn't drop to grey !?
1200 Exactly Nice catch
just for fun = =
Actually this is not rare :D
http://mirror.codeforces.com/profile/sillycross
Wow!! if Antoniuk was involved that will be definetly awesome.
Hope my rating will rise this time :P
Gd luck everyone :)
Last contest that Gerald participated was Codeforces Round 104 (Div. 1), Since then, He is preparing contests...
Thank you, Gerald!
i am a little bit worried about the problem statement.
I hope the problem setter will have explanation for the first example for problem A.
Don't worry it's unrated for you :)
Sereja also comes from Ukraine. He is always setting very attractive problemset. :)
Good luck to every one!!! Boys.
in Codeforces round 247
And what about girls?
Oh, My eyes! :)
hzjsxxy Решил Е меньше чем за минуту, хм...
Он просто сдал её через минуту (и через две, кстати). Возможно, он написал её раньше, а сразу после того, как сдал С, нашёл баг в Е и её тоже сдал.
Ну и ещё есть шанс, что там полная фигня, написанная лишь для того, чтобы пройти претесты.
Или Е решается в одну минуту :)
I don't know if it's only me, but the english translations are very bad. I was not able to comprehend problem E at all.
I can't understand russian version of problem's E statement, although Russian is my native language.
It looks like this problem much easier to solve than to understand.
I could not understand English statement, because it was not clear. After switching to Russian, failed to understand again. And I thought it is because I was not native Russian speaker. :(
I couldn't understand the statement of E.
It's not only you. For problems A-D the english translations were alright. For problem E, WTF?? I still don't understand what the problem wants us to do.
Problem D. There is no answer if m = 0 and d = 1
The statement says there is guaranteed to be a solution for given m, k. Which means that a test with m=0, k=1 will not appear.
what was the solution for problem D?
i think binary search + dp
If you try to find the formula for a given n, you will end up with something like (sum of binomials) = m. It can be solved greedily.
I think problem B should be 1000 instead of 1500 !?
Again, like other contests, a lot of newly registered participants (within 10 hours of the contest); but the worst of all is that the first person in standing, containing both div 1 and div 2, is one of those!
В задаче В для некоторых комбинаций gij должно быть отрицательным! Не все же собеседники доставляют удовольствие :)
Отличительная черта ментальности украинцев — позитивность, общительность и жизнерадостность, поэтому у нас все комбинации неотрицательные:)
Даже если в очереди комендант?
What is that mythical Test #9 in problem D? I can't pass it =\
It seems that D and E are way harder than normal for these contests. I solved E because I had code for R-B trees handy, which probably wasn't the expected solution.
Maybe your program writes "0"
That was indeed the case, but I wasn't using binsearch so my solution naturally got the zero. I don't understand the point of this, the goal is to solve the problem and not look for every possible corner case that has very little relation to the actual solution.
0 2
what about editorials?
Will be published soon after system testing.
в С настолько маленькие ограничения на n, k. что у некоторых прошло n * n * k * k!
Ещё системного тестирования не было.
такие решения должны падать
Скорее будет странно, если у кого-то не зайдет за N * N * K * K (если, конечно, восклицание не относится к факториалу:) )
Как D решать? Там надо как-то поиграться с тем, что кол-во чисел, у которых K единиц в двоичном коде на интервале [0; n] равно кол-ву таких же чисел на интервале [n + 1; 2 * n] ? Или там что-то интересней?
Рассмотрим массив P(n), i-й элемент которого — количество чисел с i единицами в двоичной записи на промежутке [n+1,2n]. Например, для n=9 P(n) = {1,4,3,1,0,0...}. Во-первых, при переходе от меньшего n к большему элементы массива P(n) не могут уменьшиться. Потому что при увеличении на n на 1 мы выбрасываем из рассматриваемого промежутка число n+1, но добавляем число 2*n+2, у которого такая же двоичная запись плюс нолик справа. Во-вторых, мы прибавляем к этому промежутку еще и число 2*n+1, которое и модифицирует массив P(n). Например для P(10) = {1,4,4,1,0...}, потому что число 19 имеет три единицы в двоичной записи, и оно увеличило третий элемент массива P(9) на 1.
Получается вот что: все четные числа приходят в рассматриваемый промежуток на смену своим половинам, и только нечетные реально модифицируют массив P(n), причем только один элемент и только на единицу. Поэтому если мы хотим найти число, в промежутке которого m чисел с k единицами в двоичной записи, нам достаточно найти нечетное число которое изменило k-ый элемент массива P(n) с m-1 на m. Иными словами, m-ое нечетное число, в двоичной записи которого k единиц. Если такое число с — ответ на задачу равен (c+1)/2.
Как именно это сделать, я подробно описывать не буду, потому что у меня какая-то переборная хрень.
Спасибо, классная идея!
Используем переход f(l+1,2*l)=F(2*l)-F(l) и получим задачу, которая была 3 дня назад на codechef (Book Game with Chef). Решается обычной поразрядной for-for-for динамикой.
Можно так: Научимся отвечать на вопрос: "Сколько чисел с k битами меньше или равны X" (пусть это f(n, k). Тогда для нашего некоторого n — количество чисел с k битами на интервале равно f(2 * n, k) — f(n, k) = Y. Заметим, что с ростом n Y возрастает. Сделаем бинарный поиск. Теперь, как считать f(n, k). Найдем старший бит в n. Пусть его позиция — p. Тогда к ответу прибавим С[p-1][k] (числа с k единицами у которых старший бит меньше p). Поставим одну из единиц на позицию p (вычтем из n эту старшую единицу) и рекурсивно продоржим.
What was the approach to solve problem C?
I used Dynamic Programming
Compute the total number of ways to break number n into summands which are <= k. Let it be S. Then number of ways to break n into summands which are <= d-1. Let it be R, these ways to break the number are "bad" and should not be counted in the final answer. Thus, the final answer is S-R.
No , I don't think that will give the correct answer in case when we take modulus along the way.
mod = 1000 ; Suppose final S = 1234 and final R = 999 ;
but when we will take modulo S%mod — R%mod <= 0 Which will give the wrong answer.
I gave just the general idea, modulus is the detail of implementation.
This is my first contest :) Hope I will get a high rating :)
I do not believe you.
Why did this solution pass systest?
Interesting part:
Interesting!
if s[i]=='4' then A[s[i]-'0'] is A[4]
strlen(s) works in O(n) time!
scanf("%d %d %d %d\n",a+1,a+2,a+3,a+4);Ссылка на скриншот
Мне кажется, или таких надо банить?
Какая сложность авторского решения в Е, и какие решения предполагались с учетом тл в 4 секунды?
Бинарный поиск + фенвик работает быстрее всех авторских решений укладывается примерно в 0.7-0.8 секунды. Сложность O(Qlog2(N)) кажется. Правда там еще сжатие координат было... Постараюсь побыстрее дописать в разборе.
Any ideas on how to solve B for a much bigger N? First time i read the problem i thought n <= 10^5
I have solved it in O(N^2) using DP. I think it can't be solved faster. So, n could be somewhere around 2000.
What is the runtime (in seconds) for n=2000?
Same here! Wasted 5 minutes and then solved C before realizing n is always 5.
how this solution AC ?!!! http://mirror.codeforces.com/contest/431/submission/6671729
48 here same as '0'. Read this http://www.asciitable.com/
i don't mean that , i mean he made an array of size 4 and used index 4 !
Doing this results in undefined behavior. So, I guess he just got lucky.
Same solution for problem D got AC in MS C++ and WA in GNU C++.
6676019
6676015
Why? :(
As for your code, the behavior of
X >> iis undefined when i = 64, for the behavior ofop1 << op2andop1 >> op2is undefined if the op2 is negative, or greater than or equal to the length in bits of the op1. So, you can get AC in both MS C++ and GNU C++ by replacingX >> iwithi < 64 ? X >> i : 0for example.Thank you, I got AC by calling the function with i=63 instead of 64.
I found that it's undefined even in MS C++...
Problem C should tell that the number must be positive or something like that. For example 17 mod 5 = 2 = -3. When you say print 17 module 5 I can print -3 too unless you specified that the answer must be positive. After 1:24 I got hacked and immediately submit another. which is now accepted but I lost a lot of point -50 and ~ -450 or -500 for timing.
the problem asked you to print the number of paths , how it can be negative ?
No, the problem asked me to print number of paths module 10^9 + 7.
http://en.wikipedia.org/wiki/Modulo_operation
"The range of numbers for an integer modulo of n is 0 to n − 1."
Fair enough! My fault.
You can blame broken % operator in C++. But don't blame contest authors ;)
No! % operator works ok. I write my code in a way which the number could be negative.
I corrected it by replacing cout << ...; by cout << (... + 10..7) % 10..7;
That's what I did. I used long long and ( + 10....007) % 10...007 staff. If % operator was mathematically correct in C, there would be no need in jumping through hoops like this.
Wasn't problem A too easy to become a contest problem?!
Nice problems.... :)
Nice contest for me... :)
Hope to see you again... :)
Can someone please explain the statement of problem E ?
The subproblem can be formulated as this: You have an area of land, with h[i] being the height of the i-th section. You want to pour V liters of "rain" on this land (so that the water level is the same for each section that isn't dry). Find the resulting water level.
Now you have the initial heights, and a bunch of queries that either change the height of one section, or ask you to solve the subproblem for a given V.
When will the editorial be available??
Editorial
Can u explain Random task, bit more clearly.Not able to understand.
Is there a way to download the test cases, other than trying to "brute force" it by sending fake solutions? My solution to E fails on one single query on test #28, and all other queries are correct. Very suspicious...
Try writing big random test generator and brute checker function, and test your solution with it.
It seems far more productive that brute forcing tests.
Considering it works on all test cases except for one single query, I don't think I would be able to replicate that easily. Besides, I already did that last time I used the same data structure.
http://mirror.codeforces.com/contest/431/submission/6672763
http://mirror.codeforces.com/contest/431/submission/6672950
aren't these two solutions same ?
why most of the times div2 winners are unrated users, even in recent topcoder contest same thing happend..!!!
Can anybody explain me why this solution gets WA 6676798 I simply solved the problem using DP without considering the condition d (the result will contain those paths that doesn't have any edge with weight d or higher ). After that i did the same thing with d-1 as k. (using edges with weight d-1 or lower ). And my answer is (first result) — (second result) . . . sorry for my bad English.
can someone explain me why this solution gets WA :6676798 my answer is : (all the paths using edges with weight k or lower) — ( all the paths using edges d-1 or lower)
Changed 6676977
i feel so stupid :| thanks
I like div-2-only contest because I have to compete with the second (or nth) account of the first-division people. No, it is a joke, lol. I don't like div-2-only because that.
Round Stats
Хм, и часто так бывает, чтобы из первой пятерки участников трое зарегистрировались за несколько часов до контеста?
Всегда так.
Нормальным кодерам не дают прохода... Каждый раз с ними за первое место бьюсь!