PROBLEM LINK:
Contest - Division 3
Contest - Division 2
Contest - Division 1
DIFFICULTY:
MEDIUM-HARD
PREREQUISITES:
Adhoc, Geometry, Implementation
PROBLEM:
There is a hidden keyboard consisting of 36 keys. You may ask the following queries:
- ?\ S - Returns the sum of the manhattan distance between adjacent characters of string S on the keyboard. Atmost 180 queries of this type.
- ?\ c - Returns the position of the key with character c. Atmost 1 query of this type.
Determine the configuration of the keyboard.
EXPLANATION:
Notice: You may also refer to this beautifully written editorial!
Alert: As this is an adhoc, implementation heavy problem, the below editorial only covers the ideas behind the model approach without touching upon the cases in much detail. Some of you may find the code linked below better approachable, which is much more verbose (and shorter than the editorial!)
For sake of brewity, we don’t refer to the characters of the keyboard by their values at all. Instead, every \LaTeX typewritten letter is a variable representing some character of the keyboard.
Let f(S) represent the value returned by a query of the first type for a given string S. Observe that the value of f(S) is unchanged when the entire keyboard is flipped over (such that each row gets reversed). Thus, queries of the first type are insufficient to determine the complete orientation of the keyboard.
The role of the type 2 query is to therefore calculate the final orientation of the keyboard; We’ll get to this later.
For now, let’s start by solving a simpler subproblem.
Imagine all the keys are placed arbitrarily in 1 row (instead of 3). How would you solve the problem then?
Naive solution
Start by picking any character x (remember, x is a variable pointing to one of the 36 characters!). Determine the distance of every other character to x.
Now, it’s easy to see that there are atmost two characters that are d units away from x (for all valid d). One of them will be to the left of key with value x, and the other to the right.
Then, place the characters with distance 2 from x, to the left and right of x arbitrarily. We will determine the proper ordering at the end.
Recursively place the characters at distance d (for d={4,6,8,\dots} increasingly) to the left/right of the currently reconstructed keyboard, after determing if the character is closer to the left or right end of the constructed keyboard (for each d, we make exactly 1 query).
Finally, query the location of the leftmost character, and reverse the constructed keyboard (if required) to fit the specified position of the character.
This approach requires at best, 35+\lceil 33/2 \rceil queries of type 1 and 35+34 queries at worst (when key x is at the end of the keyboard).
Now, it is possible to optimise the worst case scenario (by realising when we’ve constructed the keyboard upto one end, and placing all keys to the other end without making any queries) but handling the edge cases becomes convoluted when there are 3 rows (rather than just 1).
Note: It is possible to solve the original problem using a similar technique as mentioned above. However, the required implementation is simply cancerous 
.
Cleaner Approach (aka, the solution)
Select a character x and determine the distance of every other character to x. Then, select the furthest most character y from x. Clearly, y is at one end of the keyboard.
Next, query the position of character x, which can be used appropriately to determine which end of the keyboard y is present at.
Observe that there exists atmost one key in the keyboard at a distance of d_1 and d_2 from keys x and y respectively. In other words, the location of every character in the keyboard can be uniquely determined by it’s distance from characters x and y.
Thus, when there are multiple characters (whose locations we have not ascertained) at a distance d from x, we can iteratively query their distance from y, with which we can uniquely determine the position of the character on the keyboard.
When there is just one character at distance d, we can simply assign this character to the (only) undecided key that is at distance d from key x.
It is not hard to see that this approach uses \le 60 queries. While this approach may seem more complicated than the previous one, it scales well to the original problem!
For instance, notice that we never utilised the constraint of there being atmost 2 keys at distance d from x.
The other assumption was that there exists no two keys at the same distances from x and y respectively. This however doesn’t hold in the original problem (counter-example: x at location (1,1) and y at (3,11) in the keyboard; keys (1,4) and (3,1) are at the same distances from x and y respectively).
The remedy is simple - select the furthest most key in the adjacent rows (aka, at an odd distance from x). It is easy to verify that the assumption then holds.
The final assumption was that querying the position of x was sufficient to determine the complete orientation of the keyboard. This doesn’t hold when x is the middlemost key in the row (why?)
This can be tackled by querying the location of y instead, and appropriately determining the position of key x.
Thus we have found an optimal solution for the problem.
SOLUTIONS:
Editorialist’s solution can be found here.
Author’s solution can be found here.
Tester’s solution can be found TBD.