### Errichto's blog

By Errichto, 4 years ago,

Hello everybody!

On December 30 at 14:05 UTC/17:05 MSK (check your time zone here) Codeforces will host the New Year's contest Good Bye 2016. The contest is combined for both divisions, lasts 2.5 hours and contains 8 problems. Thanks to Harbour.Space and Barcelona ACM-ICPC Programming Bootcamp 2017 sponsoring the contest, winners can expect really cool prizes:

• 5 best participants (not ACM ICPC veterans) will win free participation in Hello Barcelona programming bootcamp.
• 30 best participants (not ACM ICPC veterans) will receive a 30% discount for participation in Hello Barcelona programming bootcamp.
• 100 best participants will receive t-shrits by organizers and Codeforces.

Hello Barcelona programming bootcamp in collaboration with Moscow Workshops ACM ICPC is a competitive programming training camp to be held between February 6-14, 2017 at Harbour.Space University in Barcelona. Note that lecturers and coaches are: GlebsHP, MikeMirzayanov, Endagorion, Michael, Jacob and snarknews, so the camp must be valuable. The registration is open up to January 20th, 2017.

I'm an author of problems. I want to thank several people. MikeMirzayanov for creating Codeforces and Polygon and for allowing me to prepare this contest. GlebsHP for his help in everything (hope to work with you again!). mareksom for testing (other testers TBA). My sister for drawing. I also want to thank the Hello Barcelona organizers for providing nice prizes for you.

I'm proud of the problem set and I think that everybody will find something interesting for themselves. I tried to keep statements shorter than usually so it may be a good idea for you to read more problems and choose one that fits you. Obviously, problems will be about the New Year and a little polar bear whom you might know. Since you will face one interactive problem, please read the Interactive Problem Guide in advance.

Don't forget to register. I wish you great fun and no frustrating bugs.

UPD1: The points drop will be adjusted to the round length. It means that for submitting e.g. at the end of the contest gives the same percent of points as in usual 2-hour rounds. Also, I remind you that there will be an interactive problem (as mentioned above).

UPD2: In 750F - New Year and Finding Roots the interactor was printing neibhours in format "k t1 ... tk" instead of "k\nt1 ... tk" (in one line instead of two lines). It's my fault and I'm sorry for the inconvenience. If you were heavily affected, please write to me or GlebsHP. And thanks for noticing/guessing, Gassa!

UPD3, WINNERS

Congratulations!

