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**.

More information can be found here: http://in.harbour.space/icpc/

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 - Новый год и поиск корня 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!

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).

You are always the first person to comment in cf round blog post. Why buddy

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.

`I tried to keep statements shorter than usually`

I agree, however tenshi_kanade won't be happy http://codeforces.com/blog/entry/18764?#comment-237166 http://codeforces.com/blog/entry/18764?#comment-237327

It's always great to know there is actually people who enjoyed those long story!

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.

I like the story when practising, but not during contest...

For my poor English, long story costs me much time.

Great way to end this year

[DELETED]

The legend says that in each round someone has to repeats the same joke

challange: make your rating 2017!

Challenge denied

Even getting to the number of digits of 2017! is almost impossible......

I don't think he meant that..

Hope I can do it :D

Ez :)

Challenge completed

Codeforces Say Goodbye Again! Have a good time！ I want to change my username. And how to do that ? THX

Hey !! Me too. Is there a way by which I can change my user name

(http://codeforces.com/blog/entry/6302) This link will help

thanks!Though I can see nothing but some pictures failed.

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.

veteran = retired

You are eligible for free/cheaper camp if you still can participate in acm-icpc.

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?

And what about high schoolers? Are they too young

And what about those who didn't qualify for WF this year but it was their last chance?

"you still can participate" = "it's possible that you will participate in an official acm-icpc contest somewhen in the future"

I have a lot of games did not attend, in The hope that The contest Goodbye2016 would it be possible for me to rise!

8 problems in 150 minutes for a solo contest.

Geez this is going to be tough.

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.

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.

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.

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.

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. =]

How many problems in the contest? 8 or 7

I think 8 problem

thank you

Mike! +17 rating to everyone please!

If everyone's rating increases by the same amount your relative ranking is still the same.

so, making it optional would be better..

Is the contest rated?

yes

thank you

Goodbye 2016, Hello 2017 and higher rating :)

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.

Nice id of contest : 750

Number 402 is even more interesting for you.

The red contestants:The contest is combined for both divisionsand me

And there are only 100 t-shirts for them, no wonder why they don't wear shirts.

Limak brings me good luck! :D Yeaaah!!

How can I register for it

Frequently Asked Questions

Another contest? Another ** ** ***** meme.

A brilliant way to end the year :D.

условии задач будут на русском или на английском?)

Доступны на обоих языках. Зависит от того какой выберешь

Hoping for expert from this, but now I'm probably jinxing it.

6 will kick out by 7(prime number) 2017 > (1st + last) prime number xD

may I can also say GOODBYE for Div2

Hope I won't say goodbye for Div1

UPD: I'm so happyNo you can't

All's Well That Ends Well:) Hope to give a positive reflection of this Quote on the year 2016...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...

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 ** ** *****? ***, ** ** *****.

Finally I will take part in a round again, after a long time :D

Is it rated?

Upd: Ok, I understood. Just ignore "** ** *****" comments if you don't want downvotessay ** ** *****? is like say Lord Voldemort

** ** *****? question and no downvotes? that's weird!

codeforcces VS long queue . hope codeforces win :)

interesting ... Tourist vs Petr vs AnasAbbas

You are not allllekssssa, this won't work :D

delay, delay, delay :(

I hate nothing more than getting ready and then finding the contest postponed xD

it's not more than when they delayed the contest for 3 more days :(

8.7 k registered users!)

10 mins delay

thanks to the delay 9k user registered

good bye 2016 with a delay! the last delay of this year :P

There could be another one in 10 minutes

I hope so.

Happy new delay!

Contest Delayed. Can't even say I'm surprised!

I thought it was that my computer had broken!

It was like 1 min remaining....

opens IntelliJ, parse contest using CHelperSuddenly 10 mins remaining.. I'am like did I misread the time? ;)need to spawn more server maybe?

Good to see people informing for the delay in the comments. I was right about to start solving but you reminded me, thanks!

Interactive Problem Guide is temporarily blocked by administrator?

almost 9000 registrations!! It's going to be furious!

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

Problem B* :v

Yes , Sorry

