Всем привет!
Совсем скоро, 11 апреля в 19:30 MSK состоится Codeforces Round #179, автором которого являюсь я. Это мой пятый раунд на Codeforces и я надеюсь, что не последний.
Спасибо Геральду Агапову (Gerald) за помощь в подготовке раунда и Марии Беловой (Delinur) за перевод условий на английский.
Настоятельно рекомендую прочитать условия ВСЕХ задач.
Разбалловка в первом дивизионе стандартная, а во втором: 500-1500-1500-2000-2500.
Gl & hf ! :)
Контест завершен. Надеюсь вам понравились задачи.
Победители в первом дивизионе:
1). marcina007
2). yeputons
3). gawry
4). KADR
5). enot110
Победители во втором дивизионе:
1). goie
2). Koblyk
3). Beriand
А какая разбаловка? Что-то давно не было динамической =(
I can't wait to participate in the contest！！！！ I love codeforces!!!!
Good luck everyone
Less DP — more geometry!
Sereja рубит капусту на раундах codeforces
та если бы не такие как Сергей то сидел бы ты на КФ и максимум тренировки решал
Cогласен. Задачи от Sereja всегда очень интересные, да и вообще мне нравятся все его контесты.
del
да я же ничего против не имею, правильно делает
unfortunately I cant participate in this round but seems a great contest like all contest that Sereja have prepared.
good luck & good rating changes .
than contests author is Sereja my rating decreases, I hope that today this tradition will be destroyed;))))
Ignore this please. It wronged my meaning. . .
Where is score distribution?
If there is any change in score distribution it will be mentioned before the contest. If not then the score distribution will be traditional.
Thank you. :)
here.
а что означает Gl & hf ! :) ?
good luck & have fun, что в переводе "желаю удачи и получить удовольствие"
"I strongly recommend you to read ALL the problems" — it does remind me of problems with close difficulty :P
Sereja tells this before every contest written by him.
Its hard to form problems with 7 different difficulty levels, where the only assessing tool for difficulty level is experience!
WTF?? В 1 задаче тесты из условия решение проходит, но при отправке — ошибка на 1 тесте! Разве при проверке первые тесты не такие, как в примере?
затести в разделе "Запуск"
ну не знаю. Я ломал у меня все было норм хотя и на хроме) И как по мне то лучше обвиняйте не КФ и не хром, а ваш компьютер.
ААААААААААААААААААА!!!!!!!!!!!!! Сидел писал два дерева отрезков, второй назвал также как первый, только добавил цифру 1. и все методы рекурсивные таким же образом назвал. В общем, спустя одну минуту после окончания контеста понял что я из всех методов для второго дерева отрезков, вызываю методы первого. Обидно блин! UPD: в дорешке решение зашло. вдвойне обидно.
Дерево в С (если ты про него), скорее всего, упадет, еле-еле влазит по времени
Она ж решается за O(n) без всяких структур данных.
Ага.
Хм.. Массив — это тоже структура данных:)
Не, дерево зашло за 0.546 сек
Не упало. 625 мс с vector и прочим счастьем.
Зашло моё решение в дорешке.
Great contest. Good Luck
very good system test speed thank you codeforces
Thanks for ultra-fast system testing :)
Чёрт, с задачей С на 11 тесте прям аномалия какая-то. Сначала было написал функцию, которая б по заданному закону изменяла массив, потом уже всё в мэин засунул. В конце концов упростил уже до такой степени, что осталось 2 массива (1, с которым производятся операции, и 2, псевдодвумерный, где, собственно, хранятся цифры для операций) и несколько циклов, в которых, собственно, и производится прибавление чисел. И всё равно пишет, что превышено допустимое время! — Уже не знаю, что там ещё можно оптимизировать >.<
И кстати, если глянуть, практически все как раз на 11 тесте и спотыкаются, многие и на времеи, дык что ж такого они там нагородили? о_О
Не, я вот даже код выложу. Может, кто посмотрит и подскажет, что здесь неоптимального? =( http://codepad.org/Svk2WD4D
Размер шрифта крайне неоптимален!
Ваше решение делает число операций, пропорциональное n2, поэтому не укладывается в заданное время
А можете тогда, если не сложно, хотя бы натолкнуть на мысль, какие есть более быстрые способы?
Операцию transform можно делать так: завести еще один массив pref, и если приходит запрос l r, то сделать ++pref[l] и --pref[r + 1]. После этого a'[i] = a[i] + pref[0] + pref[1] + ... + pref[i], и все такие a'[i] можно посчитать за один проход по массиву pref.
Эх, зря перепослал :( В системе не оказалось теста, который валил первое решение.
Very nice and balanced problem set...One of the best contest I have ever participated in...
Thanks
Блин, обидно, что занял не 74, а 73 место :(
Контест писал в 47ой комнате и занял бы счастливое 74 место :)
good problems.thanks.
Сегодня на задаче С я понял, что надо избавляться от взятия по модулю везде, где только можно) Вариант с Iters*(N^4) взятий по модулю — ТЛ11 Вариант с примерно Iters*(N^4/30) взятий по модулю — 0.061с.
Или я где-то втупил, и первый вариант зацикливало...
По-моему у меня было как раз O(N4) взятий по модулю. Не упало.
У меня изначально на каждой итерации N^4 было. Точнее, M^2, где M — количество валидных комбинаций из больших и маленьких людей. Т.е. в худшем случае M=(N/2)*(N/2). А итераций пускал 200) Т.е. это около 80 миллионов взятий по модулю.
Но только что я вообще завис, так как нашел в своем последнем (АС) решении гениальную защиту от переполнения:
if (ways[moves][l1-i][l2-j]>overfl)ways[moves][l1+i][l2+j]%=bs;
(обратите внимание на знаки в скобках)
У меня на позапрошлом раунде был прямо противоположный опыт — практически правильная Е свалилась из-за отсутствия модуля в одном месте.
Теперь у меня модульная паранойя. =)
How to solve problem B (Div-2) ..?
Hello, during contest I had trouble with C and got TLE status...
I tried to use a map to group the number of times each query needed to be used and did a double for loop to update answer...
I also think that some sort of Range Query algorithm would help, but I can't yet implement one. Can someone help me and describe a possible solution for C Div2?
Thanks in advance,
Bruno
Use Binary Index Tree or Segment Tree.
I used delta encoding twice, less code + better complexity.
one on the number of times that each operation executed, and the other to compute the new array
Or you can just use idea described in this editorial (problem C, two last paragraphs). That problem also was about intersection the segments.
There exist O(N) solutions.Considering each operator (Li,Ri,Di),we add a[Li] with Di and minus a[Ri+1] with Di,then the sum of a[1] to a[i] is the change of ith number.We can count the times of each operator in the same way.
So considering 1st example of the statement, how can we apply that approach? If we add + d to left element and subtract d from right element, how can we find the updated array?
3 3 3 1 2 3 1 2 1 1 3 2 2 3 4 1 2 1 3 2 3
Array is 1 2 3...
1st query is 1 2 1, so array stays now 2 1 3 (?) and so on? :/
We should calculate the times of each operators first. For each [xi,yi],add 1 to b[xi] and -1 to b[yi+1] The sum of b[1] to b[i] represents the times of ith operator. Multiply each times to corresponding Di and then apply the method above.
Thanks a lot for this hard contest. Both of my codes for problem A and C got "Pretest Past" but now both of the are Red! Also Thanks for this fast system test.
Now I get that an unrated user won the contest again!
what's your problem with them? I can't understand your wondering.
Great contest!Thanks to Sereja and Gerald!
Nice problems overall, I really like the idea behind the solution of problem D, very clean, although it was an odd round for me I solved A, C and E.
I failed problem C (div 2) and I cannot find where my solution went wrong. (I'm using segment tree). May someone help me ? Submission.
I didnt really read your code but when i too got WA11 i had an error in vector/array's ranges. Do you use N and M sizes correctly?
Thanks a lot Dixtosa :-) What a silly mistake :-(
My solution for problem A gets WA on the codeforces server but on my PC it's giving correct output for that case. Why is this happening? Could someone please help. Here's the code: http://www.codeforces.com/contest/296/submission/3511959
In my blog you can find more about it. I faced this problem a few times. Here is a conversation about how to avoid this problems.
HF & GL!
int main() { cin>>n;
rep(i,1,n) { int x; cin>>x;
}
rep(i,0,1010)
//1010 is larger than your array's size, I change it to 1000 and your program output "NO" in "Custom Test"
{ D.x=i; D.n=num[i];
}
rep(i,0,1010), but#define MX ( 1000 +3 ). I think this is the reason.Thanks a lot guys. Really silly mistake, should've been more careful :(
I tried to hack a code in problem C, which was plain brute force. I wrote a hack gen here but i got the error "FAIL Input can't start with empty line, but the first line is empty [validator wfval.exe returns exit code 3]"
Can any one tell the mistake so that I wont repeat it.
Are you sure you've uploaded in source file field and not in input file field? I've got such error because of this previously and i see your source code starts with an empty line.
Ого уже и разбор есть!) Очень быстро сегодня и тестирование и разбор)
Но рейтинг как-то опоздывает... :)
Вот Вам и рейтинг)
Tried to solve Div2 with DP lol. So much wasted time in debugging, and then saw the simple way :(. But this is one of those bad solutions that I am proud of http://codeforces.me/contest/296/submission/3514056
Div2 Problem C: I used the binary indexed tree approach...my code runs fine till testcase 11... Can any1 help me find my mistake? here's my solution http://www.codeforces.com/contest/296/submission/3512783
Thanks a lot for the contest! But:
Why didn't you make an illustration in Div 1 problem D?
It was annoying to read that text passage about sets/subsets, without an illustration showing what it's all about.
Even better (= more polite to contestants) would be to give a sample test like "3 3" or "2 3" and show (as pictures) all the valid caves in that pad.
Next time I will note your advice. Thanks :)
could anyone please provide english version of the Ideas to problems page? If I click on translate button, only problem A is being translated to English, all other problems solutions are shown in Russian itself (they do not get translated). Thankyou.
Can anyone please explain the logic behind this solution of problem B of Div 2 ? I have having hard time understanding the dp state.
Thanks!
Can someone explain solution to probl C div 1 / E div 2 in more detail please ? Thanks!
At first, note that we have only 2 type of people, let us call them "small" and "big" according to their weight. Assume some moment (state), then it can be defined by the number of "small" and "big" people on one shore and the position of the boat (the bank of the river it is adjacent to). Let the states be the vertices of the graph. It is understood that we can get from state to state with the help of the boat transportations. Therefore we have the directed (or undirected, it doesn't really matter) edge from one state to another if we can get from one to another by exactly one traversal. Obviously, the initial state is {0; 0; 0} (assuming we count people on the opposite bank, 0 corresponding to the initial bank, 1 — to the opposite), the final state is {n1; n2; 1}, where n1, n2 — the number of "small" and "big" people respectively.
So the solution can be easily implemented by using breadth-first or any algorithm of finding the shortest path in the graph (because of quite small constraints). Moreover, you don't have to build the graph explicitly, you can do it implicitly (like me , for instance (: 3513759).
The only thing you might still not understand is how to count the number of various ways to gain the minimal answer. Let us count in how many ways we can choose i people from x "small" ones and j people from y "big" ones. Obviously, that equals to
C(x, i) * C(y, j), whereC(n, k) = n! / (k! * (n - k)!). In such a way you can maintain another array that counts the number of possibilities and change it when you find the shorter path (assign the new value) or another path of the same length (add to the previous).Hope I made it at least a bit more clear to some contestants (:
Great. Many thanks!
Can someone please explain how we can have 72 ways for the following case?
5 250
50 50 50 100 100
The minimum number of rides required are 3. My DP code(12225775) gives 46 ways and I have calculated it by hand as well giving the same answer.
The possible moves are —
After either of these moves, all remaining on the left side are transported together to the right side in 1 ride.
The total comes out to be 46. I am unable to find any other case. Can anyone please point out my mistake?
UPD : Found the mistake. Was only considering cases in which a single person comes back.
Two coders form Poland in top 3! Nice to see :)
Although one of them is having relations with the German oppressor!
Screencast of me solving this round.
Thank you a lot :)
What program do you use to test it on the sample tests?
Some links: http://codeforces.me/blog/entry/6785#comment-12392
http://codeforces.me/blog/entry/6941
Could you please write an English solution?
I can't understand the statement of porblem c in div2 , what's the query stands for ? How to explain the sample tests ?
Explanation of first testcase : Initially , the elements of array (a) are : a[1] = 1 , a[2] = 2 , a[3] = 3.
We have three operations :
operation 1 : 1 2 1 : increase every element a[i] with 1 <= i <= 2 by 1
operation 2 : 1 3 2 : increase every element a[i] with 1 <= i <= 3 by 2
operation 3 : 2 3 4 : increase every element a[i] with 2 <= i <= 3 by 4
and three queries :
query 1 : 1 2 , query 2 : 1 3 , query 3 : 2 3
We have to execute the queries.
by (a,b,c)--->(a',b',c') I mean the new state of the array after performing some operation.
Query 1 asks us to perform operations 1 and 2. (1,2,3) ---> (2,3,3) ---> (4,5,5)
Query 2 asks us to perform operations 1,2 and 3.(4,5,5)--->(5,6,5)-->(7,8,7)-->(7,12,11)
Query 3 asks us to perform operations 2 and 3. (7,12,11)--->(9,14,13)--->(9,18,17)
got it! thank you!
What a pity! I just had a very little bug in Div.2 Prob A , or I would get a lot more Rating!
How I wish there is solution in English?
solution written in Chinese
Looks good to me. At least, much better than the 'official' one.