### gen's blog

By gen, 7 years ago, translation, ,

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 II

UPD3: Tutorial is available.

• +191

 » 7 years ago, # |   0 i love codeforces short contest's
 » 7 years ago, # |   -27 gl & hf
 » 7 years ago, # |   -41 I love contests !!
 » 7 years ago, # |   +53 Remarkably the two of our problem setters Evgeny Vihrov (gen), and Krisjanis Prusis (cfk), have exactly the same rating, besides being project mates.
 » 7 years ago, # |   -39 求轻虐>_<
 » 7 years ago, # |   -15 why is the handle changing item removed???
•  » » 7 years ago, # ^ |   -6 So slow... Handle changing has opened in first 10 days of New Year.
 » 7 years ago, # |   +1 Another rated contest for the div1 contestants after 2 rounds.
 » 7 years ago, # |   +2 Ideas generated from project, I am pretty sure that problem statements will be long. :( .
•  » » 7 years ago, # ^ |   0 I was wrong. Problems were short in length. Nice.
 » 7 years ago, # |   +5 What will be the point distribution ?
 » 7 years ago, # |   -15 After a little break, I'm going to write today's contest... Good Luck
 » 7 years ago, # |   +11 "the first one after a long two-week break for Div I participants."This touched the bottom of my heart...! :D
 » 7 years ago, # |   +16 I haven't wrote contest almost 2 years
•  » » 7 years ago, # ^ |   +3 Well ,you seem to be in shape.
 » 7 years ago, # |   +2 WOW number of registered in Div1 reached 850
 » 7 years ago, # | ← Rev. 2 →   0 you did a good job！
 » 7 years ago, # |   -8 is something wrong with the judge or this is normal??
 » 7 years ago, # |   -6 This contest should be declared unrated as the server was down for a long time as well the verdicts came late :\
 » 7 years ago, # |   -9 Is answer of example 3 of Magical boxes correct
 » 7 years ago, # |   +12 I hope it'll be declared unrated
 » 7 years ago, # |   +1 What is the notorious pretest 4 for problem A in div 1?
•  » » 7 years ago, # ^ | ← Rev. 2 →   +5 13 1Answer : 4
•  » » » 7 years ago, # ^ |   +5 Even simpler, 1 0 1 
•  » » » » 7 years ago, # ^ | ← Rev. 7 →   0 10 1I also think the answer is: 1 Could you help me explain it? yes, it is true. it can not contain itself.
•  » » » 7 years ago, # ^ |   +2 wow! Didn't notice the "strictly less"... Back to division 2 then, I guess :D
•  » » » 7 years ago, # ^ | ← Rev. 2 →   0 UPD. understood
•  » » » 7 years ago, # ^ |   +1 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" :(
•  » » » » 7 years ago, # ^ |   0 The correct reason is "strictly less than" not "another".
•  » » » » » 7 years ago, # ^ | ← Rev. 2 →   +7 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.
•  » » 7 years ago, # ^ |   0 Hey there, i had the same problem too. Turns out i did not read the problem statement carefully. :(
 » 7 years ago, # |   +41 Today I couldn't hack from Firefox (the popup window didn't move and "Hack" button was below the bottom of the computer screen).
•  » » 7 years ago, # ^ |   +6 I experienced this before. Click 'Tab' several times until the hack button is highlighted, then click 'Space' or 'Enter'.
•  » » » 7 years ago, # ^ |   +8 yup,i can never hack from chrome,the same problem,i have to use IE -_-
•  » » » » 7 years ago, # ^ |   +3 IE?! :)What can IE do except making your system stop working? :)
•  » » » 7 years ago, # ^ |   +4 You can press F11 and "hack" button will be seen.
•  » » 7 years ago, # ^ |   0 I came across the exact same problems several times on Google Chrome before.
•  » » 7 years ago, # ^ |   +2 You can also decrease the scale of the page content until you'll be able to click the "Hack" button.
 » 7 years ago, # |   0 very fast system testing :P
 » 7 years ago, # |   -18 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 . #include #include #include using namespace std; struct logr { double k; double x; } box[50]; bool key(const logr &a, const logr &b) { return (a.k < b.k); } int main() { float min; int n; cin>>n; for (int i=0;i>box[i].k>>box[i].x; sort(box,box+n,key); for (int i=0;i(pow(2,box[i+1].k)*box[i+1].x*pow(2,box[i+1].k))) { min=(pow(2,box[i].k)*pow(2,box[i].k)*box[i].x)-(pow(2,box[i+1].k)*pow(2,box[i+1].k)*box[i+1].x); min=ceil(min/(pow(2,box[i+1].k)*pow(2,box[i+1].k))); box[i].x=(pow(2,box[i+1].k)*pow(2,box[i+1].k)*box[i+1].x)/(pow(2,box[i].k)*pow(2,box[i].k)); box[i+1].x+=min; } } min=pow(2,box[n-1].k)*ceil(box[n-1].x/2); min=ceil(log(min)/log(2)); cout<
