Всем привет.
Это очередной 133й раунд Codeforces. Специально для 2го дивизиона, участники 1го дивизиона могут принять участие вне конкурса.
Раунд готовили Ripatti , Gerald , Aksenov239 , Delinur и MikeMirzayanov .
Раунд будет с динамической системой оценки задач. Задачи будут расположены в случайном порядке (см UPD1). Чтобы раунд был для вас максимально интересным, пожалуйста, прочитайте условия всех задач.
Удачи!
UPD1. Члены жюри посовещались и решили расположить задачи в предполагаемом порядке увеличения сложности.
UPD2. Контест окончен. Победители:
1. karensun522
2. stostap
3. sisterX
4. BiliBili
решили все 5 предложенных задач. Ура!
deleted
В прошлый раз гарантировалось, что "задача A будет в нем именно та, которую мы считаем наиболее простой". В этот раз это не гарантировано?
В этот раз гарантий нет.upd. гарантии появились):)
what's Gaussian primes?
Thank god, you didn't copy full article
133
Thanks so much for arranging the problems in expected order of difficulty.
Вновь жюри порадовали системой оценки и порядком расположения задач, спасибо.
Спасибо за перевод!
Впервые попробовал взломать чужое решение. Сначала не влез тест в 250КБ. Тогда я сделал генератор – "таймаут 15сек". Пришлось сгенерировать не слишком сложный тест на 218кб – "Невозможно обработать взлом, попробуйте еще раз" – ну что за фигня? (
Плохая карма?
Что такое генератор делает что не укладывается в 15 секунд %)
Рандом+проверка корректности?
Задачи классные, хоть я и слил контест... :) Спасибо
Задачи сегодня какие-то очень тривиальные.
Как я погляжу, ты все сдал за полчаса.. Или не все? Или вообще ничего? Прошу доказательства в студию
Для тех, кто хочет полемику разводить: 1 , 2
Ну вы же не из Див 2. Посмотрите на баллы по задачам. Все очень адекватно. Я думаю, участникам из Див 2 было весело.
Я никого не критикую, не подумайте. Я сам например больше такие люблю, чем идейные, как в последнем див1. Я, так сказать, просто подметил)
По твоему результату не скажешь) Хотя да, мне тоже показалось сильно легче чем обычно
В данном контексте слово "тривиальные" не тождественно понятию "легкие". В данном случае, я имел в виду что-то вроде "написать то, что просят", "ускорить очевидное решение" и т. п.
Задача о гамельтоновом цикле в своей постановке тоже весьма тривиальна, но решение сложноватое:) Понимаешь о чем я?
Ок, не понял значит тебя сразу)
PS: обычно называют техническими, вроде бы
Не скажи это про задачу А :) Да и задача Е, вроде, тоже не трив.
Не согласен. И в "B", и в "C" надо увидеть довольно много не шибко очевидных мелочей.
Были ли у кого-то кроме меня проблемы с загрузкой страниц во время контеста?
на начале контеста, потом вроде все стало нормально )
This contest started horribly for me (it took me a very long time to correctly deduce the formula for A, noob :P), but ended as my best placement ever (35th). I'm really happy, and I really enjoyed this entire competition, all the tasks were very interesting! Especially the Web one (even though the idea behind it is not that difficult, the formulation was very nice :D).
Gratz everyone!
First time used Yandex's notepads to solve problem A :D
so quickly rating!
Thanks MikeMirzayanov!
This time the tasks was not difficult to be writen in programing language but they were difficult to solve. For the first time i was thinking about A task 40 mins.
Contests are going in the direction of the ideal everyone love! Think more than Code! :)
Woohoo. Division 1. да, детка!
Поздравляю! :D
Продолжайте рисовать график в том же духе.
hard questions really! specially question A. I hope the editorial will be available soon. And really thanks to all of you who prepared this great contest.
Спасибо за задачи их авторам. Я, конечно, не претендовал на высокие места. Но обидно, что третья упала из-за маленьких размеров массива. И когда я в одном массиве увеличивал элементы и выходил за его пределы, я перескакивал на второй и там увеличивал. А увеличивал я... ответ. В итоге вместо 1 801 1601, я выдал 2 802 1602. Ну хоть 1, 2, 4 не свалились...
всем спасибо за понимание и минусы к коменту...
in the problem-B forming teams
is it not correct to just find the number of odd length cycles in graph described by 1..n??
It's incorrect
try test "5 0"
it is correct (ofc with also removing one more player if the number of players left is odd), but look at the test which you failed:
n = 4 3 -> 2 4 -> 2 4 -> 3
There is one cycle here, and also this leaves us with an odd number of people left so we got to remove one more, rendering the final solution of 2. Your program outputs 0.
My only conclusion could be that you implemented something wrongly. (since you passed the pretests I guess you already minded the case when the remaining number of players is odd)
yeah... i saw that... i went wrong trying to implement the graph in a different way..
anyways i think i corrected this and resubmitted after the contest...
link --> 2013484
still can't figure out what's wrong..? :(
Please don't write in crippled English on purpose, it is very disturbing.
sorry...
now it is fixed...
It's also necessary to check if there are the same number of people on the two groups
After excluding exactly one element from each odd length cycle, you can get odd number of left (not excluded) students; in such case, we must exclude one more student.
Yes. That is my mistake on that task. :(
sorry for this question(on this blog), but i am intrested why next round time is difference 08/18/2012 11:00AM
Why not? I'm very glad to see morning contest.
I love sleep :D
It's at Saturday :)
UPD: cout << (a+c-1)*(b+c-1)-c*(c-1) << endl;You can see this submission 2013799.
Instead of exact formula, use simple loop (I'm think that this is simplest solution :))
example: http://codeforces.net/contest/216/submission/2007291 [w > 0 check is not necessary]
In condition reads: (2 ≤ a, b, c ≤ 1000).
it seems all of the solutions for problem A are different with each others !! there are no two same formula for this problem in AC codes :D
i found a lot in O(1) solution :D
(B*C) + (B+C-1)*(A-1)
if we suppose we have an rectangle B*C(here A is 1) for any extra of A, we are adding a line containing B hexagons and line containing C hexagons that one of them overlaps each other, so total answer will be : B*C + (B+C-1:(one edge of B + one edge of C — one overlapped)) * ( A-1 :(for any extra of A))
Just for fun: задача с латвийской олимпиады. :)
Даешь анрейтед! Латыши знали задачи!!! :D
Качественный контест! Спасибо!
Here is my submission to problem B: 2014265. It gives correct output on my system as well as ideone. But it fails on codeforces judge. Is there some problem with my code ? Comments are welcomed!!
Function int cycle() doesn't always return a value. Maybe this is the bug you're looking for :)
My submission for Problem D results in runtime error at test case 35. i have no idea why this is happening. I am using the same concept as many other people during the contest.
Perhaps there are some bugs in 69th line and 71th line, and the bug may be "Array index out of bounds". You shoud rewrite like this.
while(lpos < threads[left].size() && threads[left][lpos] < threads[i][0]) lpos++; while(rpos < threads[right].size() && threads[right][rpos] < threads[i][0]) rpos++;
Still the same error.
You still miss the array bound check on lines 69 and 71.
You should rewrite not that while statements, but the above two while statements.
Thanks a lot!
I am getting an incorrect answer for problem B on test case #18. I wish there were a way to get the test case (it's being truncated currently).
Try using the information available, and you are very probably going to see your problem. Remember to change the value of M to the number of lines you have.
You are probably partial visiting/coloring a component, check this case
5 4
1 2
1 4
3 5
3 4
Maybe it works for that case, but the idea is when you get to 4, if you didn't paint all the component, then 3 and 1 are visited, and it might think it's an odd cycle.
Thanks, that indeed is the error. (Edit: No, it's not!)
I was not keeping a proper track of connected components.
I have found a very easy approach for problem A. The idea is to calculate like this if a>1 && b>1 && c>1 //it means its a hexagon: so ans = ans + 2*(a+b+c)-6 (calculating the tiles on perimeter)...
else //i.e. a==1 || b==1 || c==1 it means its a square now... ans = ans + (a*b*c);
for those who couldn't AC Problem D : i prefer learning function upper_bound(first_iterator, last_iterator, data); (in C/C++) (which uses binary_search and it's order is O(logN))
i think CLEAN BruteForce algorithm gets AC too... but with this function, implementing is SO EASY, it does all the job...
all you have to do is find four upper_bounds(two for each side of cell) and calculate distances see if they are equal...
In Problem B,
This Test Case :
The expected ans is 0 but how will we make 3-3 pairs with this configuration ?