The Quantum Rescue

Author : Balaji_31

Required Knowledge : Binary Search

Time Complexity : $O(T \cdot (\log N)^2)$

Editorialist : Balaji_31

Approach:

This problem asks for the minimum daily collection amount, $K$, that allows the Avengers to secure at least half the total Quantum Energy Units. $K$ must be a multiple of $M$. The process is a daily cycle: the Avengers collect $K$ units, and then Thanos destroys $P$ percent of the remaining amount.

To find the smallest valid $K$, we can use binary search. Instead of searching on $K$ itself, we search for the smallest multiplier $x$ such that $K = x \cdot M$ is a successful strategy.

For any given $K$, we run a simulation. We track the Avengers collected total and the remaining uncollected units. Each day in the simulation, we add $\min(K, \text{remaining})$ to the Avengers' total and subtract it from the remaining pile. Then, we reduce the remaining pile by $P\%$ (rounding down) to simulate Thanos's attack. This simulation continues until the remaining units hit zero.

If the simulation ends with the Avengers total being at least half of the initial amount, then that $K$ is a valid (though perhaps not minimal) solution.

The binary search uses this simulation as its check:

$\bullet$ If a test $K$ (from the middle of our search range) is successful, we know a solution exists, so we try a smaller $K$ by narrowing the search to the lower half.

$\bullet$ If $K$ fails, it was too small, so we must search the upper half for a larger $K$.

This continues until the search converges on the smallest possible multiple of $M$ that guarantees the Avengers meet their goal. The simulation is fast because the remaining units decrease geometrically, leading to an efficient overall solution.

Here's the time complexity analysis for that exact approach:

$\bullet$ Simulation: The check function is fast. Since $N$ is reduced by $P\%$ (where $P \ge 1$) each night, it shrinks geometrically. This takes $O(\log N)$ time, not $O(N)$.

$\bullet$ Binary Search: We search for a multiplier $x$ in a range of size $\frac{N}{M}$. This takes $O(\log(\frac{N}{M}))$ steps.

$\bullet$ Total: We run the $O(\log N)$ simulation inside each $O(\log(\frac{N}{M}))$ binary search step.

The time complexity per test case is $O(\log(\frac{N}{M}) \cdot \log N)$, which is roughly $O((\log N)^2)$.

For $T$ test cases, the total time is $O(T \cdot (\log N)^2)$. Fast enough.

Setter's Code:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define vll vector<ll>
#define pb push_back
#define mp make_pair
#define endl "\n"
#define mod 1000000007
#define tot(a) a.begin(),a.end()
#define minii *min_element
#define maxii *max_element

void solve()
{
    ll n,m,p;
    cin>>n>>m>>p;
    ll l=1,r=(n/m)+1,mid;
    ll ans=(ll)(1e18);
    while(l<=r)
    {
        mid=(l+r)/2;
        ll val=mid*m;
        ll nn=n;
        ll s=0;
        while(nn)
        {
            if(nn<val)
            {
                s+=nn;
                nn=0;
            }
            else
            {
                nn-=val;
                s+=val;
            }
            nn=(nn-(p*nn)/100);
        }
        if(s>=(n+1)/(2LL))
        {
            ans=min(ans,val);
            r=mid-1;
        }
        else
        {
            l=mid+1;
        }
    }
    cout<<ans<<endl;
}

int main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    ll t;cin>>t;while(t--)
    solve();
    return 0;
}

Tester's Code:

def solve():
    n, m, p = map(int, input().split())
    l, r = 1, (n // m) + 1
    ans = int(1e18)
    while l <= r:
        mid = (l + r) // 2
        val = mid * m
        nn = n
        s = 0
        while nn:
            if nn < val:
                s += nn
                nn = 0
            else:
                nn -= val
                s += val
            nn = nn - (p * nn) // 100
        if s >= (n + 1) // 2:
            ans = min(ans, val)
            r = mid - 1
        else:
            l = mid + 1
    print(ans)


t = int(input())
for _ in range(t):
    solve()