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:

3 Likes
2

We can understand it like,
since the cost of repairing operation is too high, and we only have 1000 coins
so we should try to avoid breaking the tower,
therefore we should try to be on the lower side of voltage ,
so we can divide the array in it in 1:9 , even 1:8 also works
This will surely increase the time taken to find to log (N,10/9), but will reduce the chances of
damaging the tower.

2 Likes