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 usuallyI 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.
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
"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
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 contest is combined for both divisions The red contestants:
and 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!!
Another contest? Another ** ** ***** meme.
A brilliant way to end the year :D.
условии задач будут на русском или на английском?)
условии задач будут на русском или на английском?)
Hoping for expert from this, but now I'm probably jinxing it.
may I can also say GOODBYE for Div2
Hope I won't say goodbye for Div1
UPD: I'm so happy
No you can't
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 downvotes
say ** ** *****? 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!
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
140000 Southis
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".
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.
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 shape
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.
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 PrinceOfPersia
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 n times.
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 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.
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)!
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 them
Oh. :/
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 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.
A negative value. I failed because I didn't realise this:
"... rating, described with one integer, possibly negative or 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;
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 :(
I couldn't find some monotone function in this problem, can you explain some?
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.
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 root
the 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
3
40 South
60 North
20 South
Answer — NO
1
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?
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 ?
Virtual character in his problems.
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.
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.
Can anyone explain problem D?
You can observe that the maximum ends from the starting point, the particle can go is 150 Up,Down,Left,Right. So easily this is a 300*300 grid which our particle than cover. Now, at a given time, our particle can occupy 8 different positions at a cell(The 8 different directions namely). So you can easily simulate this. Think about the memoization states. You'll find there are 300*300*8*30 states at max(row*col*directions*particle_index). Transitions are of O(1) only in between these states as at one states, you can only go to the next two states.
Were there anyone who got AC problems C by binary search?
Yes, idea is to interpret three cases as 0, 1, 2 where 0 — not enough rating to be in 1st devision 1 — all fine 2 — too much rating to be in 2nd division http://codeforces.com/contest/750/submission/23430953
I have to say that problem F is ... Wow
AC on only B and C, failed systest on A, didn't have time to submit D. Still rating increase????????
**LET ME SURPRISE YOU
1.) LOOK AT COLOR AND RATING szawinis
2.) LOOK AT SUBMISSION AND HACKING ATTEMPTS OF P_Nyagolov**
MikeMirzayanov Errichto
Because of magic
Maybe P_Nyagolov gave up after 1 hour 1 minute and started doing wrong hacks.
see difference in timings of hacking attempts
P_Nyagolov is a fkin cheater, no way he could click Ctrl+V so fast. Ban him forever!1!1!1!1
P_Nyagolov is faster than a fkin cheetah!1!111!!!!
I'AM SORRY FOR THIS.
Can we change our handle today as its last day of year and it use to happen on codeforces ?
I know this is not right place to ask but , after sending mails and messages to codeforces and Mike i didn't got any reply this was the only option.
P.S post added by Mike we can change handles now :)
Thanks sir, Happy New Year all.
Rumors have said that it is a yearly event.
(It is also the time of the year where you can't judge a book by its cover)
Problem D:my solution failed on test 15 and don't know what did I missed........
u dp on the wrong state. vis1[x][y][1][t[id]] should be vis1[x][y][1][id]
here you go.
23465573
WOW! Thanks!!!!!!!
another question.... here vis1 should be vis1[505][505][10][31]? (id->n<=30) it should be RE?
That is correct. Thanks for pointing out, I made a mistake. However, accessing an array out of bounds may not give RE, it will just have undefined behaviour. So, I am just lucky the code is still correct.
I found that because I try vis1[x][y][d][id+1] and it was an MLE.... Anyway....it's lucky that I don't need to write a new one....
that's strange. I did one with visited1[600][600][8][30] and I got AC. anyway, u only need [300][300][8][30] to get AC
23466827 I got AC for this submission.
Problem similar to C
I think something is wrong with the interactor in 750F. In particular, the statement says
Yet, compare these two submissions: 23457950 and 23457959 (sorry for the weird indentation idk why). I assert against querying out of bounds and get RTE, while without it I get TLE even with the exit(0), rather than WA.
I spent the last 40 or so minutes trying to debug and find the infinite loop — but it doesn't exist and only in the final couple minutes did I realize the issue was simply a flaw in my algorithm. This is partially why I had 20 incorrect submissions — verdicts weren't making any sense. Am I missing something here?
Anyway, I thought it was overall a nice contest (although I have some qualms with the higher problems) so thanks for giving us all a fun way to end the year!
Errichto For problem B Div2 if a person is at the south pole will he not always move towards the north pole regardless of any given direction and therefore while passing through the poles the person would always move towards the other pole?
That's why a person is only allowed to move North at the South Pole.
How to solve problem G?
А будет Dratuti 2к17?
Limak after he read problem B
There is another way to solve C using binary search. I can't understand why it works, but it passed all tests.
Will there be any news about discounts?
I don't want to go to the Barcelona camp so I am curious if my prize can be given to someone else.
Same story here. I still didn't receive anything about Barcelona, and I'm fine with transferring my discount to anybody else.
Well, I received e-mail from organisers about a week ago.
Congratulations to Petr for beating tourist at Good Bye 2016 contest.
I'm curious about how the top 100 t-shirts are going on...
Anybody received it?