Всем привет!
Приглашаю вас принять участие в Codeforces Round #253, который начнется в четверг 19 июня в 19:30 MSK. Раунд будет проходить в обоих дивизионах.
Это мой первый раунд Codeforces, и я надеюсь, что вам он очень понравится!
Большое спасибо Gerald за помощь в подготовке раунда. Также хочется поблагодарить MikeMirzayanov за создание удобной платформы для проведения соревнований. Также благодарю тестеров этого раунда: antonkov, Aksenov239, VArtem, subscriber, niyaznigmatul. А еще Delinur за перевод условий на английский.
Не пропустите шанс получить удовольствие от решения интересных задач!
UPD. Распределение баллов по задачам:
Div1: 500-1500-1500-2000-2500
Div2: 500-1000-1500-2500-2500
UPD2. Соревнование завершено, всем спасибо за участие!
Поздравляем победителей Div1:
1) tourist
2) scott_wu
3) stevenkplus
3) gs12117
5) GlebsHP
А также победителей Div2:
1) tafit3
2) thnkndblv
3) MIT3
4) lucaslima
5) liuzhijian
Особенно хочется поздравить tourist, единственного, кто решил все пять задач, а также единственного, кто решил задачу 442E - Гена и второе расстояние!
Разбор задач уже опубликован.
Early announcement, thanks for this!
Early announcement
-->more up-vote!Comment regarding Early Announcement
-->more up-vote!Comment regarding "Comment regarding Early Announcement
-->more up-vote!"-->more up-vote! :DIt's too hard to write something funny. So just down-vote me pls.
Why you down-vote me? Can't we make fun a little? :(
That would have led to an infinite loop :(
Actually my last comment have '37' down-vote. So anyone doesn't say "Comment regarding bla-bla-bla
-->more up-vote!" :DHence No infinite loop. :)
break;// thanksRepeating jokes usually aren't very funny, especially if they're formed by repeating someone else's joke.
such wisdom.
is it always necessary every time when the auther makes an early announcement someone writes a comment saying "wow early announcment"
I think, this is earliest announcement.
Hope we all get good grades
why so many down?
Maybe because programming contests aren't school, so there are no grades? (So it's a completely off-topic/spam comment.)
I think because he used "grades" instead of "ratings". Note that similar comment from the same person with correct word has been accepted AC.
I have a good answer for that, too :D
Consider the case when all participating users rank exactly according to their rating before the contest, and all participants were specialists initially. Then, since the participant has not been 'overtaken', his rating should not decrease.
All constructive ideas, comments and clarifications are welcome.
Well now i think it is because the probability of her hope being fulfilled is 0.000000000. Proving it is a good exercise of mathematical reasoning.
Please think that whether you wish is theoretically possible. That comment is down voted mainly because it was intended towards just commenting.
Hope rating++~~~ Enjoyable contest in Codeforces becomes one of my daily life~
agree. It becomes one of my daily life :)
me too,I really enjoy it,espically when my rating gets higher :)
Me too! I really hope improve myself and get the higher rating :)
me too. Rating up and down here, so enjoyable!
This is the second : tending to infinite loop in this page.
I dont want that every user comes here and contribute like this.
So, I hope this will break the flow :
break;This comment does not wish any replies as then the brake will fail.
ok
The final exam is approaching.But It is always enjoyable to have a codeforces round.Hope all the participant can enjoy the round.
participate in contest can keep on the feeling of algorithm. And codeforces contest costs only 2 hours.
yes,really can not stand watching stand by but not participanting in this game
May the codeFORCEs be with you...during exam ;)
The same day with TopCoder SRM 625.
Topcoder
break
Codeforces
Thanks god there is no worldcup match that time!
Colombia VS Côte d'Ivoire
oops! I didn't see that!
So, too bad that there is a worldcup match that time :(
Too many contests in the days of the exam , I hope there will be that much in the holiday =)
Too many contests in the exam days , hope there will be that much in the holiday
Expecting the problems to be based on footballers / football :)
maybe like this problem? ;)
^btw...speaking of football.....nice handle(yours) :)
Hope your first Codeforces Round will success and the problems are diversity and useful for everyone
hope everyone get higher rating !
I hope not. It would mean that there's something seriously wrong with the rating system, not to mention it'd be boring.
Last Codeforces round before ACM ICPC World Finals! (or not?)
I think it is yes for Div1 , but it is not necessary to stop Div2 contests during the World Finals
Waiting for ur problemset !!
last few contests users ask why problem writer write "score distribution will announce later"
but here score distribution not mentioned at all he didn't say later or mention it.
I see very little point in writing "scrore distribution will be announced later" because it doesn't give readers any new information :)
Of course as early as we dicide everything about score distibutioin I'll add the information to the post.
orly? That phrase is at least more informative than this one: "Don't miss a chance to have fun of solving interesting problems!"
I am a new member of codeforces.. I wuld like to know regarding the concept of div 1 and div 2 What are they?? and in which of them do I belong ?
Any new contestant by default belongs to Div2. If you do good, and your rating increases over 1700, then you will be promoted to Div1. The rest you will figure out once you start participating regularly.
Стремно как-то писать первый див. 1 раунд))
Судя по нику, придется, чтобы достичь цели!
а еще и разбалловка ободряет(:
Hope I will make it to first division! It's the first time I am so close. Only 31 points...
Looking forward to the codeforces round and the WC match after the contest between england and uruguay
Can anyone explain what is meant by the score distribution Div1: 500-1500-1500-2000-2500
Div2: 500-1000-1500-2500-2500
There will be 5 problems and maximum points for each individual problem are 500-1500-1500-2000-2500.
Had a really great performance Topcoder SRM 625 a few hours ago ... hoping for same (or maybe better) performance in this codeforces round! GL & HF everyone!
Please can anyone upvote/downvote my comment ? I want to see what kind of notifications we get when our posts are upvoted or downvoted .
I'm a new contestant of codeforces so div 1 or div 2 which appropriate for me... ????
Since you clearly don't know that you're assigned a division based on your rating (and unrated means div2 automatically), it's clear that you're new :D
div2
div2
There was some problem . Xellos and aangairbender's comments were not visible when I replied .
Why don't you press F5 when you reply?
Does Div2 B have 1500 or 1000 points?
I really don't understand C div 2 problem statement and examples!!!
Can someone explain div2 B problem ?!
my brute force approach passed the system tests.
For all different substrings, I searched for the maximum possible value for
l.I feel like I just took out my hack interest over the past 2 years... +4 mfw
Problem B Div2 was harder than usual! I also think D div2 was easier than C! Because it had more pretest passed submissions!
Very Hard Contest O.o , C — no idea, D-I hate statistics homeworks , E — wow what a problem, but no idea :(
It reminds me of #146div1.......
Hard contest :/ !!
AC :333,
Правильно ли я понимаю, что в div. 1 C оптимальная стратегия — жадная, нужно лишь её правильно реализовать? Если да, то как, если нет, то как следует решать задачу?
Все мои жадности не прошли стресс с решением за O(n3)(задача о перемножении матриц).
Можно подробнее о перемножении матриц?..
Есть классическая задача. дано n - 1 матриц со сторонами aixai + 1 у i-й матрицы. за какое наименьшее время их можно перемножить. получаеться полный аналог задачи div1C но вместо min(a, b) пишем a * b * c, где c — выкидываемое число.
dp[L][R] — ответ для подотрезка с L до R и крайние числа удалять нельзя.
Переберем число M (L < M < R), которое удалим последним. Тогда это принесет нам min(a[L], a[R]) + dp[L][M] + dp[M][R]. Выберем максимум по всем M.
Вот и я придумал такое же решение, а как справиться с тем что не умещается по памяти? Ведь (5 * 10 ^ 5) ^ 2 * 4 байт не умещается?
По времени (5 * 105)3 тоже не умещается :)
А чтобы уместилось, нужно по-другому решать. Читайте разбор. ;)
Всё уместится. Просто нужен хороший интернет.
Ага. Помню этот коммент :D
У меня зашла жадность — если есть локальные минимумы, то брать их, иначе брать элемент с максимальной стоимостью (т.е. за который дадут больше всего очков).
Причем нестрогий локальный минимум. Вроде бы даже несложно доказать, что данная жадность эквивалента решению из разбора.
Да, если строгий, то WA10. Спасибо претестам, которые это ловят — иначе я получил бы вместо -105 примерно... -105 :D
Внезапно оказалось, что это решение вообще за линию и пишется в несколько строчек: 6924410.
Гена сдал задачу про себя (E). Причем оказался единственным.
Из серии "сделай сам и научи других".
How do you solve Div.1 B ? I see lots of people have solved it. I myself submitted something that will definitely get TLE on system testing. The solution eludes me. :/
sort by decreasing values and greedy algorithm
Can you prove this solution?..
The editorial's up, and the solution's there. Key idea of the solution: if a set S has
, adding p to it increases the result proportionally to p (so we want to add the largest p).
dp[i][j], i — all taken count, j — last taken
[ Deleted ]
Ive got an easy idea for that ... but waiting until the final test :D
Editorial please...!
Скучаю по взломам(((
I hope system testing and rating update come quickly
Hard contest...please give editorial soon.
Интересные, но ОЧЕНЬ сложные задачи. я так ничего и не решил((
Нормальная тема для "я первый раз в Див 1" :-)
С точки зрения сухого рейтинга ты гораздо более в выигрыше, чем те, кто решили одну.
Не понимаю, как А div. 2 пустили на контест. Совершенно безыдейная задача.
Вроде как уже долгое время div2 A — безыдейная задача.
Не понимаю, как кацапов вроде тебя пускают на контест?
Давайте пока разбора нет, я спрошу про Е (див 1). Можно ли ее решить перебором одной вершины (которую выкидываем), для оставшихся точек строим диаграмму Воронного, по диаграмме находим точку внутри прямоугольника, самую дальнюю от оставшихся?
как это нет разбора?
Пока писал и отправлял коммент, разбора не было.
а это http://codeforces.com/blog/entry/12739 что?
Problem C (div2) is hard to understand.
Can anyone give me solution for problem D div2 ?
Can anyone give me solution for problem D div 2?
See editorial
I am in the same room with you~ how lucky~ When you hack others.. I felt quite scared!!!!!!!!
Well, your solution was safe... which can't be said about GodDammit. Hacked after lock, early on in the contest. Talk about choosing a bad name :D
It is so hard to become International master....sad....2049.....
the system testing is very quickly! good
Сегодня кацапня победила меня, но я еще вернусь и покажу кто на цф-е альфач!!!!
Как решать задачи, не зная, как их доказать:
0. Видим, что все сдают, паникуем.
1. Пишем жадное решение.
1.1. Вспоминаем о контестах, когда надо было дополнительно посортить массив, чтоб заработало.
2. Сортируем.
2.1. Упс, не прокатило.
3. Ну тогда сортируем и разворачиваем.
4. ?????
5. PROFIT!
А если серьёзно, как доказать, что такое (6920862) решение всегда даёт правильный ответ?
Читай разбор, там написано:)
Отличный способ решать задачи=)
Я ещё ради интереса в середине контеста посмотрел в див. 2, а там 200 прошедших претесты D и всего 13 C... Да, это был день полный новых впечатлений.
Впервые, упоминание подобной методики увидел на алголисте:
http://algolist.manual.ru/olimp/poi_sol.php
С тех пор часто к ней прибегаю =).
Думается мне, что нужно намешать эти методики и выдать свой ТРИЗ с блекджеком и шлюхами)
Напомнило
Ну ты пока что напиши здесь какой-нибудь бинпоиск, а я за это время попытаюсь придумать нормальное решение...
Damn, why TL in D was so strict :/? My O(n log n) failed and I ended up on a 171st place instead of in TOP20 :/. Moreover, I wasn't the only one. There are many failed submissions because of TLE.
Same here. Got TLE for pascal solution 6921143. The same code receives AC in 390 ms on Delphi: 6923185.
Our Java solutions work something like 500ms... I don't think 4xJava solution time limit is strict.
Are you sure? This is ~1/3 of all submitted solutions during contest.
(Edited picture, thanks nic11)
Maybe
You can post the pic in HTML, you can resize there.
You can look at Aksenov239 solution: 6923989, or mine 6923978 with classes and recursion. Both of them work quite fast.
If you can't see this submissions, you can view it on pastebin: mine and by Aksenov239.
I don't know exact shape of testcases, but solution described in editorial does something like "do something until something" which can be estimated by O(n log n), maybe maxtests where easy cases where your solution worked faster? My solution works offline and takes teta(n log n) time and I'm not using anything which can make constant to significantly grow like set or maps. My space complexity is also O(n log n), but that shouldn't be the case. Is there anything really stupid I'm doing, which was a reason I got TLE http://codeforces.com/contest/442/submission/6917926 ?
And one more question — what is the point of setting such big constraints? Will anybody get hurt if n<=10^5 instead of 10^6? I guess not.
We have maxtests on which model solution works teta(n log n). Setting smaller limits always increases chances some solutions with wrong complexity pass.
But I'm really sorry that I forgot to include a maxtest in pretests.
Sometimes, it's impossible to make sure just all solutions with good complexity pass. As was clearly the case here...
I'm glad that swistakk solution got TL. And I will get hurt if coders like swistakk take top20 place.
Lol, that's pretty rude :P. I guess this is my award for whining about TLs while I should be grateful for preparing contest, but you know, receiving TLE in solution with optimal complexity (especially those without any complicated data structures) is always frustrating :P
Would you also get hurt if coders like me get second place on ACM ICPC WF ( ͡° ͜ʖ ͡°)?
I got TLE because I stupidly used heap to maintain 2 maximals and use cout to output.
I think the TL is fine, but it would be better to add maximal test case in pretest so we will know the code is not optimal enough.
Hm, I got AC after changing vectors to arrays (and 1e6 to 1e6 + 5 :P). I guess what's taking most of the time is doing n resizes to 23 and 23n resizes to 2 :P. I was also really close to exceeding memory limit (230 out of 256MB). Allocating that amount of memory is slower than I wanted it to be.
Поразительно похожие посылки у двух участников сразу по двум задачам: по С 6919815 и 6919490, D 6921687 и 6921824.
В третий раз одинаковый код по С(Div2) 6919367 и D(Div2) 6921882.
Вот не лень же вам все это искать!
My solution of D div2 failed in test case 5 because i didn't use setprecision :(
Many many people missed D because of this :(
In the Ukraine and Russia this coders are named "Loh" or "Noob".
Many People missed that the error was 10^-9 and not 10^-6.
I feel that to give credit to the right technique for problem B (div1), the constraints should've been such that n < = 105
P.S.: After sorting the array of probablities, I just used a naive test-all-subarrays algorithm which passed.
Your O(N2) Solution couldn't pass N = 105 ;)
Anyway , I see the O(N) solution, I think 100 has been chosen nicely by author ... cause nobody have 105 firends who set problem !!!!
Mike Mirzayanov? :D
"Your O(N2) Solution couldn't pass N = 105 ;)"
-- This is precisely why I said that the constraints should be increased. I did not find the O(N) technique and was still able to solve it.
--I don't even feel like replying to what you wrote later on man. I'm out.
А когда мне рейтинг добавят, ребят? Ура! Я блакитный!
Ого, я до сих пор оранжевый. Когда потерял на А 20 минут, т.к. написал в одном месте > вместо >= и потом вообще не имел идей по В, думал, что пришло время возвращаться домой в фиолетовые.
Красавчик, бро!
А тут ничего так :-) У меня серия — второй контест подряд косячу сортировку массива.
Да ладно, ты-то фиолетовый? Ты ж пишешь статьи о сложных структурах данных.
Мало ли кто что пишет Оо
Div1 — B I got wrong answer at test 17.
only for this line : printf("%.10lf\n",1);
Some of you will be amused to see the output
my WA code
my AC code
shit happens :D
Printf expects double, you pass int. It's because of the compiler.
When I passed pretests on Div. 2 B, I thought I was the luckiest guy in the room(I was just playing with the code and it started giving right answers :D). Didn't pass the systest though...
Can someone suggest a book to study algorithms please? Which books did you use to learn them? Both Russian and English ones are acceptable ;)
Introduction to Algorithms by Cormen and other guys is my favourite one, although I've read only DP chapter...
thanks
Hi, In Div 1 — B I got wrong the case #31, however when I run it locally it works fine and give the correct answer. Does somebody now where may the problem be?
Have no idea why that is a problem, but after doing the following, it worked:
Thanks, I had always though that double and long double were identical in GNU C++!. I find rather surprising the huge difference between the result in one case and in another. Well next time I'll use long double if I can remember it!
You're welcome.
But have you got any clue to why the output is like that when using "double"?
And the more weird thing is this. I don't think it's a mere precision problem (not sure): http://ideone.com/31XMxJ
Anyway, I haven't looked carefully at it yet. Will probably do that on Sat. isA.
And something that may help explain the reason but haven't tried before is checking the assembly code outputted from the compiler. But of course, don't forget to use the same compiler & compiler flags as theirs. (Sorry if it's a noob note, I'm a little nooby so I assume everyone is like me :D)
More or less I have finally found it. It has something to do with he -O2 flag it seems to handle some comparisons in a different way, I suspect that it doesn't save mx to memory so it uses a value with more precision (long double?), which is lost whne saving to memory. The question is that the order in the priority queue is changed. But now for equal values of the first parameter the queue gives the result in reverse order which is wrong.
Possibly in your ideone output, when printing the output mx is saved into memory and that affects i's precision. (Well is an hypothesis)
So it is a bug in my code. That's good I don't want to lose my faith in GCC !! :-)
Yeah can some one tell me what is wrong with his solution?
В Div1 вначале во вкладках с условиями сбоку отображалась неправильная разбалловка, потом в какой-то момент она стала правильной (когда мне пришлось обновить вкладку с задачей где-то в середине контеста), вот пруф
Номер раз
И номер два
Более крупно, если нужно: раз, два
так там всегда данные обновляются после обновления страницы
Речь о том, что на первом скриншоте у В макс стоимость 1000.
Ага, а у D -- 2500. Короче, вначале была разбалловка второго дивизиона
В div2 тоже какое-то время разбалловка была неправильной. Помню, что за B и C было написано 1500.
Почему это (6916735) правильно?
В частности, вот это:
Потому что если длина строки меньше, чем количество символов, которое можно добавить, то в ответ можно включить всю строку + еще сиволы. Ибо именно ты решаешь, какие символы добавить.
Div1B / Div2D решается за линейное время http://codeforces.com/contest/443/submission/6928411, мне кажется ограничение N <= 100 слишком маленькое, вполне можно было сделать побольше.
I have some understanding problem about div1 D. About the 2 conditions, what I think are:
Am I understand the 2 conditions right? And how does these 2 conditions affect the problem ? Thanks.
Round Stats