### yaro's blog

By yaro, 8 years ago, translation,

Hello, friends!

Winter 188th Codeforces Round is coming!

We wished to prepare for you some enjoyable problems (as we believe, not very difficult) with nice ideas and clear statements.

"We" includes authors of the problems yaro and Rei, Codeforces Rounds supervisor Gerald and the platform founder MikeMirzayanov. Special thanks to Pasha (PavelKunyavskiy) and Artem (RAD) for the testing and helpful comments.

Last time I was preparing a competition here on Codeforces, Rounds were still "beta". Well, with less "beta" comes greater responsibility. So I wish the authors and the organizers a successfully held Round. As for the participants, I wish you the unconventional ideas, the clean code (and a clean keyboard, of course), and satisfaction from five (well, possibly the less number will also do...) correct and accepted solutions!

It seems to us that it is not an easy job to arrange the problems by their difficulty, so we have chosen the dynamic scores. Still (out of curiousity) let us put a bet on the following relative difficulties for the problems: div.1 — B-B-C-C-E, div.2 — A-B-C-C-E. How close is our guess?

UPD Sorry for the problems with the Codeforces testing queue during the round.

We will still be happy if you rate our contest (when it will be over): short survey.

And with the gap of one hack the winner of div.1 is meret (Jakub Pachocki)!

Div.1 standings, Div.2 standings.

Analysis (thanks to Rei for the translation).

• +331

 » 8 years ago, # | ← Rev. 2 →   0 Seeing your bet on difficulty levels, Just one question: Are the last 3 questions of div2 not gonna be the same as first 3 questions of div 1..??
•  » » 8 years ago, # ^ |   +1 Yes, they are.
•  » » » 8 years ago, # ^ |   -21 what is d diff b/w div 1 & div 2? i am a beginner and this is my first contest. what should i opt for- div 1 or 2? plz reply asap
•  » » » » 8 years ago, # ^ |   0 Div 2 for new-comers
•  » » 8 years ago, # ^ |   +32 it seems like div 2 will be A-B-**D**-**D**-E !!!!
•  » » » 8 years ago, # ^ | ← Rev. 2 →   +16 D1 500 = D2 1500, D1 1000 = D2 2000, D1 1500 = D2 2500This tradition is also a bit strange. The ratios of points are different.
•  » » » » 8 years ago, # ^ |   0 Are you sure that ratios of point must be equals to ratios of difficulties? It isn't clearly.
•  » » » 8 years ago, # ^ |   +5 Exactly!
 » 8 years ago, # |   -14 maybe there will be GAME OF THRONES effect on the problem statement.. :)
•  » » 8 years ago, # ^ |   -14 'We have to save Robb! He needs your help, but for this you have to find the number of .... to identify the traitor. Please, hurry up!' For example
 » 8 years ago, # |   +16 Since you said for div 2 it's A-B-C-C-E, I guess you meant that it's A-A-C-C-E for div 1?Or is it A-B-D-D-E for div 2??
•  » » 8 years ago, # ^ |   +2 C'mon everyone, don't be so peaky :) He only said that the 3th and 4th problem are of similar difficulty.
 » 8 years ago, # |   +10 I hope that this round will be easier because according to the announcement, it seems that this round is going to be difficult. Thanks !
 » 8 years ago, # |   +5 Haaa, Game of Thrones! "Growing Strong" & "As High As Honor"!
 » 8 years ago, # |   -69 contest is prepared by a lot of people thank you all but I hope it will not be like chinese contest
•  » » 8 years ago, # ^ |   +47 Contest is prepared by 2 person — yaro and Rei. I just wrote extra solutions for more checking.
 » 8 years ago, # | ← Rev. 2 →   0 Thanks yaro and also Rei for the contest!
•  » » 8 years ago, # ^ |   -25 if it is easy for you, it will also be easy for other people :D
•  » » » 8 years ago, # ^ |   -16 Than the competition becomes a speed competition :D
•  » » » » 8 years ago, # ^ | ← Rev. 2 →   -9 I participated in two such contests(but it was not simple(AB — very simple and CDE or DE — difficult(solved by 5-30 users)1) Codeforces Round #163 (Div. 2) (there were 2 very simple problems, third was solved by 80 users, and two last weren't solved) — it's really speed competition2) Untitled contest
•  » » » » » 8 years ago, # ^ |   -11 I had a similar experience, where just one unsuccessful hack brought me from position 200 to position 1300 XD
•  » » » » » » 8 years ago, # ^ |   0 And my schoolmate did one successful hack and comes to position 400 from position 900(but his own solution crashed on final tests)
 » 8 years ago, # |   -25 what is d diff b/w div 1 & div 2? i am a beginner and this is my first contest. what should i opt for- div 1 or 2? plz reply asap.
