Привет, Codeforces!
25 декабря 2015 года в 18:00 MSK состоится четвертый учебный раунд Educational Codeforces Round 4 для участников из первого и второго дивизионов. С прошлого учебного раунда в этот раз прошло всего ничего. Несмотря на то, что проведение раунда мы спланировали ещё в понедельник, мы почему-то забыли включить его в расписание, поэтому в расписании раунд только появился. Таким образом, это уже четвертый и последний в этом году учебный раунд.
<Эти два абзаца может быть никогда не изменятся>
О формате и деталях проведения учебных раундов я писал уже ранее. Также об учебных раундах вы можете прочитать здесь.
Раунд будет нерейтинговым. Соревнование будет проводиться по немного расширенным правилам ACM ICPC. На решение задач у вас будет два часа. После окончания раунда будет период времени длительностью в один день в течении, которых вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования. Таким образом вы можете локально тестировать решение, которое хотите взломать, или, например, запустить стресс-тест.
</Эти два абзаца может быть никогда не изменятся>
Подготовкой задач в этот раз занимался только я (Эдвард Давтян). Пока благодарю, только MikeMirzayanov мы вместе придумывали задачи. Через некоторое время здесь появится благодарность тестеру. Также заранее благодарю Машу Белову Delinur, которая вычитает английские тексты условий, когда они появятся :-)
На этом раунде вам по традиции будет предложено шесть задач. Думаю задачи в этот раз будут немного проще, чем обычно. Это связано с тем, что исходный комплект задач оказался чересчур сложным, поэтому мы убрали самую сложную задачу (она скорее всего будет самой сложной на следующем раунде) и добавили очень простую задачу. Надеюсь комплект задач вам понравится и вы решите все задачи!
Поздравляю всех с наступающим новым годом!!!
Good luck and have fun!
UPD 1: Первая фаза соревнования закончена, ломайте решения соперников!
UPD 2: Опубликован полный разбор задач.
Merry Christmas, friends!
I think that Tests on the first day must be weaker to Increase the number of hacks... Last Educational Round had strong tests on first day...
number of hacks should be increase by weaker pretest.
correct
I think that hacking on educational rounds is meant to strengthen the test data, not to test your abilities with hacking. Otherwise the test data would have been called pretests.
I love the end of the year because it is full of contests :D
>end of the year
>only because full of contests
>sees username
Alright, checks out.
my friend annoying me.. :| sorry
I didn't mean it to be offensive by the way :3
happy new year!!!!! best wishes for you!!!! :D
Сделайте уже рейтинговым, что ли
Чем больше плюсов на комментарии выше, тем ближе Новый Год!
На следующем раунде = "раунде 337 для второго дивизиона" или "предновогоднем совмещенном раунде"?
мне кажеться на educational round 5
Да ты прав.
me at cf educational round
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░░░░░░██░░░░░░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░░░░██████░░░░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░░░█████████░░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░████████░███░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░█████████░░███░░░░░░░░░░░░░░ ░░░░░░░░░░░░░███████████░░░██░░░░░░░░░░░░░ ░░░░░░░░░░░░██████████░░░░░░██░░░░░░░░░░░░ ░░░░░░░░░░██████████░░░░░░░░░██░░░░░░░░░░░ ░░░░░░░░░░█████████░░░░░░░░░░░██░░░░░░░░░░ ░░░░░░░░░█████░░░░░░░░░░░░░░░░░██░░░░░░░░░ ░░░░░░░░████████░░░░░░░░░█████░██░░░░░░░░░ ░░░░░░░░░░░███████████████████░░░░░░░░░░░░ ░░░░░░░░░░░████████████████████░░░░░░░░░░░ ░░░░░░░░░░██████████████████████░░░░░░░░░░ ░░░░░░░░░████████████████████░░██░░░░░░░░░ ░░░░░░░░████████████████████░░░░██░░░░░░░░ ░░░░░░░████████████████░░░░░░░░░░██░░░░░░░ ░░░░░░████████████░░░░░░░░░░░░░░░░██░░░░░░ ░░░░░████░░██░░░░░░░░░░░░░░░░░░░░░░██░░░░░ ░░░░███████░░░░░░█████░░░░░░█████████░░░░░ ░░░░██░░████████████████████████░░░░░░░░░░ ░░░░░░░█████████████████████░░░██░░░░░░░░░ ░░░░░░███████████████████░████░░░██░░░░░░░ ░░░░██████████████████████░░░░░░░░░██░░░░░ ░░██████████████████████░░░░░░░░░░░░███░░░ ░███████████████░█░░░░░░░░░░░░░░░░░░░░██░░ █████████░█░░░░░░░░░░░░░░░░░░░░░░░███████░ ░░░░░░░███░░░░░░░███████░░░░░░██████░░░░░░ ░░░░░░░░███████████████████████████░░░░░░░ ░░░░░░███████████████████████████░██░░░░░░ ░░░░██████████████████████████████░███░░░░ ░░░█████████████████████████████░░░░░██░░░ ░░█████████████████████████░░░░░░░░░░░██░░ ░█████████████████████░█░░░░░░░░░░░░░░░██░ █████████████████░█░░░░░░░░░░░░░░░░░░░████ ░░░░░███████████░░░░░░░░███░░░░████████░░░ ░░░░░░░░░░░░░░░░███░█████░█████░░░░░░░░░░░ ░░░░░░░░░░░░░░░░████████░░░░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░░██████░█░░░░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░░██████░█░░░░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░░█████░░█░░░░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░░████░░░█░░░░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░░████████░░░░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░ ░░░░░░███████░░████████░░██░░███████░░░░░░ ░░░░░░░░░░░██░░██░░░░██░░██░░██░░░██░░░░░░ ░░░░░░░░░░░██░░██░░░░██░░██░░██░░░░░░░░░░░ ░░░░░░███████░░██░░░░██░░██░░███████░░░░░░ ░░░░░░██░░░░░░░██░░░░██░░██░░██░░░██░░░░░░ ░░░░░░██░░░░░░░██░░░░██░░██░░██░░░██░░░░░░ ░░░░░░███████░░████████░░██░░███████░░░░░░ ░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░
HAPPY NEW YEAR !!!!!!!!!!!!!!!!
My whole life.
*Christmas. I know, ok? :D
Chrismas?
Happy Halloween and Happy Solving!
Are you on internet explorer?
Happy Merry Christmas! Good luck !!!!
I am happy because Christmas is on the way
I am happy because Christmas on the way
Problem A : WA on test 9 :(
Very poor English.
I think problem B is easier than problem A .
Imo, its not easier to implement, but its easier to understand statement :)
UPD: Actually, after checking my code, it seems B is easier in implementation too...
How is problem C solved? I think checking whether a given string is "good" is easy, but I was stumped with the actual problem.
just useing stack
It's just as easy. You can never change opening brackets and only change closing brackets to make them match. Then you just go as the regular check with a stack, if you get an opening bracket you push it in the stack, if you get a closing bracket you pop the top of the stack. If the closing bracket doesn't match the top of the stack then you increase your changes by 1.
Why is the answer of [{>} not 1?
because [ { ] } is not an RBS .
check the definition of an RBS in the problem statement .
OMG thats tragic... :( Can't believe I missed this.
Just being greedy. Since you can't make a bracket type correct string out of a bracket type mismatch string (with the limits in statement), the only thing you can do is fix the bracket kind mismatch. The absolutely correct ones shouldn't change, or you'll make the answer worse. As for the kind mismatch pairs, fix any one of them, that will work.
Можете объяснить задачу D?
Эдвард Edvard Давтян в поте лица уже пишет разбор:
ooo спасибо. Теперь можно увидеть кто сколько взломов сделал
Эмиль задача похожа на задачу http://informatics.mccme.ru/mod/statements/view3.php?id=634&chapterid=641#1 разбор и код к задаче http://cppalgo.blogspot.com/2010/11/6.html
Спасибо Нурбек ))
I didn't notice that the round will start at 18:00 instead of 18:05 so I missed the first five minutes.
Well it's unrated and educational so 5 minutes shouldn't matter.
yes, I'm just saying that it's better to mention that there's no +5 in the announcement next times
Each email has exact time when contest will start. Also there is countdown in sidebar and contests page.
ICPC-style contests do not have rooms, so we do not need 5 minutes for delay between end of registration and contest start.
I don't rely on emails, and for the countdown I only used it to compute start hour but not the exact time, that's what happened with me.
I'm not complaining since it's not big deal, I was just saying that such things might happen so in the future if you decided not to make the +5 delay in the rated rounds it's better to mention that in the announcement.
Codeforces team introduced contest time in local timezone. No more complaints :D
I know that feel
Editorial will be available today or after hacks phase?
It will be today.
Russian editorial is already available here
Couldn't get a clue about problems D and E any pointers from people who solved them ?
Any hints for E?
D and E were completely new to me ... hints about D too would be appreciated
D was somewhat simple. Just do a line sweep from right to left.
The whole time i was thinking of a way to solve with segment tree, i think it's about time i read up on line sweep.. thank you
Hint: convert a permutation into a graph or a cycle notation. (For example, if you have [1 3 2], write a graph with edges from 1 to 1, from 2 to 3, from 3 to 2) and before thinking about how to find a square root of permutation, observe what happens when you square a permutation. Another hint: it has something to do with the parity of the length.
How is Problem D solved?
How to solve problem E ?
Edit: I was wrong, I am sorry if I have misleaded any of you.
Привет. Вопрос по задаче D.Кто может объяснить, почему меня TL 19? Вроде я решил как все за O(nlog(n))
Медленный ввод/вывод, попробуй позаменять cout/cin на printf/scanf. По крайней мере у меня из-за этого падало с TL 19.
My solution to problem D has the max complexity at sort but still get TLE test 19. 15018905 Is that because the memory is too large or sort sometimes can reach O(n^2) ? Can anyone help me ?
It's not the problem of sort(), it's the problem of your I/O method.
Using cin/cout will lead to a dramatically long excution time when facing such huge test cases. scanf/printf is strongly recommanded here.
15019648
I made a change on your I/O method, and it's now WA on test 19 with ~600ms. Hope you can figure the problem out.
Thank you so much, I didn't know using cin/cout would slow down the program so much :((
I also got TLE, on the same test case, see 15016054, i did it in Java. I noticed that Egor has custom input and output streams. How can i set these up with IntelliJ, CHelper plugin?
Can someone help me with D?
Current idea that gave WA#20: if segment is given as (L, R), put (L, 0) to vector and (R, 1) as well. Then sort, and check when interval is opened and when is closed. Meanwhile checking if total number of opened intervals is >=k.
UPD: I found out mistake.
Was your implementation buggy or the algo?
The algo passes the preliminary test cases. I used the same idea.
I missed endpoints where segments == k
I checked =k instead of >= k
good if the Educational round had (div.1) and (div.2) :-)
good if the Educational round had (div.1) and (div.2) :-)
Maybe 3 hours will be better?
Damn, get the idea in D, spent 1.5 hours implementing it and finished 5 mins before the end with correct algo, but TL.
Contest over, got totally different idea and now it is AC. Spent 20 mins.
Aggrhhh! First one was too complicated so I can't evaluate complexity for it, but felt like "good enough". Second one was obvious O(N * log(N)).
BTW, got hacked with my new solution because of not perfect I/O. Fixed now :)
mine was even worse .I thought towards the middle of the contest that I would not be able to do D so took a break.While there were 20 minutes left I came back and thought over the question for a while.An idea struck me 10 minutes prior to end of the contest and I frantically coded this and submitted with 40 odd seconds left .Result WA on case 1 (there was no time to run on local system). I was debugging the solution half an hour back and here is the correct one. If you compare the codes you'll see that there is a difference of a single character. I wrote '=' instead of '==' in an if condition.**FACEPALM**
I don't know why some members like to enter the contest virtually and submit prepared solutions one after another just to get high rank. It is not competitive anyway.
What's even worse is that sometimes the solutions submitted are not even theirs.
What's even worse is that some people add a false special test in their code and try to hack it later .
really people !!
mind=blown
I have a question about the problem D.
For this test case:
The answer is
How so, if the point 3 is located on the two segments?
The acceptable condition is ">= k", not "== k".
My bad, forgot about that. Must be because of the pressure from the possibility of my solution getting hacked. :P
Hi!
I'm trying to hack a solution that should get TLE in a strong case, but you don't permit me to upload the test case (It's too heavy).
For problem D, I used compression, but TLE on test #16, can anyone explain why?
Code
I believe your solution is of complexity O(N^2), even after compression.
Can you point out that mistake please?
I believe its just wrong approach. You have O(N^2) complexity when filling axis array — every segment could have the length of N. So with N segments, each one length of N you will get O(N^2) right away.
Your algorithm is correct (I think) but it's too slow.
There you iterate over every segment, even after compression segments have length (in the worst case) of 2n, so that part of your code is O(n2), with n = 106 it's too slow
Очень понравилась задачка про квадратный корень из перестановки. Может это и баян, но решения я не знал, но удалось придумать :)
Привет в отсылке http://mirror.codeforces.com/contest/612/submission/15018850 Есть ответ участника, но нет ответа жюри. Ошибка ТЛЕ. В чём может быть проблема? Вывод участника 1 -99999884 99999950
Скорее всего там на грани фола решение, у вас и 19е (на котором большая часть людей свалилась) прошло еле еле — 3946 ms. Там дальше есть и более требовательные тесты.
Проблема скорее всего в медленном вводе/выводе.
UPD: глянул код, похоже таки с вводом-выводом все в порядке, но смущают три используемых HashMap'а. Я предполагаю что для 200000 точек заполняться при чтении они будут довольно медленно. Самое простое и быстрое что можно сделать — это задать им начальную capacity (если в джаве это можно сделать) что бы избежать множественного рехешинга в процессе. А вообще лучше упростить алгоритм и избавиться от них совсем :)
Спасибо. Просто смутило, что ответ был дан, а решение упало с ТЛЕ.
Can anybody explain why this 15030396 got TLE, while this exactly same code 15030456 got AC?
I guess its because software execution time isn't very precise value :) Just improve your code to execute 2-3 times faster and it should be ok.
I would like to report a possible bug. If I go to standings -> div 2 and then click "friends standings" it doesn't do anything.
Мое решение на тесте для взлома получило TLE, хотя на этом же тесте у меня все ок. В чем может быть проблема? Решение.
Is system testing planned? I thought it starts automatically once hacking phase is finished.
Done, great and terrible hacker.
The contest has been rejudged with all the successful hacks. Аpplause to the best hackers!
I think here is a little bug, but I may be mistaking. After choosing "Division 2" I cannot get back to the standings for Both divisions. Also, as already mentioned, if one chooses "Division 1" or "Division 2", then clicking on "Friends standings" shows the "Common standings".
Thumbs up to "recursionishell" test in problem A created by gepardo. Too bad it is not the first test where recursion solution will fail.