The earth is round :/, so it should be mentioned that if we can go in circles or not :(.

The problem should be cancelled.

The contest not the problem.

we can go in circles is demonstrated in sample tc 3.. ?

You can always go West. But you can't go South after hitting the South pole...

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.

So, the answer for

`1`

`40000 South`

is

`NO`

?Yeah, According to the judge, its a NO. :/

I am so stupid :(

There is a sentence in statement about this: "before any of the instructions or while performing one of them".

y wud it be NO?

20000 South + 20000 North=YES ..right?

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.

Damn :/

The word 'clearly' doesn't add any value =)

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.

Howerver in test case:

5 20000 South

1000 North

1000000 West

9000 North

10000 North

Ans: Yes

1000000 west means around the circle but same is not true for north and south, is quite strange for me.

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

What I am saying is 1000000>20000 is allowed for west but not north and south.

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 shapeThe 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.

Something has to be done about B.

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.

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.

worst problemset ever !

worst comment ever

nice problemset!! but i need to improve a lot

I too was expecting a much better problem set..very much disappointed..

Your arguments are overwhelming.

I think the majority is probably people salty about B. It wasn't unclear you just had to read carefully.

Not the worst problemset ever ! it's just your worst performance ever !!!

Tell me result at this test. (task B)

Do not discuss problems during the contest.

oh... sorr

B is a shitty problem. sorry.

After reading problem setter is Errichto i was expecting a great contest :/

same.

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!!

How to solve E?

please someone call AMD

I miss his problems' difficulty

I need to wait 2 minute at last 30 minutes of contest to look code of a participant, it's awful

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

## life

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 :((((

How to approach D?

Hint: MAX_T * n = 150

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.

Hint: Notice that the farthest visited cell will have distance at most 5*30 = 150 (in x and y coordinate).

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.

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!

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.

it's over 9000

How to solve D?

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

ntimes.Also observe that the final grid size is not that big

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.

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)

Let

xbe his initial rating. Write the inequalities after every round, choose the 2 most restricting ones, and from there you can determine the answer.B was a hard problem at the way i understand:

he finishs in north pol with the same direction as first :|

.

I think D is such a great problem (Assuming that I pass system tests of course ;D)!

I agree with you, though i can not figure it out :D

1.Petr

2.tourist

3.rng_58

reminds me of good old memories! ^_^

IN problem B, if Earth is sphere, how come he fall down from earth ? Errichto I was expecting to end my year happily :(

Apparently the solution for this test for B according to judge is NO :

2

25000 South

15000 North

The earth is a sphere. Why is this not allowed?

You cant move south when you are at south pole

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.

or while performing one of themOh. :/

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.

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.

To be honest this contest was very confusing. I wish some things were worded differently or omitted to make problems clearer.

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.. !!!

Goodbye 2016. Goodbye rating.

Nice Set of problems :) Happy New Year In Advance :) Happy Coding :)

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

I mean I get -1, but I suck so that could be entirely wrong.

I also get -1 but I also suck so idk :/

I got -1 too, but I suck too, so it could be wrong

me too -1

-1

-1

I tried to hack Coder2000'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.

A negative value. I failed because I didn't realise this:

"... rating, described with one integer,

possibly negativeor zero."-1, But how come the rating be -1? Just kidding :-p

The 32 pages of people who were hacked on B probably hints at some unintentional ambiguities in the problem.

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.

Many people tried to hack me on problem B, I hope there is no tricky case i missed.

in this case:

3 1000 South 2000 North 1000 South

your solution return yes or no? I tried hack you :[

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..

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.

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.

Hm, maybe, but not for me. For me A and B are basically the same and D is easier than C.

By difficulty I mean the number of solvers.

A to B: 6434/4267 ~ 1.50

B to C: 4267/3100 ~ 1.38

C to D: 3100/1296 ~ 2.39

D to E: 1296/113 > 11

So I don't understand what do you mean.

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%

Statements weren't short :|

Cheated by Errichto :|

Can someone explain how to solve C? Thanks.

binary search

could you explain more ?!

our left bound is 1899 — 200000 * 100

our right bound is 1899 + 200000 * 100

mid = (left + right) / 2

mid — our start rating

we 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;

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 .

I was trying with dynamic programming, which doesn't pass the 10th test, sadly.

let's assume initial rating was x

then at ith step tot rating change =y

then 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

Did exactly this, but failed on Test case 25 :(

Are you considering that rating can be negative? Your variable

`ratinglow`

should start as`-infinity`

.yes it could be negative (1 ≤ n ≤ 200 000). (- 100 ≤ ci ≤ 100). so answer is -20,000,000

I couldn't find some monotone function in this problem, can you explain some?

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)

Let LL be the lower limit of ones rating, and UL is the upper limit.

Now, let the ith contests input is Ci Di

if 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.

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.

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.

I think, it's just psychology

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.

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.

To my problem TestCase :

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.

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

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.

You could have clarified.

How to do that in ongoing contest?

Can someone plz share any ideas to solve problem F?

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.

When you do a good contest: The best problem-set ever When you don't : The worse Come on people!

What could be some initial ideas on E?

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.

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.

To remove 201666622222016 you only need two erase operations.

right, my segtree would store:

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.

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.

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!

Failed to submit solution for F... The connection is not good in china.

Anyway, we enjoyed this contest. Thank you.

But we expected nice problemset from Errichto.

:(:(:(

I think the problems were good. Prob B was clear from the context.

Tourist

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

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.

Well, actually my solution passed with 139 ms time which is pretty solid. Shame I didn't manage to finish writing it during contest.

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

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.

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.

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.

Can you tell me why those overlapping state(same depth and direction) won't give any new cells?

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.`

What was the idea behind F?

"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?

Each testcase has 500 inputs, so I don't think a probabilistic method would work. I'm also curious.

of course it's not that simple :D

I have an idea but I'm not sure if it's correct and it seems it's not the intended one.

first ask question on any node S, then walk in a random path starting from S you will end up in a leaf, now return to S and walk in a random path too but in other direction, merging the two paths you get a path that starts at leaf and end at a leaf.

no it's easy to know which node of this path have maximum height (it's middle node in the path), and you also know its exact height (number of nodes in the path)/2, let's call this node V, now go to parent of V and go into a random path until you reach a leaf again you can know which node have maximum height make this node the new V and repeat until you reach a node that is

direct child of the rootthe worse case to reach direct child of the root is 1+2+3+4+5 = 15 questions most probably you will ask less

if you have asked less than 15 questions then you can ask about the direct child of the root and you have two candidates to be root, ask about on of them if its degree is 2 then the node you asked is the root otherwise it's the other node. in this case you you can at most 16 questions.

but what if you asked exactly 15 questions? then you have to guess the root (1/2) chance of correctness, however if you shuffled to adjacency list of all nodes that you asked then this case will rarely happen. (**UPD**: fruwajacybyk's comment is fixing the this issue in my solution )

I was going to add shuffle line but time was up before I submit so I don't if this idea will pass

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.

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.

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 :(

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?

The best gift for the new year is a new division!

What was the hack in Problem:B ??

pos < 0 || pos > 20000

Hack 13

40 South

60 North

20 South

Answer — NO

Hack 21

40000 South

Answer — NO

I think tourist lost first place because comunodi hacked 7 solutions in his room .

Maybe if Petr wouldn't hack, he could solve F. So, we cant be so sure!

Yes , but now tourist needs only one hack to win while peter hacked 6

Is there any efficient way to find which room a person belongs to?

room 67

you can click on the country flag in the standing page to know the room and view all submission

oh~ I see!

Thanks a lot!

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

ААА

What did you mean russian kid

How to solve E?

system testing__a

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 line

So sad :(

See UPD2 in the post — if that's the only issue with your solution, you're likely to get the points

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 :( .

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)

[offtopic] Congratulations on the new color!

Actually no. If you are exactly at the north pole, whatever direction you would go it would be south.

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 :)

DELETED

is it rated?

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

you should use long long or long long int for rx, because 3000000000 in long int is negative

ohh yeah an extra zero.. but how come it is giving right answer on my pc i am running same code same input?

I think your compiler, you can use codeblock or devc :v

Thanks for help

Contest not yet open for practice? I'm unable to submit code now.

Problem C: my solution failed on test # 32

What I missed?

You didn't check if there was a div1 rating that was lower than any div2 rating.

Thanks

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?

AC solution WA solution The differences between these two code are two "cerr<<"s. Is this function change the variable?

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<<x then x is stored differently and compared differently. x!=90 in TC#19 if you don't cerr. See this submission: http://codeforces.com/contest/750/submission/23456419 It says x==90 is false just one statement above and then prints "YES". See the "A somewhat amusing side note" here for more: http://gynvael.coldwind.pl/?id=535

Please tell how can we clarify a question in ongoing contest?

Please tell how can we clarify a problem statement in ongoing contest if we have doubt in it?

I wonder when I can submit my code...

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. :/

why practice submission is closed ?? :(

when the round will be opened for practice ?

Its open now

thanks

When I can change my nickname ?

Symmetry

Christmas tree

Moral from today's problem D :| If you have choice between bfs and dfs, always choose bfs.

i chose dfs :D

Saddest round of the year , I always fail the Goodbye Round(3 years straight)

Good Bye 2014, 3rd place, 2894 -> 2898 (+4)

Good Bye 2016, 3rd place, 2895 -> 3030 (+135)

The inflation is surprisingly fast.

You didn't locked any problem. I was expecting on more submission at the end! :(

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.

Ignorance

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 (><)

That moment when you lose the first place because of a newbie.

That moment when you lose a CF t-shirt because of 1 minute late

Yeah that's exactly the same :D

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 :-)

Sorry , but who is Limak ?