•  » » 8 years ago, # ^ |   +8 Div 2
•  » » » 8 years ago, # ^ |   0 thx
•  » » 8 years ago, # ^ |   +6 trying opting for div1 !! (only if you could !)
 » 8 years ago, # |   +9 judgement is going very slowly... please check
 » 8 years ago, # |   0 What the hell is that?! 15 minutes to get a response for the submission?!!!
 » 8 years ago, # |   +5 in queue for more than 10 minutes in Div2 B. judging sucks. :(
•  » » 8 years ago, # ^ |   +3 still in queue.
 » 8 years ago, # |   +10 very slow judgement, this is becoming very annoying
 » 8 years ago, # |   -9 There seems to be a problem each contest.
 » 8 years ago, # |   -7 Queued :(
•  » » 8 years ago, # ^ |   -16 Yeah, I think is time to upgrade those Pentium II they have, don't you think? In TopCoder this never happens, just saying...
•  » » » 8 years ago, # ^ |   +8 Watch out, people are very sensitive here... My "Queued" comment presses some buttons that the other complaints don't
•  » » » 8 years ago, # ^ |   0 In topcoder problems there are not super large constraints, so the system test is evaluated quickly... Just saying.
•  » » » » 8 years ago, # ^ |   0 We are talking about the pretests here, which are known for their lack of "super large constraints", whose time-limit is 2s anyway. So, please.
•  » » » » » 8 years ago, # ^ |   0 In fact, some pretests can have 'super large constraints' :) I don't know if this contest have it, but well... Have fun and keep coding.
•  » » » 8 years ago, # ^ | ← Rev. 2 →   0 There's no judge results right after the submission. How would it possible to get queue? (Solutions aren't testing on samples)
 » 8 years ago, # |   -7 How is my solution hacked even when i ddnt lock it ??
•  » » 8 years ago, # ^ |   +1 when you didn't lock your solution it can be hacked but you can resubmit another solution again, but when you lock it, you can't resubmit another solution.
 » 8 years ago, # |   0 The judegement is very slow. Hope the system test will be finished as soon as possible.
 » 8 years ago, # |   +1 Wow, so many hacks for Div2 Problem C. I guess some coders overlooked the constraints for input data. Anyway, at least it was interesting trying to hack others. Oh and it seems to me that the writers have managed to make a nearly-perfect A-B-C-D-E problem set for DIV2, at least according to number of solvers before sys-test...
•  » » 8 years ago, # ^ |   +4 For Div2 Problem C.Maybe some case like this: -1000000000000000000 1 2
•  » » 8 years ago, # ^ | ← Rev. 4 →   +4 my hacking test for problem C Div 2: -1000000000000000000 1 1000000000000000000
 » 8 years ago, # |   +5 i guess one of reason that the pretest is a bit slow is because many TLE codes for C div 2 :)
 » 8 years ago, # |   +5 thanks yaro and Rei for the contest! :) next time try to make the system testing a bit faster!
 » 8 years ago, # |   +3 how cruel the C in div.2 is! -10^18 1 10^18 is a strong test data.^_^.
 » 8 years ago, # |   +6 Survey for the contest....what a democracy..!
 » 8 years ago, # |   0 Sad sad sad :-(|) ... ... long long x,y,m; long long res; ... int mymx = max(x,y); // int ??? int mymn = min(x,y); // int ??? x = mymx; y = mymn; ... 
 » 8 years ago, # |   0 system testing has also been too slow!!! what is the reason?
•  » » 8 years ago, # ^ |   +5 I guess because of the amount of TLEs in DIV2 C and DIV1 A
•  » » » 8 years ago, # ^ |   +9 All TLEs solutions in A div 1 (C div 2) were hacked, I think. And slow speed of system testing is because slow B div 1 (D div 2) solutions.
 » 8 years ago, # | ← Rev. 2 →   0 Oh,It my best rank until now.
 » 8 years ago, # |   +18 Status of submission 3895303 is still "Running on pretest 8", why?
•  » » 8 years ago, # ^ |   +39 Because that code is Forrest Gump ..... "Run Forrest Run " ...... :) :
 » 8 years ago, # | ← Rev. 2 →   0 my submission 3887964 for Div-2 B failed on the last test case! :(
 » 8 years ago, # |   0 oh damn, i forgot to update the volume of vessels...
 » 8 years ago, # | ← Rev. 2 →   +1 I don't understand why i was got RTE in div-2 B. I just assign the size of sting s to n and it gets AC. AC link http://codeforces.com/contest/318/submission/3895790 RTE link http://codeforces.com/contest/318/submission/3888165 Can any one explain it?Thanks in advance.
