Hi. I think these are nice medium-hard interactive problems. I will discuss solutions in a stream today at https://www.twitch.tv/errichto.
UPD, recording is here https://youtu.be/9oEihYrAR5kUPD and I added text solutions in this blog.
P1. Mostly A — You're given two integers $$$N$$$ and $$$K$$$ ($$$N \leq 50\,000$$$, $$$K \leq 10$$$). You need to find a hidden string of length $$$N$$$ with lowercase English characters a-z. At most $$$K$$$ characters are different than 'a'. You can choose your own string of length $$$N$$$ and you will get info YES/NO whether your string is lexicographically smaller than the hidden one. There is no explicit limit on the number of queries. There's still some time limit (say, 2 seconds).
Hard version: Minimize the number of queries.
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
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$$$.
P2. Cloyster (https://codeforces.com/gym/102341/problem/C) — There's a grid $$$N \times N$$$ ($$$N \leq 2000$$$), each cell with some value. You can ask at most $$$3 \cdot n + 210$$$ queries "get value at cell (i, j)". Find the cell with the maximum value. For each of other $$$N^2 - 1$$$ cells, it's guaranteed that at least one adjacent cell has a greater value. Two cells are adjacent if they share a side or a corner.
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?
P3. Moving Car — A car on an infinite line starts at unknown position $$$X$$$ and unknown constant speed $$$V$$$ ($$$1 \leq X, V \leq 1000$$$). After $$$i$$$ seconds, it will be at $$$X + i \cdot V$$$. At time $$$0$$$ and then after every second, you get to ask about some position and you get a response whether the car is on the left, on the right, or at this position. Use at most 1000 queries to find values $$$X$$$ and $$$V$$$.
Hard version: $$$1 \leq X, V \leq 10^5$$$
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.
If you know the source of problems 1 or 3, please let me know.