Wednesday, January 21, 2015

Codeforces Round #286 (Div.1 C / Div.2 E) - Mr. Kitayuta vs. Bamboos

Problem Statement:
506C - Mr. Kitayuta vs. Bamboos

Solution:
A very nice problem, another problem that I would never solve if not for the official tutorial :D The official tutorial is very well-written, so you should check them out! Kudos for the problem setter and the writer for the editorial! Only read this if you are still stuck :P This post is more for my self-referential note.

Since there is no easy way to construct an instance of the solution with a global minimum, one should think, is it easier if we guess the answer instead? Hence we turn ourselves to binary search. Let's assume we have a value X, we have a nice property on the search space: if it is possible to hit the bamboos such that at the end of M day all the bamboos are at most of height X, then all bigger X will be feasible, hence we want to find smaller X. Otherwise, if X is not feasible, then all smaller X will not be feasible too, hence in this case we want to find bigger X instead. This forms the basis of the binary search.



Now how to check whether X is feasible? Let's focus on a bamboo. Here we let \(t = \max{0, \lceil \frac{h+aM-X}{P} \rceil } \), which represents the minimum number of hits necessary such that at day M the bamboo will have height X. So how did we derive that? First, ignoring the fact that the bamboo must not have negative heights, we want to achieve \(h+aM-tP \leq X\), and after rearranging the inequality we will get \( \lceil \frac{h+aM-X}{P} \rceil \leq t\). Now let's check whether hitting t times will ensure that the bamboo at day M will have height less than X. Imagine that we allow the bamboo to grow freely from day 1, and we only hit the bamboo t times only at the last day (that is, before it grows for the last time). Here we have 2 cases:
1. The height of the bamboo after t times of hitting is still positive, hence we will definitely have the height less than X after it grows at the end of day M.
2. The hight of the bamboo is negative. Then it will be only less than X if the growth rate of the bamboo is less than X, since at the end of day M it must grow once.

Next, calculate all t of each bamboo, and we perform a trivial check: if the sum of all t is bigger than KM, then there are more hitting than we can afford, so we must conclude that X is not feasible. Otherwise, continue.

From here, we need to find a way to distribute the job of hitting the bamboos that is congruent with the constraints. Here we have a clever way to do it:
1. Let's consider each bamboo one by one again. Here we know that we need to hit the current bamboo t times.
2. We actually have this property: if the i-th hit is performed before a certain day \(d_i\), then it is not possible for the bamboo to have height at most X at day M! That means, for each i-th hit, we can find the earliest time in which we can hit the bamboo. Why are we so concerned with this? You'll see later.
3. So how do we calculate \(d_i\) for each i-th hit? Starting from i = 1 to t, we do:
Let's call \(D_r\) be the remaining number of days the bamboo can grow since last hit, given that the last hit was done in day \(d_{i-1}\). Also, define \(T_r\) as the number of remaining hits we can perform, given that we already performed i-1 hits. Finally let \(H\) be the height of the bamboo currently. Now, how many days d since \(d_{i-1}\) can we perform the i-th hit earliest? Whatever the value of d will be, it must satisfy
\([H+da - P] + (D_r - d) a - (T_r-1)P \leq X\), where \([x] = \max{0,x}\).
We will always have two possible values:
3.1. We want to perform the hit only at \(d\) where hitting the bamboo will not lead to negative height. This means \(H+da-P\) must be strictly bigger than 0. Hence we have \(\lceil \frac{H-P}{a} \rceil \leq d\), therefore we would like to choose the smallest d possible, which is when the equality occurs.
3.2. We also may want to perform the hit when the height of the bamboo is still less than \(P\), hence negative height. But if we do so, we must ensure that using the rest of the hits on the last day will allow the bamboo to have height at most X. This means \(0 + (D_r-d)a - (T_r-1)P \leq X\). Therefore we have \(\lceil \frac{D_ra-(T_r-1)P-X}{a} \rceil \leq d\), so we choose the lowest d possible. But this value of d is only valid if and only if \(\lceil \frac{H-P}{a} \rceil > d\), otherwise the height of the bamboo after the i-th hit won't be negative in the first place.
3.3 Choose the smallest of the feasible choices. So for finally \(d_i = d + d_{i-1}\).
4. Here I forgot to mention that we need to maintain an array day[i], which keeps track on the number of hit performed in day[i]. So depending on \(d\) calculated, we will increment day[\(d_i\)] by one.
5. Update \(T_r\), \(D_r\), and \(H\) accordingly.

After the above operation (done in O(KM)), we need to check whether day[i] is a feasible distribution of hitting jobs. Here we can iterate from i = 0 to M, each time we see the total number of jobs at day[i] is bigger than K, we can simply forward day[i]-K jobs to day[i+1]! Why, because by definition each hitting job performed before forwarding is that of earliest possible, hence pushing them to later days will still be valid! It remains to check that at day[M] the total jobs is less than K. Because of this clever arrangement, we only need O(K(M+1)) operations in total check if there is a feasible distribution of hitting jobs.

So in total we have complexity of \(O((N+K(M+1))\lg{10^{14}}\) where \(10^{14}\) is the worst case search space. A great problem!


#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
long long a[100005],h[100005];
int N, M, K;
long long P;
int day[5003];
int t[100005];
bool check(long long X) {
    for(int i=0;i<M;++i){day[i] = 0;}
    long long sum = 0;
    for(int i=0;i<N;++i){
        long long T = max(0LL, (h[i]+a[i]*M-X)/P + ((h[i]+a[i]*M-X) % P == 0 ? 0 : 1LL));
        if((h[i]+a[i]*M-X)<0) T = 0;
        t[i] = (int) T;
        sum += T;
    }
    if(sum > K*M) return false;
    for(int i=0;i<N;++i){
        long long H = h[i];
        long long Dr = M;
        long long Tr = t[i];
        long long d = 0;
        while(Tr > 0) {
            long long bigger = (P-H)/a[i] + ((P-H)%a[i] == 0 ? 0 : 1LL);
            if((P-H)<0)bigger = 0;
            long long smaller = (Dr*a[i] - (Tr-1)*P - X)/a[i] + ((Dr*a[i] - (Tr-1)*P - X)%a[i] == 0 ? 0 : 1LL);
            if((Dr*a[i] - (Tr-1)*P - X) < 0)smaller = 0;
            if(smaller < bigger){
                day[d+(int)smaller]++;
                Dr -= smaller;
                H = 0;
                d += smaller;
                if(d >= M) return false;
            } else {
                day[d+(int)bigger]++;
                Dr -= bigger;
                d += bigger;
                if(d >= M) return false;
                H = H + bigger * a[i] - P;
            }
            --Tr;
        }
    }

    for(int i=0;i<M-1;++i){
        if(day[i] > K){
            day[i+1] += day[i]-K;
        }
    }
    return (day[M-1]<=K);
}

int main(){
    int u,v;
    scanf("%d%d%d",&N,&M,&K);
    cin >> P;
    for(int i=0;i<N;++i){
        scanf("%d%d",&u,&v);
        h[i] = u;
        a[i] = v;
    }
    long long lo = 0, hi = (long long) 5e13, mid;
    while(lo <= hi){
        mid = (lo+hi)/2LL;
        if(check(mid)){
            hi = mid-1LL;
        } else {
            lo = mid+1LL;
        }
    }
    cout << lo << endl;
    return 0;
}