•  » » 8 years ago, # ^ |   +3 same thing happening to me too...but i got MLE instead of RTE..RTE: 3887964, AC: 3895821
•  » » » 8 years ago, # ^ |   0 But i want to know what's the problem with "i
•  » » » » 8 years ago, # ^ |   +12 s.size() returns an UNSIGNED integer, so if s.size() is less than 4This statement ( s.size() — 4) won't be a negative number! It will be a really big positive number and the loop won't end and it will try to access out of bounds places in the arrayYou need to cast s.size() to (int), signed int in order to avoid this..You can print the value of s.size()-4 when s has size less than 4 and see the output yourself.
•  » » » » » 8 years ago, # ^ |   0 I had the same problem, and I got the answer.thank you guys for asking and answering the question.
•  » » 8 years ago, # ^ | ← Rev. 2 →   +60 s.size() is unsigned, so when s.size() < 4, s.size() - 4 would be a large unsigned integer, and you'll get RTE.Edit: That's why some people (including me) has a predefined macro #define SZ(x) (int)x.size() :D
•  » » » 8 years ago, # ^ |   +6 Thank's peter50216. Now i have my answer.
•  » » 8 years ago, # ^ |   +2 Happened with me as well. I should never have ignored those compiler warnings.
 » 8 years ago, # |   -29 the worst thing about codeforces is that the main testing takes place after the contest ,if it would have told that my solution is wrong after running the test cases during the contest ,i would have corrected my solution this thing needs to be changes,i m not sure even after passing pre test cases whether my solution will increase or not
•  » » 8 years ago, # ^ |   +14 that's why it's called 'pre'-test
 » 8 years ago, # |   0 Waiting Contest rating update.
 » 8 years ago, # |   0 I think it's A-B-B-D-E for Div 2
•  » » 8 years ago, # ^ |   +32 And it seems like A-B-E-C-F for Div 1 .^_^.
•  » » » 8 years ago, # ^ |   +20 what do you mean by F ? F...K ?
•  » » » » 8 years ago, # ^ |   +2 I mean it's harder than E...it has 3000 point
 » 8 years ago, # | ← Rev. 2 →   -20 D (Div. 1) was very similar to TCO 2A Hard. I was able to copy & paste 1/3 of the code.
 » 8 years ago, # | ← Rev. 2 →   0 Is div-2 C can be solved by Extended Euclid?
•  » » 8 years ago, # ^ |   +6 Div-2 C is simple brute force, but you need to take care of the corner cases where the answer is 0 or -1 or when one of x and y is negative.
•  » » » 8 years ago, # ^ | ← Rev. 2 →   0 It's not a 'simple brute force'. Consider the Test Case -1000000000000000000 1 1000000000000000000. With a pure brute force this TC would definitely give TLE. The trick is to consider the case, when one of the numbers is <0 and the other one >0. And only then you can do brute force. Edit: oh, sorry, I missed the last part of your comment JuanMata
 » 8 years ago, # | ← Rev. 2 →   0 Can any one tell me about SergeiFedorov's solution for Problem E? ... My solution get TLE when Princess && Shadow are within a same block....
•  » » 8 years ago, # ^ |   +44 Well, I could ))
•  » » 8 years ago, # ^ | ← Rev. 2 →   +52 Idea: if we could reach point outside of the forest, than do it with both points. Then find two nearest trees on the border (one by x coordinate and one by y coordinate) and win :)If we stand inside the forest and could not get out of it, then just go to the position where shadow stands. Then again to the new shadow position and so on, until we reach it. Of course one should check that they lie in the same component.I use simple dfs to move from one point to another while inside forest. And greedy one to move to the border trees while points lie outside.
•  » » » 8 years ago, # ^ |   +1 ... Wow, this is better ... I have learnd a lesson ... .. Thanks ~~
 » 8 years ago, # |   +3 For all those who solved problem D, where do you get the array?
•  » » 8 years ago, # ^ |   0 One way to get it is to precompute it. I left the code I used in my solution: 3891054.
•  » » » 8 years ago, # ^ |   0 Or precompute it like this: 3896247 (only compute the masks you actually need instead of all; runs 5 secs on my computer).
 » 8 years ago, # |   0 Interesting round! Can't wait to see editorial for Balance.
•  » » 8 years ago, # ^ |   +6
 » 8 years ago, # |   +4 when is the next round comming?
 » 8 years ago, # |   0 any hint about Div1 D ?
•  » » 8 years ago, # ^ |   0 There is always an option to find our analysis. It's not that hard (I know at least three ways to find it)...