Thanks for participating. If you want to know intended solutions, see the editorial (it isn't completely ready yet though). See you next time and have an awesome New Year!

Announcement of Good Bye 2016

• +556

 » 4 years ago, # |   0 Thank you for the large number of problems. It's always more fun to have a choice in what I try to solve (instead of hitting a wall where everything afterwards is unrealistic for me to solve lol).
•  » » 4 years ago, # ^ |   +32 You are always the first person to comment in cf round blog post. Why buddy
•  » » » 4 years ago, # ^ |   +8 I usually just come online to look for a problem to solve and then see the new post. I don't think I'm always the first though lol.
 » 4 years ago, # |   +311 I tried to keep statements shorter than usually
•  » » 4 years ago, # ^ |   +33
•  » » » 4 years ago, # ^ |   +40 It's always great to know there is actually people who enjoyed those long story!
•  » » » 4 years ago, # ^ |   -23 Long questions are going to be fun — Everyone is going to spend half an hour to read all 8 questions and it's gonna be hilarious to watch as a bystander.
•  » » » 4 years ago, # ^ |   +4 I like the story when practising, but not during contest...For my poor English, long story costs me much time.
 » 4 years ago, # |   -10 Great way to end this year
 » 4 years ago, # |   -61
•  » » 4 years ago, # ^ | ← Rev. 2 →   -94 [DELETED]
•  » » 4 years ago, # ^ |   0 The legend says that in each round someone has to repeats the same joke
 » 4 years ago, # |   +62 challange: make your rating 2017!
•  » » 4 years ago, # ^ |   +66 Challenge denied
•  » » 4 years ago, # ^ | ← Rev. 2 →   +183 Even getting to the number of digits of 2017! is almost impossible......
•  » » » 4 years ago, # ^ |   -66 I don't think he meant that..
•  » » 4 years ago, # ^ |   +5 Hope I can do it :D
•  » » 4 years ago, # ^ |   +31 Ez :)
•  » » 4 years ago, # ^ | ← Rev. 2 →   +73 Challenge completed
 » 4 years ago, # |   +19 Codeforces Say Goodbye Again! Have a good time！ I want to change my username. And how to do that ? THX
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 Hey !! Me too. Is there a way by which I can change my user name
•  » » » 4 years ago, # ^ |   +1 (http://codeforces.com/blog/entry/6302) This link will help
•  » » » » 4 years ago, # ^ |   0 thanks!Though I can see nothing but some pictures failed.
 » 4 years ago, # |   +12 What do you mean by ICPC veteran? Do you have to be a medal winner to be a veteran or are you a veteran even if you have participated in regionals.
•  » » 4 years ago, # ^ |   +10 veteran = retiredYou are eligible for free/cheaper camp if you still can participate in acm-icpc.
•  » » » 4 years ago, # ^ |   +13 This is not my concern, but what about guys who don't want to participate in ACM or are too young? Or are willing to go, but don't have teammates?
•  » » » » 4 years ago, # ^ |   +4 And what about high schoolers? Are they too young
•  » » » 4 years ago, # ^ |   0 And what about those who didn't qualify for WF this year but it was their last chance?
•  » » » 4 years ago, # ^ |   +33 "you still can participate" = "it's possible that you will participate in an official acm-icpc contest somewhen in the future"
 » 4 years ago, # | ← Rev. 2 →   +9 I have a lot of games did not attend, in The hope that The contest Goodbye2016 would it be possible for me to rise!
 » 4 years ago, # |   -18 8 problems in 150 minutes for a solo contest.Geez this is going to be tough.
•  » » 4 years ago, # ^ |   +60 Why? The problems are sorted by difficulty. You don't even have to read all the problems. If I will add three nearly unsolvable problems to the standard CF round, it become harder? Don't think so.Even if the problems were not sorted by difficulty, there are many coders who much stronger than you. You can read only problems which are solved by someone.And this is combined round, so first problems will be like AB in div.2.
•  » » » 4 years ago, # ^ | ← Rev. 2 →   +27 Wouldn't the duration be a bit too short for coming up with ideas? Even for someone (like you) who are able to solve all 8 questions in a competition, I believe that the last three hard questions are going to be challenging enough to worth some time of yours to come up with an approach and 150 minutes seem to be a bit short for top contestants who will sprint through as many questions as possible.
•  » » » » 4 years ago, # ^ |   +23 I agree with you but many a times, it is not about trying to come up with ideas about the question but about selecting which problem suits you the best and code it up and get it accepted. Even in ICPC, never has a team (except once) solved all problems or tried to think about all the problems.
•  » » » » 4 years ago, # ^ |   +31 Your goal is to solve all the problems on the contest? I think you understood it wrong. Problems are different, you know? If the author (such experienced author as Errichto) thinks that 8 problems for 2,5 hours is good then maybe he is right? Let's take standard div.1 round and add div.2 AB to the problemset. It takes 5-15 minutes to solve them and it doesn't change hardness of the contest at all.
•  » » » » » 4 years ago, # ^ |   +10 I think you are right on the second and third point and I've evaluated the difficulty of the round incorrectly by my first impression.For the first point I think you are correct too, but I want to be an optimistic dreamer for now, especially when I am not sure how far can I push. =]
 » 4 years ago, # |   0 How many problems in the contest? 8 or 7
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 I think 8 problem
•  » » » 4 years ago, # ^ |   +4 thank you
 » 4 years ago, # |   +36 Mike! +17 rating to everyone please!
•  » » 4 years ago, # ^ |   +41 If everyone's rating increases by the same amount your relative ranking is still the same.
•  » » » 4 years ago, # ^ |   +81 so, making it optional would be better..
 » 4 years ago, # |   -69 Is the contest rated?
•  » » 4 years ago, # ^ |   -21 yes
•  » » » 4 years ago, # ^ |   -33 thank you
•  » » 4 years ago, # ^ |   -15
 » 4 years ago, # |   0 Goodbye 2016, Hello 2017 and higher rating :)
 » 4 years ago, # |   +177 Is there a possibility that instead of getting funding to Barcelona camp we can get funding to Petrozavodsk camp xD? It is significantly cheaper, so that should be easier to give xD.
 » 4 years ago, # |   -9 Nice id of contest : 750
•  » » 4 years ago, # ^ |   -16 Number 402 is even more interesting for you.
•  » » 4 years ago, # ^ |   -10
 » 4 years ago, # |   +182 The contest is combined for both divisions The red contestants:
•  » » 4 years ago, # ^ |   +261 and me
•  » » 4 years ago, # ^ |   +115 And there are only 100 t-shirts for them, no wonder why they don't wear shirts.
 » 4 years ago, # |   -17 Limak brings me good luck! :D Yeaaah!!
 » 4 years ago, # |   -6 How can I register for it
•  » » 4 years ago, # ^ |   0
 » 4 years ago, # |   +164 Another contest? Another ** ** ***** meme.
•  » » 4 years ago, # ^ |   0 Another ** ** ***** meme.
 » 4 years ago, # |   +5 A brilliant way to end the year :D.
 » 4 years ago, # |   -55 условии задач будут на русском или на английском?)
•  » » 4 years ago, # ^ |   -48 Доступны на обоих языках. Зависит от того какой выберешь
 » 4 years ago, # |   0 Hoping for expert from this, but now I'm probably jinxing it.
 » 4 years ago, # | ← Rev. 2 →   -60 6 will kick out by 7(prime number) 2017 > (1st + last) prime number xD
 » 4 years ago, # |   +108 may I can also say GOODBYE for Div2
•  » » 4 years ago, # ^ | ← Rev. 2 →   +34 Hope I won't say goodbye for Div1UPD: I'm so happy
•  » » 4 years ago, # ^ |   +9 No you can't
 » 4 years ago, # |   -16 All's Well That Ends Well :) Hope to give a positive reflection of this Quote on the year 2016...
 » 4 years ago, # |   -29 To be honest, the thing I care about most is how the gifts will be awarded lol. If winners are the top 100 contestants then I would cry for a moment leaning against the wall...
 » 4 years ago, # |   -76 I know I will get lots of downvotes but we just can't forget this meme and specially for new year, let's all say ** ** *****? ***, ** ** *****.
 » 4 years ago, # |   +8 Finally I will take part in a round again, after a long time :D
 » 4 years ago, # |   -42 Is it rated?
•  » » 4 years ago, # ^ | ← Rev. 2 →   -31 Upd: Ok, I understood. Just ignore "** ** *****" comments if you don't want downvotes
•  » » 4 years ago, # ^ |   +22 say ** ** *****? is like say Lord Voldemort
•  » » 4 years ago, # ^ |   -27 ** ** *****? question and no downvotes? that's weird!
 » 4 years ago, # | ← Rev. 2 →   +58 codeforcces VS long queue . hope codeforces win :)
 » 4 years ago, # |   -44 interesting ... Tourist vs Petr vs AnasAbbas
•  » » 4 years ago, # ^ |   +75 You are not allllekssssa, this won't work :D
 » 4 years ago, # | ← Rev. 2 →   +40 delay, delay, delay :(
 » 4 years ago, # | ← Rev. 2 →   +11 I hate nothing more than getting ready and then finding the contest postponed xD
•  » » 4 years ago, # ^ |   -10 it's not more than when they delayed the contest for 3 more days :(
 » 4 years ago, # |   +12 8.7 k registered users!)
 » 4 years ago, # | ← Rev. 2 →   +6 10 mins delaythanks to the delay 9k user registered
 » 4 years ago, # |   +45 good bye 2016 with a delay! the last delay of this year :P
•  » » 4 years ago, # ^ |   +45 There could be another one in 10 minutes
•  » » 4 years ago, # ^ |   +5 I hope so.
•  » » 4 years ago, # ^ |   +5 Happy new delay!
 » 4 years ago, # |   +31 Contest Delayed. Can't even say I'm surprised!
•  » » 4 years ago, # ^ |   0 I thought it was that my computer had broken!
•  » » 4 years ago, # ^ |   0 It was like 1 min remaining.... opens IntelliJ, parse contest using CHelper Suddenly 10 mins remaining.. I'am like did I misread the time? ;)
•  » » 4 years ago, # ^ |   0 need to spawn more server maybe?
 » 4 years ago, # |   +23 Good to see people informing for the delay in the comments. I was right about to start solving but you reminded me, thanks!
 » 4 years ago, # |   +13 Interactive Problem Guide is temporarily blocked by administrator?
 » 4 years ago, # |   0 almost 9000 registrations!! It's going to be furious!
 » 4 years ago, # | ← Rev. 2 →   -23 I am 100% sure that Problem B is judged incorrectly. There is a difference between going towards the south and to continue moving in the direction that he specified from the start of movement if I am at some place on the earth and I specified that I will move INF kilometers to the right then I will be moving in circles around the earth and I will not stop !! It doesn't mean that I will leave the earth xS
•  » » 4 years ago, # ^ |   +6 Problem B* :v
•  » » » 4 years ago, # ^ |   +3 Yes , Sorry
•  » » 4 years ago, # ^ | ← Rev. 2 →   +1 The earth is round :/, so it should be mentioned that if we can go in circles or not :(.The problem should be cancelled.
•  » » » 4 years ago, # ^ |   +9 The contest not the problem.
•  » » » » 4 years ago, # ^ |   0 we can go in circles is demonstrated in sample tc 3.. ?
•  » » » » » 4 years ago, # ^ |   +3 You can always go West. But you can't go South after hitting the South pole...
•  » » 4 years ago, # ^ | ← Rev. 2 →   +11 I spent lot of time solving B and then as it is written earth is round, so obviously one has to move forward for distances > 20000. Should have been properly explained, spent lot of time and got result as hacked.
•  » » » 4 years ago, # ^ | ← Rev. 2 →   +1 So, the answer for140000 South is NO?
•  » » » » 4 years ago, # ^ |   +1 Yeah, According to the judge, its a NO. :/
•  » » » » » 4 years ago, # ^ |   +1 I am so stupid :(
•  » » » » » » 4 years ago, # ^ |   +4 There is a sentence in statement about this: "before any of the instructions or while performing one of them".
•  » » » » » 4 years ago, # ^ |   0 y wud it be NO?20000 South + 20000 North=YES ..right?
•  » » » » » 4 years ago, # ^ |   +8 Clearly in the problem statement, it has been mentioned that whenever you are performing a work, you should not move south of South pole or north of north pole.
•  » » » » » » 4 years ago, # ^ |   0 Damn :/
•  » » » » » » 4 years ago, # ^ |   0 The word 'clearly' doesn't add any value =)
•  » » » » 4 years ago, # ^ |   0 After moving 20000 KM to the south you are at the South Pole, you can't continue walking beyond that because you are at the South Pole and want to move (20000 KM) to the South which is not allowed as described in the statement.
•  » » » » » 4 years ago, # ^ | ← Rev. 2 →   0 Howerver in test case: 5 20000 South1000 North1000000 West9000 North10000 NorthAns: Yes1000000 west means around the circle but same is not true for north and south, is quite strange for me.
•  » » » » » » 4 years ago, # ^ |   0 The problem is that in every place of the world, you can go west (except on the poles), but you cannot go Norther than North Pole
•  » » » » » » » 4 years ago, # ^ |   0 What I am saying is 1000000>20000 is allowed for west but not north and south.
•  » » » » » » » » 4 years ago, # ^ |   0 I mean, if you are in Australia, you can go east and reach the Americas, and from there, you reach Africa, and then India, and then you repeat. From any point not in the poles, you can always go east/west. However, if you go from Africa, north, you reach Europe, and then the North Pole. But any direction you move from there, you are moving south. The problem is that the división of earth in the north-south direction is not according to the sphere shape, but to the projection shape
•  » » » » » » 4 years ago, # ^ |   0 The answer is "YES" here, Notice that if you go West or East your distance from the South and North Poles won't change. So moving East or West can simply be ignored.
•  » » 4 years ago, # ^ |   -18 Something has to be done about B.
•  » » 4 years ago, # ^ |   0 Clearly in the problem statement, it has been mentioned that whenever you are performing a work, you should not move south of South pole or north of north pole.
•  » » 4 years ago, # ^ |   0 As you said, there is a diffrence between moving into direction that he specified from the start, and going towards the south. And the sentence "If at any moment of time (before any of the instructions or while performing one of them) Limak is on the North Pole, he can move only to the South." in my opinion makes it 100% clear that Limak goes towards the south, not in one direction.
 » 4 years ago, # |   0 worst problemset ever !
•  » » 4 years ago, # ^ |   +163 worst comment ever
•  » » » 4 years ago, # ^ |   -14 nice problemset!! but i need to improve a lot
•  » » 4 years ago, # ^ |   +9 I too was expecting a much better problem set..very much disappointed..
•  » » » 4 years ago, # ^ |   +73 Your arguments are overwhelming.
•  » » » » 4 years ago, # ^ |   +38 I think the majority is probably people salty about B. It wasn't unclear you just had to read carefully.
•  » » 4 years ago, # ^ |   0 Not the worst problemset ever ! it's just your worst performance ever !!!
 » 4 years ago, # | ← Rev. 2 →   -20 Tell me result at this test. (task B)
•  » » 4 years ago, # ^ |   +4 Do not discuss problems during the contest.
•  » » » 4 years ago, # ^ |   +3 oh... sorr
 » 4 years ago, # |   +105 B is a shitty problem. sorry.
 » 4 years ago, # |   +73 After reading problem setter is Errichto i was expecting a great contest :/
•  » » 4 years ago, # ^ |   0 same.
•  » » 4 years ago, # ^ | ← Rev. 5 →   +16 Maybe the fist four problems aren't interesting but the last four are very good,i can even say that they are some of the best problems i have ever seen!!
 » 4 years ago, # |   +18 How to solve E?
 » 4 years ago, # | ← Rev. 4 →   +35 please someone call PrinceOfPersiaI miss his problems' difficulty
 » 4 years ago, # |   +19 I need to wait 2 minute at last 30 minutes of contest to look code of a participant, it's awful
»
4 years ago, # |
+50

Contest last 10 seconds, going to submit hack case. WiFi disconnected....

# life

•  » » 4 years ago, # ^ |   0 I realised my mistake on F 7 mins before end... I needed just one more function(10-15 lines) and there were just 15 secs... Now I wanna cry :((((
 » 4 years ago, # |   0 How to approach D?
•  » » 4 years ago, # ^ |   +21 Hint: MAX_T * n = 150
 » 4 years ago, # |   +14 Pretty hard but enjoyable contest I think. Can anyone explain how to solve D? I was looking for some kind of pattern but couldn't seem to find anything that worked.
•  » » 4 years ago, # ^ |   +2 Hint: Notice that the farthest visited cell will have distance at most 5*30 = 150 (in x and y coordinate).
•  » » 4 years ago, # ^ |   +6 I did a sort of BFS with memoization for repeated states. Since you could never shoot a firework more than 150 or so squares from the start, you can generously say that there is a 300 by 300 square area where fireworks can explode. Of course, there are 8 different directions the fireworks could be going, and 30 different possible states it could be at indicating how many splits that firework can do. I know this leaves out a lot of information, but you can see the main idea of how you memoize, you can figure the transitions out yourself.
•  » » » 4 years ago, # ^ |   +3 I started thinking along those lines but convinced myself that there'd be too many states to place into a queue but now that I think about it's not bad. Yeah the main idea is pretty clear, thanks for the help!
•  » » 4 years ago, # ^ |   0 Simulate the process, but remove fireworks that are in the same location and going in the same direction. There are not that many possible positions of the fireworks, they can be bounded by a 400x400 square, and each firework only has one of eight possible directions.
 » 4 years ago, # |   +13 it's over 9000
 » 4 years ago, # |   +6 How to solve D?
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 Hint : You can build the grid via an alternating sequence of 90 degree and 180 degree rotations and you need to perform this replication of the grid exactly n times.Also observe that the final grid size is not that big
 » 4 years ago, # |   0 How to solve C?(ternary search?) I remember there was a blog asking for finding maximum value of x where f(x)=1 and where f(x) varies as 00....000....1111...11...00...00. There someone said it was impossible.
•  » » 4 years ago, # ^ |   +3 form the inequality equations.After forming the inequalities the possible range of initial ratings lies in the range [L,R].if R==INF ans = Infinity. if L>R ans = Impossible. else ans = R+(some of all rating changes)
•  » » 4 years ago, # ^ |   0 Let x be his initial rating. Write the inequalities after every round, choose the 2 most restricting ones, and from there you can determine the answer.
 » 4 years ago, # |   0 B was a hard problem at the way i understand:he finishs in north pol with the same direction as first :|.
 » 4 years ago, # |   +21 I think D is such a great problem (Assuming that I pass system tests of course ;D)!
•  » » 4 years ago, # ^ |   0 I agree with you, though i can not figure it out :D
 » 4 years ago, # |   +40 1.Petr2.tourist3.rng_58reminds me of good old memories! ^_^
 » 4 years ago, # |   +6 IN problem B, if Earth is sphere, how come he fall down from earth ? Errichto I was expecting to end my year happily :(
 » 4 years ago, # |   +1 Apparently the solution for this test for B according to judge is NO :225000 South15000 NorthThe earth is a sphere. Why is this not allowed?
•  » » 4 years ago, # ^ |   +18 You cant move south when you are at south pole
•  » » 4 years ago, # ^ |   +24 If at any moment of time (before any of the instructions or while performing one of them) Limak is on the South Pole, he can move only to the North.
•  » » » 4 years ago, # ^ |   +13 or while performing one of themOh. :/
•  » » 4 years ago, # ^ |   +15 25000 South means he has to move 25000 miles, constantly in the southern direction, NOT "face South, move straight 25k miles".He can't move 25k miles to the South, because there are only 20k until the South pole, where he can't keep moving South.
•  » » 4 years ago, # ^ |   0 Clearly in the problem statement, it has been mentioned that whenever you are performing a work, you should not move south of South pole or north of north pole.
 » 4 years ago, # |   +3 To be honest this contest was very confusing. I wish some things were worded differently or omitted to make problems clearer.
 » 4 years ago, # | ← Rev. 3 →   +10 I wasn't able to submit last 20 seconds, the page was loading ... the site is very slow when there're a lot of people. I will be upset if problem will pass systest in practice. : (( p.s very good problem set : ))p.p.s HAPPY NEW YEAR.. !!!
 » 4 years ago, # |   +190
 » 4 years ago, # |   +206 Goodbye 2016. Goodbye rating.
 » 4 years ago, # |   +13 Nice Set of problems :) Happy New Year In Advance :) Happy Coding :)
 » 4 years ago, # |   0 What is the answer for this test case for problem C?20 -2 1 -100 2 -100 2 -100 2 -100 2 -100 2 -100 2 -100 2 -100 2 -100 2 -100 2 -100 2 -100 2 -100 2 -100 2 -100 2 -100 2 -100 2 -100 2 -100 2
•  » » 4 years ago, # ^ |   0 I mean I get -1, but I suck so that could be entirely wrong.
•  » » » 4 years ago, # ^ |   +2 I also get -1 but I also suck so idk :/
•  » » » » 4 years ago, # ^ |   0 I got -1 too, but I suck too, so it could be wrong
•  » » » 4 years ago, # ^ |   0 me too -1
•  » » 4 years ago, # ^ |   0 -1
•  » » 4 years ago, # ^ |   0 -1
•  » » 4 years ago, # ^ |   0 I tried to hack Coder_404's solution with this case and I was quite sure his code gave "Impossible" as an answer for this case :( seems I was wrong. I can't check his code right now. I wish he tells me now what his output for this case is :/ if he notices this comment then, I guess.
•  » » 4 years ago, # ^ |   0 A negative value. I failed because I didn't realise this: "... rating, described with one integer, possibly negative or zero."
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 -1, But how come the rating be -1? Just kidding :-p
 » 4 years ago, # |   +14 The 32 pages of people who were hacked on B probably hints at some unintentional ambiguities in the problem.
•  » » 4 years ago, # ^ |   +19 I don't think it's the problem's fault in this case... "Go South/East/whatever X miles" is a pretty unambiguous command imo, and it does NOT mean "face South/East/whatever and move forward X miles straight". Also if you understand it that way, the East/West directions should involve a stupid amount of trigonometry (you wouldn't stay on a constant latitude), which makes it even clearer that can't be the author's intention.
•  » » 4 years ago, # ^ |   +10 Many people tried to hack me on problem B, I hope there is no tricky case i missed.
•  » » » 4 years ago, # ^ |   0 in this case:3 1000 South 2000 North 1000 Southyour solution return yes or no? I tried hack you :[
•  » » » » 4 years ago, # ^ |   +3 my output is "NO"oh, I see what cause many people tried to hack me, it's because I usually use unsigned data type, I only use int data type only if it's too important, sorry for that..
 » 4 years ago, # |   +62 Is it just me, or difficulty increase between D and E is too big? I mean, I expect a lot of people have exactly 4 solved problems.
•  » » 4 years ago, # ^ |   0 I was thinking the same thing, but if you look at the difference between A and B, B and C, C and D you'll notice the same pattern.
•  » » » 4 years ago, # ^ | ← Rev. 2 →   +1 Hm, maybe, but not for me. For me A and B are basically the same and D is easier than C.
•  » » » » 4 years ago, # ^ |   0 By difficulty I mean the number of solvers.
•  » » » » » 4 years ago, # ^ | ← Rev. 2 →   0 A to B: 6434/4267 ~ 1.50B to C: 4267/3100 ~ 1.38C to D: 3100/1296 ~ 2.39D to E: 1296/113 > 11So I don't understand what do you mean.
•  » » » » » » 4 years ago, # ^ |   0 If you look at percentage of solvers:A: 6434/6610 ~ 97.3%B: 4267/6610 ~ 64.6%C: 3100/6610 ~ 46.9%D: 1296/6610 ~ 19.6%E: 113/6610 ~ 1.71%
 » 4 years ago, # | ← Rev. 2 →   +72 Statements weren't short :|
•  » » 4 years ago, # ^ |   +5 Cheated by Errichto :|
 » 4 years ago, # |   +3 Can someone explain how to solve C? Thanks.
•  » » 4 years ago, # ^ |   -19 binary search
•  » » » 4 years ago, # ^ |   0 could you explain more ?!
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   0 our left bound is 1899 — 200000 * 100our right bound is 1899 + 200000 * 100mid = (left + right) / 2mid — our start ratingwe check this one in a loop from 1 to n, and if it didn't pass in any time, we change our bound (r = mid if our current rate more than we need (we didn't change div 1 to div 2 ) and left if our curr rate less than we need(we didn't change div 2 to div 1)And, finally, we check our bouds(right and left) if it pass write final rate, else write "Impossible".Variant "Infinity" can be only if all d[i] = 1;
•  » » » » 4 years ago, # ^ |   0 basically whenever you move from 1-->2 or 2-->1 for the first time in a valid way there will be a range of ratings. for example if the test is like : 2 -7 1 20 2 then range is 1900 to 1906 and then you can carry out all the operations from this point and figure out which yields the maximum ; your predicate here will also be monotic which implies we can do a binary search .
•  » » » 4 years ago, # ^ | ← Rev. 2 →   +4 I was trying with dynamic programming, which doesn't pass the 10th test, sadly.
•  » » » » 4 years ago, # ^ |   +3 let's assume initial rating was xthen at ith step tot rating change =ythen if div1 x+y>=1900,x>=1900-y if div2 x+y<=1899,x<=1899-y this gives a minimum value for x and a maximum value of x take maximum of all minimums(eg x>=5 ,x>=6,x>=7 all relate to x>=7) take minimum of all maximums if min>max impossible case else maximum is ans
•  » » » » » 4 years ago, # ^ |   0 Did exactly this, but failed on Test case 25 :(
•  » » » » » » 4 years ago, # ^ | ← Rev. 2 →   0 Are you considering that rating can be negative? Your variable ratinglow should start as -infinity.
•  » » » » » » » 4 years ago, # ^ | ← Rev. 3 →   0 yes it could be negative (1 ≤ n ≤ 200 000). (- 100 ≤ ci ≤ 100). so answer is -20,000,000
•  » » » 4 years ago, # ^ |   0 I couldn't find some monotone function in this problem, can you explain some?
•  » » 4 years ago, # ^ |   0 I just find min, max value of div1, div2. if there is no div2 ==>> Infinity. if a max value of div2 is bigger than a min value of div1 ==>> Impossible. Finally, there is solution = 1899 + position — maxValueDiv2 to find maximum value. Drawing range will be helpful (Sorry Bad English)
•  » » 4 years ago, # ^ |   +5 Let LL be the lower limit of ones rating, and UL is the upper limit.Now, let the ith contests input is Ci Diif Di is division 1, then you check if his upper limit allow him to participate in the div 1, also change the rating of both LL and UL according to the rating change.If Di is division 2, then you check if the LL allow it, and change rating accordingly.
•  » » 4 years ago, # ^ | ← Rev. 3 →   0 For each contest count difference between rating after it and at the beginning of the year (easy DP). If there is no div2 rating answer is infinity.Then find div2 contest with a maximal rating before it. For optimal answer this rating is 1899. When you assume that it is equal to 1899 you can calculate rating at the beginning.After that check if every div1 rating is above 1900, if not print impossible.And print rating after last contest.
 » 4 years ago, # | ← Rev. 3 →   +9 Everyone solved C except me.. I participate as an Expert and I solve at most 2, i participate as a Specialist and I solve 3-4, what is wrong with me.
•  » » 4 years ago, # ^ |   +7 I think, it's just psychology
 » 4 years ago, # |   0 Whats wrong with problem B ? Isn't it allowed to move along NS or SN arc on arrival on either of poles ?? It wasn't mentioned.
•  » » 4 years ago, # ^ |   +15 If I understand what you mean correctly: "If at any moment of time (before any of the instructions or while performing one of them) Limak is on the South Pole, he can move only to the North."i.e. You go North to the North pole, then you must stop and go South because that's the only cardinal direction available at that point.
•  » » » 4 years ago, # ^ |   0 To my problem TestCase : 1 40000 South YES 
•  » » » » 4 years ago, # ^ |   0 The answer should be NO. After moving 20000 km, you hit the South pole, at which point you are supposed to go further South but that is impossible.
•  » » » » » 4 years ago, # ^ |   0 Simple Misunderstandings can ruin our solutions. I thought that when we move in a direction , we continue to move in that direction till we reach our destination. :P
•  » » » » » » 4 years ago, # ^ |   +3 A problem with that (besides the fact that the "while performing one of them" sentence made the author's intention pretty clear imo) would be that moving east or west would be very difficult to handle — think of going south 1 m from the north pole first, then going west 1000 m, keeping your path straight instead of staying on a constant latitude (ie always keeping west). How far from the pole are you now? You would need some painful trigonometry.
•  » » 4 years ago, # ^ |   0 You could have clarified.
•  » » » 4 years ago, # ^ |   0 How to do that in ongoing contest?
 » 4 years ago, # |   0 Can someone plz share any ideas to solve problem F?
•  » » 4 years ago, # ^ |   +10 Find some path from leaf to leaf. For the middle vertex of it, you'll know for sure what depth it's on, and what its parent is. Use that information to find a longer path (you already have a half of it) etc. Some optimizations are needed on the low depths to fit under 16 queries.
 » 4 years ago, # |   +22 When you do a good contest: The best problem-set ever When you don't : The worse Come on people!
 » 4 years ago, # |   0 What could be some initial ideas on E?
•  » » 4 years ago, # ^ |   +3 The first thing I thought about after reading the statement was Mo's algorithm. But then contest ended :( I don't know whether it could be solved using this thing, It's just an idea.
•  » » 4 years ago, # ^ |   0 I was going to try using a segment tree to keep track of occurances of 2, 0, 1, 6, 2 followed by 0, 2 followed by 1, and so on until you have a count of all 12 possible combinations. You could easily query how many 2016s were in a range, and then I had a theory that if there was more than 1 2016, the answer would be the min of all vals in my seg tree within the given range. Of course you store a similar tree for 2017, but you only need to check if a single 2017 exists. Shouldn't be to big of a problem on memory, but I figured I didn't have enough time to code it.
•  » » » 4 years ago, # ^ |   0 To remove 201666622222016 you only need two erase operations.
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   0 right, my segtree would store: val[("2")] = 6 val[("0")] = 2 val[("1")] = 2 val[("6")] = 5 val[("20")] = 7 val[("21")] = 7 ... val[("2016")] = 7 remember it's storing the number of occurences of "stringhere" as a substring within the range. So the min of all those numbers is 2. And so the answer is 2.
 » 4 years ago, # |   +36 Errichto, you are the best. I really loved problems from A to E, they are as much complicated as they need to be, the statements are clear and ideas are pretty interesting.
 » 4 years ago, # | ← Rev. 2 →   +27 Very nice problemset! :)I wish the duration was longer... The last three problems were really interesting, but I couldn't spend enough time on any of them during the contest. Even top-rated users didn't solve more than 6 (out of 8) problems!
 » 4 years ago, # |   0 Failed to submit solution for F... The connection is not good in china.Anyway, we enjoyed this contest. Thank you.
 » 4 years ago, # |   0 But we expected nice problemset from Errichto. :(:(:(
•  » » 4 years ago, # ^ |   0 I think the problems were good. Prob B was clear from the context.
 » 4 years ago, # |   -18 Tourist
 » 4 years ago, # |   +11 Ok, just finished writing D. Here is my approach: Assume starting point is (0;0). Build the first firework and add passed points to the set. Now, instead of running 2 recursive functions for left and right subtree, run only one for the left. Add points to the set. After that it is possible to find all points from the right subtree using symmetry around last point of previous firework ending. Does it make any sense? Will it pass system tests? :D
•  » » 4 years ago, # ^ |   0 I think you'll get tle...My approach: you can consider a grid of size 300x300, because 30*5 = 150 so if you start at center (pos (150,150)) you won't ever leave any border. You can simulate the steps recursively with this cut: if position (x,y) was visited going on direction d on step i, return.if(dp[x][y][i][d]) return; And this cuts off a lot because you have just 300*300*30*8 possibilities for these... You go from 5*2^30 complexity to just 5*8*2700000.
•  » » » 4 years ago, # ^ |   0 Well, actually my solution passed with 139 ms time which is pretty solid. Shame I didn't manage to finish writing it during contest.
•  » » » » 4 years ago, # ^ |   0 Just saw your code... amazing job! :D I said I thought it would be TLE bcause I thought something similar but the way I'd code it (a "dumber" way) it would be TLE... nice
•  » » » » 4 years ago, # ^ | ← Rev. 3 →   0 How are you exactly calculating the reflection of a point on the line ? I know that there is a standard formula from coordinate geometry but the problem with that is that the resultant coordinates may not be integers.
•  » » » » » 4 years ago, # ^ |   0 Let's say firework is going straight up. In some point P it splits into two. Then one child goes left by 45 degree and another right by 45 degree. For each point from left subtree we can find corresponding one from the right like this: rightX = P.x + P.x — leftX; rightY = leftY.The same way coordinates can be calculated if firework is going straight down. If it is going left or right rightX will be equal leftX and rightY = P.y + P.y — leftY.If firework is going diagonally then new coordinates:rightX = P.x — P.y + leftY;rightY = P.x — leftX + P.y.
•  » » » » » » 4 years ago, # ^ |   0 I used the same idea as yours during the contest but alas made a stupid bug in the reflection part :( Now got AC. Thanks for the help.
•  » » » 4 years ago, # ^ |   0 Can you tell me why those overlapping state(same depth and direction) won't give any new cells?
 » 4 years ago, # |   +154 Flat Earth believers' reaction when reading this problem statement : In this problem we assume the Earth to be a completely round ball and its surface a perfect sphere.
 » 4 years ago, # |   0 What was the idea behind F?
•  » » 4 years ago, # ^ |   0 "I didn't participate in contest but I hope this is true. After making 11 random guesses, the probability of not to find any leave is 1/2048. After finding a leave, just ask h-2 question to go root."I thought it's the solution but when I was writing I realised we can't go to root that simple :P So what is the solution?
•  » » » 4 years ago, # ^ |   0 Each testcase has 500 inputs, so I don't think a probabilistic method would work. I'm also curious.
•  » » » 4 years ago, # ^ |   0 If you have a vertex v with depth d, and a known children u at depth d+1, you can find the parent by doing a walk of length (h-d) from v, not going through u. The walk ends at a leaf if and only if the first edge is not an edge to the parent of v. When close to the root (d <= 2), it is possible to find the root with a search at depth at most d. (It is needed to get under 16 queries). To find the initial vertex, use two disjoints paths to a leaf from a starting node, as the depth of all nodes in the paths are then known.
•  » » 4 years ago, # ^ |   +31 Search for a long path connecting two leaves, using DFS. When you have a path of length at least 7 then the root is at distance at most 2 from the middle of that path. In worst case scenario you need 1 + 2 + 3 + 4=10 questions to get path of length 7. Then there are 7 possibilities for the root. So in 6 questions you can choose among them.
•  » » 4 years ago, # ^ | ← Rev. 5 →   +10 Here's a solution, completely deterministic.Start at vertex 1. Choose 2 of its neighbors and ask questions and dfs along those paths until you reach a leaf. Now you know which direction is to the root. If you are distance <= 2 to the root, BFS. Else, dfs from this vertex until you find a leaf. Then move back to the top of this path (you can do this because you know the length of the path AND what the depth of the vertex you started at is).Now repeat, if you are distance <= 2, BFS. You can check that in all cases this takes at most 16 queries.Very ugly to implement though :(
 » 4 years ago, # |   +1 Nice quality problems, hard statement for me though. :(Am I the only one who logged out two times automatically during this contest? Maybe its because of the internet disconnection issue, but is it a feature?
 » 4 years ago, # |   +3 The best gift for the new year is a new division!
 » 4 years ago, # | ← Rev. 2 →   0 What was the hack in Problem:B ??
•  » » 4 years ago, # ^ |   0 pos < 0 || pos > 20000
•  » » 4 years ago, # ^ |   0 Hack 1340 South60 North20 SouthAnswer — NO Hack 2140000 SouthAnswer — NO
 » 4 years ago, # |   +17 I think tourist lost first place because comunodi hacked 7 solutions in his room .
•  » » 4 years ago, # ^ |   0 Maybe if Petr wouldn't hack, he could solve F. So, we cant be so sure!
•  » » » 4 years ago, # ^ |   +6 Yes , but now tourist needs only one hack to win while peter hacked 6
•  » » 4 years ago, # ^ |   0 Is there any efficient way to find which room a person belongs to?
•  » » » 4 years ago, # ^ |   +17 room 67 you can click on the country flag in the standing page to know the room and view all submission
•  » » » » 4 years ago, # ^ |   +3 oh~ I see!Thanks a lot!
•  » » » » 4 years ago, # ^ |   +3 Well, I found it's actually double click the block with handle.(but don't click on the handle)There may be some people without setting their country :D
 » 4 years ago, # | ← Rev. 2 →   -8 ААА
•  » » 4 years ago, # ^ |   0 What did you mean russian kid
 » 4 years ago, # |   0 How to solve E?
 » 4 years ago, # |   -90 system testing__
•  » » 4 years ago, # ^ |   +4
 » 4 years ago, # | ← Rev. 2 →   -36 a
 » 4 years ago, # |   0 For problem F my program reads k in a line, but then the real format turns out to be k and ti in the same lineSo sad :(
•  » » 4 years ago, # ^ |   0 See UPD2 in the post — if that's the only issue with your solution, you're likely to get the points
 » 4 years ago, # |   -13 Problem B was asking for a solution which was contrary to logic . If the earth is round, even in the South Pole one can go West or East. Goodbye 2016, goodbye rating :( .
•  » » 4 years ago, # ^ |   +27 The West and East directions are actually not defined on the poles. (Think of these directions as a vector field on the sphere, defining it on the poles would break the continuity)
•  » » » 4 years ago, # ^ |   +27 [offtopic] Congratulations on the new color!
•  » » 4 years ago, # ^ |   +6 Actually no. If you are exactly at the north pole, whatever direction you would go it would be south.
•  » » 4 years ago, # ^ |   +19 Actually we can keep on arguing about the geography, but the matter of fact is that we should do what's written in problem statement(if problem states you can't go south from south pole, accept it). No one ever batted an eye about the polar bear doing all the funny things it did in today's problem statements, you accepted it didn't you :)
 » 4 years ago, # | ← Rev. 3 →   -47 DELETED
 » 4 years ago, # |   -37 is it rated?
 » 4 years ago, # | ← Rev. 2 →   0 can anyone help me with 3rd question of contest http://codeforces.com/contest/750/submission/23442653 in my above code it shows wrong answer on pretest 1 but when i am running it on my pc i am getting right answer
•  » » 4 years ago, # ^ |   +1 you should use long long or long long int for rx, because 3000000000 in long int is negative
•  » » » 4 years ago, # ^ |   0 ohh yeah an extra zero.. but how come it is giving right answer on my pc i am running same code same input?
•  » » » » 4 years ago, # ^ |   0 I think your compiler, you can use codeblock or devc :v
•  » » » » » 4 years ago, # ^ |   0 Thanks for help
 » 4 years ago, # |   +20 Contest not yet open for practice? I'm unable to submit code now.
 » 4 years ago, # |   0 Problem C: my solution failed on test # 32What I missed?
•  » » 4 years ago, # ^ |   0 You didn't check if there was a div1 rating that was lower than any div2 rating.
•  » » » 4 years ago, # ^ |   0 Thanks
 » 4 years ago, # |   +8 Solution my solution for B FST at this test case: 2 15072 South 15072 North The system says the solution outputs a "NO" and expected "YES". I use the custom test and paste my solution and the input correctly. But it outputs an "YES" after running..... Sad story... FLOAT TRAP?
•  » » 4 years ago, # ^ |   +8 AC solution WA solution The differences between these two code are two "cerr<<"s. Is this function change the variable?
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 TL:DR; Comparison between double and int is compiler's mood/code dependent. Well, it has something to do with registers during comparisons. Basically when you do cerr<
 » 4 years ago, # |   0 Please tell how can we clarify a question in ongoing contest?
 » 4 years ago, # |   +1 Please tell how can we clarify a problem statement in ongoing contest if we have doubt in it?
 » 4 years ago, # |   0 I wonder when I can submit my code...
 » 4 years ago, # |   +1 Tourist lost the first place by just 44 points and was way clear of everyone else. Still got a negative rating change. Such harsh is life once you are on the absolute top. :/
 » 4 years ago, # |   0 why practice submission is closed ?? :(
 » 4 years ago, # |   0 when the round will be opened for practice ?
•  » » 4 years ago, # ^ |   +5 Its open now
•  » » » 4 years ago, # ^ |   0 thanks
 » 4 years ago, # |   +3 When I can change my nickname ?
 » 4 years ago, # |   +35 Symmetry
•  » » 4 years ago, # ^ |   +11 Christmas tree
 » 4 years ago, # |   -10 Moral from today's problem D :| If you have choice between bfs and dfs, always choose bfs.
•  » » 4 years ago, # ^ |   +6 i chose dfs :D
 » 4 years ago, # | ← Rev. 2 →   -8 Saddest round of the year , I always fail the Goodbye Round(3 years straight)
 » 4 years ago, # | ← Rev. 2 →   +127 Good Bye 2014, 3rd place, 2894 -> 2898 (+4)Good Bye 2016, 3rd place, 2895 -> 3030 (+135)The inflation is surprisingly fast.
•  » » 4 years ago, # ^ |   +13 You didn't locked any problem. I was expecting on more submission at the end! :(
•  » » » 4 years ago, # ^ |   +40 Actually I did (http://codeforces.com/contest/750/submission/23453012). Implemented, failed example 1, debugged, passed example 1, failed example 2, debugged, passed example 2, submitted, failed example 1.
 » 4 years ago, # |   -15 Ignorance
 » 4 years ago, # |   +1 Actually, a straight line from West to East on normal global map curves to across the equater on the Earth. For example, half line towards West from England hits around Mexico.So I though problem B was very difficult geometric problem at first (><)
 » 4 years ago, # |   +96 That moment when you lose the first place because of a newbie.
•  » » 4 years ago, # ^ |   +3 That moment when you lose a CF t-shirt because of 1 minute late
•  » » » 4 years ago, # ^ |   +13 Yeah that's exactly the same :D
 » 4 years ago, # |   +95 Errichto, GlebsHP and all who helped, thank you a lot! The problems were great. It was the most popular round in the history of Codeforces.Errichto, looking forward to see you as a problem writer again! I'm really happy to see Limak on the contest :-)
•  » » 4 years ago, # ^ |   0 Sorry , but who is Limak ?
•  » » » 4 years ago, # ^ |   0 Virtual character in his problems.
 » 4 years ago, # |   0 IDK why F is not working for me. My solution: http://codeforces.com/contest/750/submission/23459842 Infinite random tests variant: http://pastebin.com/jE98nJyH At that moments, I always suspicious about author's bug, but for all such situations it was bug on my side.
•  » » 4 years ago, # ^ |   0 Found all bugs, when Infinite random starting to find mistakes after adding shuffle of links. It had first link always pointing towards to root, so... simple asking of first link was eventualy leading to root.
 »