MAXEP - Editorial

general
,
1

PROBLEM LINK:

Div 1
Div 2
Practice

Author: Full name
Tester: Full name
Editorialist: Oleksandr Kulkov

DIFFICULTY:

SIMPLE

PREREQUISITES:

Binary search

PROBLEM:

You’re given integer 1 \leq N \leq 1.5 \times 10^5. You need to guess some number x such that 1 \leq x \leq N, for that you may ask arbitrary number y and you’ll know if y < x or not. If y < x you’ll pay 1 coin and if y \geq x you’ll pay c+1 coins, where 1 \leq c \leq 150 is given integer. You need to guess x before you run out of coins and you have 10^3 coins at the start.

QUICK EXPLANATION:

Use binary search, but split segment as 1:9.

EXPLANATION:

Let’s count what amount of coins you have to use to find arbitrary number x if there are N variants of it.

dp_1 = 0
dp_N = \min\limits_{y=2}^{N} \max(1+c+dp_{y},1+dp_{N-y})

This formula would take O(n^2) to be computed, but luckily 10^3 coins is way more than enough to guess the number and we may allow ourself some margin from optimal solution. You may see that if for segment [l;r] we will take y=\left \lfloor \dfrac{9l+r}{10}\right\rfloor, it will allow you to guess any number x \leq 1.5 \times 10^5 for c=150 in at most 603 coin. Thus you may modify binary search to solve the problem:

int N, c;
cin >> N >> c;
int L = 1, R = N;
while(R - L >= 1) {
    int y = (9 * L + R) / 10;
    cout << 1 << ' ' << y << endl;
    int res;
    cin >> res;
    if(res == 0) {
        L = y + 1;
    } else {
        R = y;
        cout << 2 << endl;
    }
}
cout << 3 << ' ' << L << endl;

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.

Tester’s solution can be found here.

RELATED PROBLEMS:

1 Like