### Errichto's blog

By Errichto, 7 weeks ago, 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.

slow solution
hint
solution
hard version (optimal number of queries)

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.

hint

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$

hint
solution
cool improvement
hard version

If you know the source of problems 1 or 3, please let me know.  Comments (8)
 » 3 is very similar to NEERC 2013 I pdf
 » Hi, can someone tell the approximate ratings of these problems, so I can figure out If this stream is for me or not?
•  » » at least div1-B
 » Fun fact: during a contest, I solved problem 2 using a (dubious) randomized algorithm. SolutionAsk about $3n/2$ random queries, then do dfs from the maximum. I used some optimizations: stopping random queries when getting a particularly high value, avoiding querying the same cell twice, visiting random directions while doing the dfs. After around $30$ submissions (of the same code), I got $100$ points, although my solution had an error probability of around $10\%$.
 » 3 Hard Binary Search Problems
 » For problem 3, there are at least two different ways to calculate the exact median position among remaining states in linear time $O(X_{\text{max}} + V_{\text{max}})$ per query, which might be useful for an even harder version of the problem. SpoilerBucketing-based approachSuppose without loss of difficulty that $i > 0$. Then, make buckets of positions of size $i$. Then, the state $(X, V)$ gets sent to bucket $\left\lfloor \frac{X + i \cdot V}{i} \right\rfloor = \left\lfloor \frac{X}{i} \right\rfloor + V$, so that if we store for each position $X$ the smallest and largest remaining options for $V$, the number of states sent into each bucket can be calculated efficiently using prefix-sums on the at most $X_{\text{max}} + V_{\text{max}}$ buckets. It is then easy to find the bucket containing the median. Finally, since each value $X$ contributes at most 1 position to the median bucket, the actual median within that bucket can be easily found in $O(X_{\text{max}} + i)$ using counting-sort, or just $O(X_{\text{max}})$ with a linear-time selection algorithm.(Side note: To the best of my knowledge, g++'s implementation of std::nth_element is actually $\Theta(n \log{n})$ on worst-case inputs since its fallback when quick-select performs poorly is sorting-based.) Sorting-based approachFor any $V$, let $X_l(V)$ and $X_r(V)$ denote the smallest and largest values of $X$ such that $(X, V)$ is consistent with the queries already made. If we imagine processing the possible values of $X + i \cdot V$ in increasing order, the events of interest occur at $f_l(V) = X_l(V) + i \cdot V$ and $f_r(V) = X_r(V) + i \cdot V$ for the various possible values of $V$. Everything that happens between two events can be calculated easily with some linear formula. But $f_l$ and $f_r$ are both weakly increasing functions, because $X_l$ and $X_r$ are the point-wise maximum (resp. minimum) of several functions all with slope either $0$ or less than $i$. As a result, we can sort the events of interest in $O(V_{\text{max}})$ by merging these two ascending lists, and then it is straightforward to find the median position in $O(V_{\text{max}})$ time.
 » where i can submit solution of problem a ?
 » Why there is no this task?I think it's harder than them, and there were very few people solved the task correctly.