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.
P2. Cloyster (https://codeforces.me/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.
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$$$
If you know the source of problems 1 or 3, please let me know.
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.
Ask 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.
Suppose 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.)For 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.
Why there is no this task?I think it's harder than them, and there were very few people solved the task correctly.