•  » » 7 years ago, # ^ |   +1 I vote for considering his solution and I'm not afraid of negative feedbacks ^_^
•  » » » 7 years ago, # ^ |   0 Thanks a lot for support Scientist 1642 :)
•  » » 7 years ago, # ^ |   +6 sorry mate , It would have got run-time error, max size of box is set to 50 :P
•  » » » 7 years ago, # ^ |   0 Bro , okay thats true that i had minor error , but at last my code would not passed the pretests and i would have surely corrected it ;) Anyways nevermind if not revaluvated , i will try to finish faster in next contest :D
•  » » 7 years ago, # ^ | ← Rev. 2 →   0 anyway you got Wrong Answer. 1 10000000 4  1 0 1 
•  » » » 7 years ago, # ^ |   0 Yepp, i know , there was a correction in the 2nd last line , instead of divisoion by two , square root would have come ^_^
•  » » » » 7 years ago, # ^ |   +1 no, whole your code is wrong.you need to solve the problem without using pow or log because of big constraints
•  » » » » » 7 years ago, # ^ |   0 Ooops xDYeah , you are surely correct this time :)
 » 7 years ago, # | ← Rev. 2 →   +10 I mean, seriously, are those statements supposed to explain the problem, or confuse it even more??
•  » » 7 years ago, # ^ |   +13 Sorry, they were shorter in the beginning, but we had to explain some subtle things and they grew in size... :/
•  » » » 7 years ago, # ^ |   +3 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.
•  » » » 7 years ago, # ^ |   -30 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
•  » » » » 7 years ago, # ^ |   0 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)
•  » » » » 7 years ago, # ^ |   +5 I can understand that can be frustrating... But there were reasons for coordinates: Just by looking at the sample, you can tell that one can replant a plant anywhere at real coordinate. The origin of the problem had coordinates also, so they were kept. It is often quite valuable to tell that some data is redundant, and is a good reminder to trust your reasoning.
•  » » » » » 7 years ago, # ^ |   -37 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 :/
•  » » » » » » 7 years ago, # ^ |   +3 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.
•  » » » » » » 7 years ago, # ^ |   +17 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?
•  » » » » » » » 7 years ago, # ^ |   -13 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."
 » 7 years ago, # |   +45 My solution for problem C wasn't rated. http://codeforces.com/contest/269/submission/3052470
•  » » 7 years ago, # ^ |   -26 Tyle przegrać!
•  » » 7 years ago, # ^ |   +11 I still don't get point for my solution ;/ It is correct. I resummit it and i get AC.
 » 7 years ago, # | ← Rev. 5 →   0 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!.
•  » » 7 years ago, # ^ |   +14 But the sink will be node 2, the problem specifically says that the sink is node n.
•  » » 7 years ago, # ^ |   0 "Vertices 1 and n being the source and the sink respectively."
•  » » 7 years ago, # ^ |   0 In this problem, there cannot several solution because there cannot appear cycle.
 » 7 years ago, # |   0 What's the idea behind div1-B and div1-C?
•  » » 7 years ago, # ^ | ← Rev. 2 →   +1 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
•  » » » 7 years ago, # ^ |   0 Can you tell me what the coordinates which given in the input used for?
•  » » » » 7 years ago, # ^ |   0 I believe they are just to trick you into thinking you need to use them ;D
 » 7 years ago, # |   0 I can't understand why the coordinates are given in problem div1 B
•  » » 7 years ago, # ^ |   -38 "Because fuck you" :P. Poor joke. Just to mislead contestants ; /
•  » » 7 years ago, # ^ |   0 You don't need those co-ordinates to solve the problem
•  » » 7 years ago, # ^ |   0 Well they matter because the plants need to be sorted in ascending order in order for N — LIS to work.
•  » » » 7 years ago, # ^ |   0 Yes, but they are already sorted on input.
 » 7 years ago, # |   0 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.
 » 7 years ago, # |   0 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.
•  » » 7 years ago, # ^ |   +5 When we use BFS we shouldn't add vertex number N to the queue. You can view test 12, it is quite small.
 » 7 years ago, # |   +4 link to editorial please?
•  » » 7 years ago, # ^ |   +9 In the Russian thread gen has said that it's not ready yet, so it'll be tomorrow.
 » 7 years ago, # |   +22 thanks for nice problemset. I realized I shouldn't pass a round even if its writer is Purple.
•  » » 7 years ago, # ^ |   +11 Thanks, glad you liked it!
 » 7 years ago, # |   -14 While this site is great and enjoyable, I would like to report a little problem in the site which wasted 45 minutes of my time in this contest; The sequence was: I submitted my solution for problem B in time ~ 00:58. My submission's status appeared and after a little time it failed in pretest #4. I reviewed and resolved the bug then I resubmit the new one. THE SITE SHOWED ME THE PREVIOUS SUBMISSION'S STATUS, SO, I THOUGHT THE NEW ONE ALSO HAS BEEN FAILED ON PRETEST # 4! After 45 minutes surprised about why the solution fails on pretest #4, I found out my new one did not submit actually. I resubmit it again and it passed pretests and accepted later.I think it will be better if the site avoid appearing the submission's status except after it surely is sure that the submission was successful and the new one strongly will appear on top of previous ones!Thanks in advance!
 » 7 years ago, # | ← Rev. 7 →   +4 Testcases in Div2.C are not strong enough.My code got AC, but fails on this test: 2 0 1 1000000000 1 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.
 » 7 years ago, # |   +39 Congratulations to kelvin to be the first participant who has successfully upsolved the hard problem 269E - String Theory: 3062253!
•  » » 7 years ago, # ^ |   +36 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
 » 7 years ago, # |   0 Div2 Problem C. On test case 15, the answer should be 14 but my output is being shown by your system as 15. But when I run the same code on my system, the output comes out to be 14 which should be correct. Please check.
 » 7 years ago, # |   +4 Div 2 was really good and amusing contest , questions were just so cool , i loved solving them , thanks gen :)