Hotter-colder
Time limit1sMemory limit256 MB
An interactive problem: locate a hidden point in a d-dimensional integer grid using at most 100d queries that only report whether the latest Chebyshev distance got smaller or larger.
- Level
Hard8 of 10
- Topics
- Binary search, Implementation, Math, Geometry
- Solved
- No attempts yet
Problem
This is an interactive task.
Small Tuple and her brother Kortesh live happily in their -dimensional world. Today they came up with an idea to play hide-and-seek, and Kortesh will be the first seeker. As finding people in large-dimensional worlds is usually quite a difficult task, they decided to use their walkie-talkies for communication. Moreover, each of them took their GPS receivers.
Tuple hid in one of the points of the Hypercube Forest and is not going to move until Kortesh finds him. The forest is a hypercube with its side equal to ; it contains all -dimensional points whose coordinates are integers from . Kortesh walks round the forest and once in a time uses his walkie-talkie and tells Tuple his current location. Then, Tuple responds with a single word: hotter if Kortesh came closer to Tuple since their last (i.e., the most recent) communication, or colder otherwise.
Given -dimensional points , Tuple says that is closer to than if [ \max_{i = 1, 2, \ldots, d} |x_i - p_i| < \max_{i = 1, 2, \ldots, d} |y_i - p_i|. ]
Unfortunately, Kortesh forgot to charge his walkie-talkie and the battery will allow him only for communications. Help him find his sister before he loses the ability to contact her.