It seems reasonable to discover characters one by one from left to right.

Let's say that we already know the prefix raay and we're looking for the fifth character. We can binary search it in $$$\log 26$$$ queries with queries like raaymzzzzz... to know if the fifth character is at most m. We need $$$N \cdot \log 26$$$ queries, and every query prints a string of length $$$N$$$. The time complexity is $$$O(N^2 \cdot \log 26)$$$, too slow.

Character 'a' is very common so we can always check for the character 'a' first by asking a query like raayazzzzz.... If the hidden string is lexicographically greater than this, we run binary or linear search from 'b' to 'z'. It's still not better than $$$O(N \cdot (N - K)) = O(N^2)$$$ time complexity.

We need to quickly jump over a long block of characters 'a'.

We need to efficiently handle long blocks of characters 'a'. That's possible in $$$O(\log n)$$$ by binary searching the length of such a block. For example, asking a query raayaaaazzzz... tells us if we have at least four characters 'a' after an already known prefix raay.

After finding the length of a block of 'a', binary search the next character from 'b' to 'z'. The total number of queries is $$$O(K \cdot (\log N + \log 25))$$$. Printing that many strings of length $$$N$$$ is fast enough.

To solve a problem optimally, we should always halve the number of possible strings. If there are $$$X$$$ strings that match the answers from all queries so far, then we need to query the $$$X/2$$$-th lexicographically smallest of those strings.

You can use dp or combinatorics to count the number of possible strings at the beginning, say $$$X_0$$$. You need bignums!

Let's imagine a huge list of sorted possible strings, indexed from $$$1$$$ to $$$X_0$$$. Maintain an interval of indices $$$[L, R]$$$, initially, $$$L = 1$$$ and $$$R = X_0$$$. While $$$L < R$$$, ask about string at index $$$m = (L+R)/2$$$. To find that string, we need to use dp or combinatorics to find the $$$m$$$-th lexicographically smallest string with at most $$$K$$$ characters non-'a'. If the "dp or combinatorics" part isn't obvious to you, first solve an easier version: given $$$n$$$ and $$$k$$$, find the $$$k$$$-th lex smallest binary string of length $$$n$$$.

As always, use binary search. Can we divide the search area by two? So, can we divide the rectangle into two halves and go to one half?

problem C here https://drive.google.com/file/d/1ymS9INds6_w06CobKjP0QJILuM2oTNp4/view

As always, use binary search.

There are $$$1000 \cdot 1000$$$ possible objects and we want to find one of them.

Create a list of $$$1000 \cdot 1000$$$ pairs (speed, startingPosition). In each second, go through all pairs and compute where the car would be right now. We got a sequence of possible current positions of the car. Ask a query at the median of that sequence. Go through the list of pairs and leave only those that match the query feedback (LEFT/HERE/RIGHT).

Let $$$N = 1000$$$. We start with $$$N^2$$$ objects and we need $$$O(\log (N^2)) = O(\log N)$$$ iterations of binary search. Each iteration requires iterating possible pairs and there are initially $$$N^2$$$ of them. You might say that the time complexity is $$$O(\log N \cdot N^2)$$$ but we can bound it better. The list of pairs is halved every time so the time complexity is $$$O(N^2 + N^2 / 2 + N^2 / 4 + \ldots) = O(2 \cdot N^2) = O(N^2)$$$.

Instead of finding the median, you can choose a random possible pair and ask about its current position. The expected number of queries is $$$O(\log N)$$$.

Use the "cool improvement" (get random pair instead of the perfect median). Instead of keeping all pairs explicitly, keep a range of possible positions $$$X_L, X_R$$$ for every speed $$$V$$$.

It isn't trivial to choose a random object in such representation. Think like this: There are $$$V$$$ drawers, each with some number of objects. To choose a random object, you need to first choose a drawer using weighted probability. A drawer with more objects inside should be more likely to be chosen.

For every speed $$$V$$$, it's easy to update the range of possible values $$$X$$$ after every query.

Let $$$N = 100\,000$$$. The expected number of queries is $$$O(\log(N^2))$$$ and we iterate an array of size $$$N$$$ every time. That's $$$O(\log(N^2) \cdot N) = O(N \log N)$$$ total time complexity.