Hello everyone!
Codeforces round #165 will start today at 19:30 in Moscow time. It will be a round held in both divisions, the first one after a long two-week break for Div I participants. :)
This time the problems were prepared by me, Evgeny Vihrov (gen), and Krisjanis Prusis (cfk). Apart from competing together in ACM ICPC this year, we are also colleagues in a project that involves much algorithmic thinking. Actually, some of the contest problems were born during the work on this project.
In this contest you will get to know a legendary hero Emuskald of many talents and help him complete his ingenious ideas. The problems cover a multitude of algorithmic concepts, so as always we hope that each participant will find a problem that matches his taste.
Big thanks to Gerald Agapov (Gerald) for help during the preparation of this contest, to Maria Belova (Delinur) for problem statement translation and also to Mikhail Mirzayanov (MikeMirzayanov) for the excellent contest-making platform for Codeforces — Polygon.
We wish you an exciting round!
UPD1: Score distribution:
DivII: 500 1500 1500 2000 2500
DivI: 500 1000 1500 2000 2500
UPD2: Congratulations to the winners!
Div I
Div II
UPD3: Tutorial is available.
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.
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 ?
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
I haven't wrote contest almost 2 years
Well ,you seem to be in shape.
WOW number of registered in Div1 reached 850
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
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. :(
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.
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."
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.
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 :)