Привет всем!
Раунд Codeforces #165 начнётся сегодня в 19:30 по Московскому времени, и будет проведён в обоих дивизионах. После долгого двухнедельного перерыва это первый раунд для участников Div I. :)
В этот раз задачи подготовили я, Евгений Вихров (gen), и Кришьянис Прусис (cfk). Кроме совместного участия в ACM ICPC в этом году, мы также коллеги по проекту с множеством алгоритмических задач. Некоторые задачи раунда появились именно во время работы над этим проектом.
Во время контеста вы познакомитесь с легендарным героем Эмускальдом множества талантов и поможете воплотить в жизнь его гениальные замыслы. Задачи покрывают большое количество алгоритмических идей, поэтому, как всегда, мы надеемся, что каждый найдёт себе задачу по вкусу.
Большое спасибо Геральду Агапову (Gerald) за помощь в подготовке раунда, Марии Беловой (Delinur) за перевод условий, а также Михаилу Мирзаянову (MikeMirzayanov) за великолепную платформу создания контестов на Codeforces — Polygon.
Мы желаем всем интересного раунда!
UPD1: Разбалловка задач:
DivII: 500 1500 1500 2000 2500
DivI: 500 1000 1500 2000 2500
UPD2: Поздравляем победителей!
Div I
Div II
UPD3: Появился разбор.
Нормальный был вопрос....
Пока что ещё не решили.
Поставьте динамическое! С ним интереснее.
… Интереснее сливать вклад, предлагая его :D
"РаспредЕление" от слова дЕлят. Учи язык.
Так-то проверочное "дЕлят" (ударный), ну да ладно.
Здесь гуманираиям не место!!
Свой родной язык должны знать не только те, кто занимается гуманитарными науками!
Мой родной язык не русский...
I love contests !!
Эх, чувствую контест будет интересным, жалко пропускать :(
Думаю контест будет не простой!
Прошлый его контест был легкий и интересный.
Remarkably the two of our problem setters Evgeny Vihrov (gen), and Krisjanis Prusis (cfk), have exactly the same rating, besides being project mates.
Всем удачи!!!
求轻虐>_<
why is the handle changing item removed???
So slow... Handle changing has opened in first 10 days of New Year.
Another rated contest for the div1 contestants after 2 rounds.
JUST HAVE A FUN!
По описанию контеста кажется что он будет довольно интересен. Надеюсь так и будет)
Ideas generated from project, I am pretty sure that problem statements will be long. :( .
I was wrong. Problems were short in length. Nice.
What will be the point distribution ?
Это будет мой первый див-1 раунд, надеюсь не слиться в синие)
Надежда умирает последней. :3
Аналогично!
Triple kill
Высокого рейтинга!!!
After a little break, I'm going to write today's contest... Good Luck
Ух долгожданный кодефорс всем удачи!!!
Прошлая задача про треугольники обрадовала. Надеюсь и сегодня обрадуете.
Будут задачи про другие фигуры. :)
"the first one after a long two-week break for Div I participants."
This touched the bottom of my heart...! :D
Интересная разбалловка Div II.
I haven't wrote contest almost 2 years
Well ,you seem to be in shape.
для див 2 задачи обещают быть интересными
Уже в сумме 3326 участников) Вот это рекорд!
Ну если учесть что не все Div I пишут Div II, то это не рекорд)
все ок))
WOW number of registered in Div1 reached 850
Что означает вердикт: "Ошибка исполнения"?
Ето означает что у тебя прога не работает
"Ето"
В очереди уже 3 минуты — не к добру...
сейчас длина очереди достигла почти 7 минут.
is something wrong with the judge or this is normal??
This contest should be declared unrated as the server was down for a long time as well the verdicts came late :\
Тупой контест!
Только стал синим и всё!!!!!!! Капец
I hope it'll be declared unrated
Кто знает, как решалась C(div. 2)/A(div. 1)?
Одно из решений: Перебираем ответ бинарный поиском, а для того чтобы проверить могут ли влезть все коробки, достаточно проверить для текущего, влезают ли каждый тип прямоугольников в эту перебираемую коробку.
Бинарный поиск не нужен, потому что в коробку размера M + 15, где M-максимальный размер коробки из инпута, гарантированно все влезет. Это так, потому что в коробку размера i помещается 22(i - j) коробок размера j.
Даже лучше, хватает проверить только коробки от 2maxk + 1 до 2maxk + 16, так как количество их до 10^9. ;)
Спасибо за объяснения.
У меня все проще — я просто отсортировать массив забыл.
Я решил немного по-другому, для каждой типа искал минимальный размер коробки, чтобы все данные коробки этого типа вместились, и выбрал максимум в качестве ответа
Да, такое и оригинальное решение.
Можно решить, используя логарифмы.
What is the notorious pretest 4 for problem A in div 1?
1
3 1
Answer : 4
Even simpler,
1
0 1
I also think the answer is: 1 Could you help me explain it?
wow! Didn't notice the "strictly less"... Back to division 2 then, I guess :D
UPD. understood
Through out the contest I considered that the largest box could have been used as the final packing box and so I output 3 to the above case. And Now I read "He has decided that the best way to pack them would be inside another magical box" :(
The correct reason is "strictly less than" not "another".
I personally interpreted the problem as ->if the largest box can fit in all other boxes, then why go for an even larger box and not take it only. So for me, the reason is "another". Dont know about others.
Hey there, i had the same problem too. Turns out i did not read the problem statement carefully. :(
Прошу помочь найти ошибку в решении задачи C Div-2. Решение UPD: нашел ошибку
Первая найденная мной ошибка: переполнение int32 при возведении его в степень.Я не прав.Насколько же хитро автор замаскировал наибольшую неубывающую подпоследовательность в В... А в целом задачи понравились.
Today I couldn't hack from Firefox (the popup window didn't move and "Hack" button was below the bottom of the computer screen).
I experienced this before. Click 'Tab' several times until the hack button is highlighted, then click 'Space' or 'Enter'.
yup,i can never hack from chrome,the same problem,i have to use IE -_-
IE?! :)
What can IE do except making your system stop working? :)
You can press F11 and "hack" button will be seen.
I came across the exact same problems several times on Google Chrome before.
You can also decrease the scale of the page content until you'll be able to click the "Hack" button.
Задача C. Не знаю, как народ в общем, а я не впер, что он обязательно должен создать коробку... Либо я тормоз, либо условие странное :( Скорее первое, но все равно обидно. Я думал, если все влезает, то крутяк. В общем решал другую задачу
1) Ларец v можно положить в ларец u, если длина стороны ларца v строго меньше, чем длина стороны ларца u.
2) Помогите ему найти наименьший волшебный ларец, в который можно поместить все его ларцы.
Очевидно, что ларец, в который он положит все свои ларцы, должен быть больше наибольшего из ларцов.
Hey , i was getting badway 504 in last two minutes of contest. And in the last two minutes i was waiting to submit my solution to 3rd but couldnt do it due to that 504 error. Please Please please consider my solution for C now as i had completed it in time ,else it will be unfair .
I vote for considering his solution and I'm not afraid of negative feedbacks ^_^
sorry mate , It would have got run-time error, max size of box is set to 50 :P
anyway you got Wrong Answer.
Yepp, i know , there was a correction in the 2nd last line , instead of divisoion by two , square root would have come ^_^
no, whole your code is wrong.
you need to solve the problem without using pow or log because of big constraints
I mean, seriously, are those statements supposed to explain the problem, or confuse it even more??
Sorry, they were shorter in the beginning, but we had to explain some subtle things and they grew in size... :/
I am not talking about length, I am talking about how much useful the information you put, was aiming make clearer the task itself. Let's mention for example the task Div2 B, the definitions of updated or not are so misleading.
And this coordinates in Div1B ; /... I've read description 5 times to be sure that these coordinates are just a mislead :d... Not a funny joke, but pretty confusing :d
Why do you think it is a joke? Determining what data do you need is an important part of solving a problem.
Also, I think that all statements were rather clear and unambiguous. (Div2 at least)
I can understand that can be frustrating... But there were reasons for coordinates:
Anyone, who isn't a monkey, will immediately know that if you can replant them into any real coordinate (what was clearly stated in description), exact coordinates are redundant. Putting something like that in the description won't take any positive effect. It causes thoughts like "Either I am dumb or author thinks that I'm dumb". Reading the description few times took me more time than solving+coding :/
That wasn't the intent. :D But I'll try to make short and clear statements in the future, this time it just was an experiment for us to write extended legends about one hero.
So, in your opinion reading the task is not included in solving it. I would beg to differ. Understanding the statement is a first step in solving every task. Hence, if you rushed too fast or haven't done it well — sorry, there's no one to blame except you (except if the statement was way to unclear, but it's not the case here in my opinion). Well, I have seen quite a lot of tasks where some information doesn't matter — it's your task to decide what you need and what you don't. Some perfectly valid tasks could even be one-liners, where all you need to do is to understand the statement. Why not?
You're all talking "determining which data is important" is a part of solving task. But in this case this was so obvious and it hasn't caused effect "Oh! I'm so smart, I figured out that this coordinates are not important! Such a nice result!" but "Probably I didn't read description carefully, because it would be too obvious if those coordinates really were redundant."
Несколько комментариев по поводу DIV-2:
Тут ответ.
Посмотрите вот этот тест:
Входные данные:
1
0 1
Выходные данные:
1
Ответ тут должен быть 0
Всё, понял, понял...
Единственно необработанный случай... как обидно...
u mean :
n . . ,
max 1 ( for case when previus in max box < but it need max+1 size)?
Почему валится поиск в ширину в С див1 ?
Должно проходить, может быть кладёте в очередь сток?
Затупил :(
Мда, вот это фейл. Я стоку присвоил 10^9 и подумал, что ровно столько в него не втечет. Оказалось, что втечет, да и еще так точно.
Да, был и такой тест. :D
сорри...
"...Некоторые задачи раунда появились именно во время работы над этим проектом." Всем желаю такой интересной работы:) Спасибо за классные задачи!
My solution for problem C wasn't rated. http://codeforces.me/contest/269/submission/3052470
Tyle przegrać!
I still don't get point for my solution ;/ It is correct. I resummit it and i get AC.
Интересный раунд. Разбор задач будет?
Из-за нехватки времени мы ещё не сделали, но завтра будет. Пока можно поломать голову над Е. :)
I think Test #12 in problem C is wrong, because "If there are several solutions you can print any of them."
Edit: Sorry guys i get it!.
But the sink will be node 2, the problem specifically says that the sink is node n.
"Vertices 1 and n being the source and the sink respectively."
In this problem, there cannot several solution because there cannot appear cycle.
What's the idea behind div1-B and div1-C?
Div 1 B-> Just have to take out the Longest Non-Decreasing sub-sequence(k). Since you can move plants to any real co-ordinate, there are plenty of them. And the answer becomes n-k
Can you tell me what the coordinates which given in the input used for?
I believe they are just to trick you into thinking you need to use them ;D
I can't understand why the coordinates are given in problem div1 B
"Because fuck you" :P. Poor joke. Just to mislead contestants ; /
You don't need those co-ordinates to solve the problem
Well they matter because the plants need to be sorted in ascending order in order for N — LIS to work.
Yes, but they are already sorted on input.
На дорешивании div2 C не проходит 15 тест, причем он запущенный у меня локально выдает правильный ответ. Моё решение (с++11): http://pastebin.com/CXxCDx9V Протокол тестирования: http://pastebin.com/8j5BV3q5
Запуская у себя получаю верный ответ 14. Компилировал clang++ и g++46 — всеравно 14, почему на сервере тестов получается 15?
вероятно, дело в неточности даблов
Люди, объясните, плиз, почему решение 3051832 по задаче В прошло, несмотря на то, что в цикле там может быть обращение к -1 элементу массива и выход за его границы.
Потому что выход за границы массива в С++ — не обязательно Runtime Error, чуваку повезло
Hi. Does anyone have any idea how the code in below could work correct in my computer and get WA on pretest 2 on CF? I checked it with MS and GNU and they gave Compilation Error and WA on pretest 2 respectively. here's the code: 3060066 thanks.
Can anybody tell me what were the bugs in Div1 C, which weren't detected by pretests, what caused so many succesful hacks? I'm pretty curious about that.
When we use BFS we shouldn't add vertex number N to the queue. You can view test 12, it is quite small.
link to editorial please?
In the Russian thread gen has said that it's not ready yet, so it'll be tomorrow.
thanks for nice problemset. I realized I shouldn't pass a round even if its writer is Purple.
Thanks, glad you liked it!
Доброе утро. Подскажите, когда будет выложен разбор задач?
В процессе, сегодня должен быть.
Testcases in Div2.C are not strong enough.
My code got AC, but fails on this test:
link: http://codeforces.me/contest/270/submission/3062842
BTW, if youare interested why it fails look at this line:
ll xarisxi = pow(4, 1.0*(V[i+1].first-V[i].first));
where I calculate 4 to the power of the difference between two quantities of boxes.Congratulations to kelvin to be the first participant who has successfully upsolved the hard problem 269E - Теория струн: 3062253!
Thank you for the congrats and for preparing a great contest! During the contest, I was very happy to find out that I know how to solve the hard problem, but equally sad when I (after 30 min or so) find out I probably cannot finish it in time :p
Div 2 was really good and amusing contest , questions were just so cool , i loved solving them , thanks gen :)