Errichto's blog

By Errichto, 3 years ago, In English

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.net/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.

  • Vote: I like it
  • +235
  • Vote: I do not like it

| Write comment?
»
3 years ago, # |
  Vote: I like it +32 Vote: I do not like it

3 is very similar to NEERC 2013 I pdf

»
3 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Hi, can someone tell the approximate ratings of these problems, so I can figure out If this stream is for me or not?

»
3 years ago, # |
  Vote: I like it +51 Vote: I do not like it

Fun fact: during a contest, I solved problem 2 using a (dubious) randomized algorithm.

Solution
»
3 years ago, # |
  Vote: I like it +145 Vote: I do not like it

3 Hard Binary Search Problems

»
3 years ago, # |
  Vote: I like it +26 Vote: I do not like it

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.

Spoiler
»
3 years ago, # |
  Vote: I like it -8 Vote: I do not like it

Why there is no this task?I think it's harder than them, and there were very few people solved the task correctly.