MNERROR - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: biggestotaku
Tester: pols_agyi_pols
Editorialist: iceknight1093

DIFFICULTY:

Simple

PREREQUISITES:

Binary search or math

PROBLEM:

There’s a hidden non-decreasing boolean array of length N.
You can query for the value at any given index at most Q times.
However, if you ever receive a 1, no more queries can be made.

After all queries have been made, you need to make a guess as to where the first 1 in the array is.
The error of your guess is defined to be the difference between it and the actual value.
Find the minimum possible error if you query optimally.

EXPLANATION:

First, it’s obvious that we should always query indices only in increasing order.
That is, if we some query index x and then later some index y, x \lt y must hold.
This is because if we query x and receive a 1 we must stop immediately and no further queries can be made anyway; whereas if we receive a 0 we know for sure that everything before index x contains a 0 too; so there’s no point querying them.

Now, suppose we make the queries x_1, x_2, \ldots, x_k.
What’s the best possible guess we can make?

There are two possible cases:

  1. When querying x_k, we received the value 1.
    Now, the only information we have is that A_{x_k} = 1 but A_{x_{k-1}} = 0.
    So, the split point lies somewhere between indices x_{k-1}+1 and x_k.
    We have no idea which one it is, so the best we can do is to guess the midpoint of this range, i.e \displaystyle \frac{x_{k-1} + 1 + x_k}{2}, to be not too far away from either end.
    (If this fraction is not an integer, round it either up or down - it doesn’t matter.)
  2. Alternately, when querying x_k, we received the value 0.
    Now we know that A_{x_k} = 0 and A_{N} = 1 but nothing inbetween.
    Again, the best we can do is to guess the midpoint \displaystyle \frac{x_k+1+N}{2}.

With this knowledge, let’s try to fix a maximum allowed error D and see if we can possibly use at most Q queries to achieve this.

The first query cannot be too large, because we can’t be too far away from 1.
Specifically, if our first query is at index x_1, then \text{ceil}\left(\frac{1+x_1}{2}\right) must be at most D distance away from 1; since if we receive a 1 on the first query we must guess \text{midpoint}(1, x_1).

This forces x_1 \le 2D+1.
Clearly, it’s optimal to just choose x_1 = 2D+1 (or technically, x_1 = \min(N, 2D+1)) since it allows us to “eliminate” the maximum number of options.

So, with one query we’re able to eliminate 2D+1 points.
We now have Q-1 queries left for the remaining N - (2D+1) points.
Clearly, the exact same strategy applies: the second query x_2 cannot be made too far away from 2D+2, so again we’re able to eliminate another 2D+1 points, and so on.

In general, with Q queries, we’re able to eliminate Q\cdot (2D+1) points.
Let R = N - Q\cdot (2D+1) denote the number of points remaining.
Then, as long as R \le 2D+1 we’re actually fine, because:

  • If any of the Q queries result in a 1, we can choose the midpoint of the corresponding segment and obtain an error of at most D.
  • If all Q queries result in a 0, then we know the answer lies in the remaining segment of length R.
    We must guess the midpoint of this segment, which can give an error of at most D if and only if R \le 2D+1.

So, we’re actually able to account for (Q+1) \cdot (2D+1) points in total.
If this value is \ge N then we have a strategy to obtain an error of at most D, otherwise we don’t.

The solution is hence to find the smallest integer such that (Q+1) \cdot (2D+1) \ge N.
This can be done easily in \mathcal{O}(\log N) time with binary search, or you can use a bit of math and ceiling division to get there in constant time.

TIME COMPLEXITY:

\mathcal{O}(\log N) or \mathcal{O}(1) per testcase.

CODE:

Editorialist's code (PyPy3, binary search) 
for _ in range(int(input())):
    n, q = map(int, input().split())
    
    lo, hi = 0, n
    while lo < hi:
        mid = (lo + hi) // 2
        if (q+1) * (2*mid + 1) < n: lo = mid + 1
        else: hi = mid
    print(lo)
Author's code (C++, direct formula) 
#include<bits/stdc++.h>
#define int long long
#define nl "\n"
using namespace std;

int cel(int p, int q) {
    return (p + q - 1) / q;
}

void solve() {
    int n, q;
    cin >> n >> q;
    int k = cel(cel(n, q + 1) - 1, 2);
    assert((2 * k + 1) * (q + 1) >= n && (2 * k - 1) * (q + 1) < n);
    cout << k << nl;
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t = 1;
    cin >> t;
    int cid = 0;
    while(t--){
        solve();
    }
}