Observation 1

Type 1 queries can only provide us relative position of keys corresponding to the characters. Since the structure of the keyboard is symmetrical about the vertical axis, it is impossible to distinguish between two keyboards which are mirror images of each other with respect to the line of symmetry using Type 1 queries alone. We need our Type 2 query to distinguish between them. But can we use any character to do so?

Observation 2

There are two keys in the whole keyboard such that if we apply a Type 2 query on the character of these keys, we will still not be able to distinguish between the mirror images or in other words, our precious Type 2 query will be wasted. Let’s call these keys and the characters of these keys Unsafe (shown in Red below) and other keys and characters Safe (shown in Green below).

We need to make sure that we don’t use a Type 2 query on an Unsafe character. So, how can we determine if a character is Unsafe or not using only Type 1 queries?

Observation 3

Let’s pick any arbitrary character $c$ and find its distance from all other characters using Type 1 queries of length $2$. If $c$ is an unsafe character then there will be exactly two characters having the maximum odd distance from $c$ among all the characters. otherwise, there will be exactly one such character.

• Proof

Observation 4

If we know the exact position of two characters $c$ and $d$ such that $c$ is in the first or third row and $d$ is in the second row and we know the distance of all other characters from both $c$ and $d$, then we can uniquely determine the exact position of all other characters from this information.

• Proof

Suboptimal Solution (69 Queries)

Pick any arbitrary character $c$ and find the distance of all other characters from this character using $35$ Type 1 queries. Now, check if $c$ is Unsafe or not using Observation 3.

• $c$ is Unsafe. In this case, there are only two possible keys which may correspond to $c$. To determine whether $c$ lies in the first row or the third row, check the maximum even distance. If $c$ lies in the first row, this distance will be $14$ else this distance will be $16$. Also, any character lying in the second row will be having an odd distance. Pick any of them as $d$ and apply the Type 2 query on $d$ to get its exact position. Now, find the distance of all other characters from $d$ using $34$ Type 1 queries and then by Observation 4, we can determine the exact position of all other characters.
• $c$ is Safe. In this case, find the exact position of $c$ using the Type 2 query. Using Observation 3, we know that at most $1$ character will be having the maximum odd distance from $c$ and its position can also be uniquely determined depending on whether $c$ lies in the first or second or third row and whether it lies to the left or to the right of the line of symmetry. Choose this character as $d$ and find the distance of all other characters from $d$ using $34$ Type 1 queries. Then, by Observation 4, we can determine the exact position of all other characters.

So, we used a total of $35+34=69$ Type 1 queries and $1$ Type 2 queries in either case. This is sufficient to get around $66.23$ points.

Optimization to 57 Queries

Now that we have a solution using $69$ queries, let’s try to eliminate $12$ queries from it. Let’s group the remaining $34$ characters other than $c$ and $d$ according to their distance from $c$. It is not hard to see that no matter wherever $c$ is, there will be at least $12$ such groups. Now if we know the location of all characters in a group except one, we can easily determine its location because there will only be one valid location for this character to exist. So, we can skip the Type 1 query of this character with $d$, thus reducing one query per group. In total, we can reduce at least $12$ queries, reducing the query count to $57$ queries which is sufficient to get $100$ points (with a margin of even $3$ more queries for solutions with bad implementation).