## Friday, May 15, 2015

### Codeforces 536A - Tavas and Karafs

Problem Statement:
536A - Tavas and Karafs

Solution (from the official editorial, which is more succinctly written. I'm placing it here for my self reference.):
Given a sequence $$s_i$$, we are only allowed to perform m-operation: choose at most m numbers in the sequence and decrease them by 1. Then it is provable that by performing at most t m-operation, we can reduce all $$s_i$$ to 0, if and only if $$\max s_i \leq t$$ and $$\sum_i s_i \leq tm$$.
Proof:
Forward direction: if we can reduce all $$s_i$$ using t operations, then it is clear that the biggest $$s_i$$ must not exceed t, and that the total sum of $$s_i$$ will not be more than $$mt$$. The interesting part is to prove that this conditions are sufficient.

Backward direction: given that we have $$max s_i \leq t$$ and $$\sum_i s_i \leq mt$$, we will prove that we can reduce all $$s_i$$ to 0. The proof is due to mathematical induction on the total sum of $$s_i$$. Suppose that for all $$s_i$$ such that $$\sum s_i \leq K$$ satisfying the above conditions for all possible (m,t) are all reducible to 0. We will show that it is also true for all $$\sum s_i = K+1$$. We have two possibilities:
1. There are at least m $$s_i$$ which are non-zero, hence there are at most m $$s_i$$ which are equal to t (otherwise, if there are more than m $$s_i$$ equal to t, then their sum will be more than mt, a contradiction). We perform one m-operation on these m numbers containing all $$s_i$$ with value equals to t. The resulting $$s_i$$ will have maximum of t-1, with sum at most K. By induction definition, the resulting $$s_i$$ can be reduced to 0 using at most t-1 m-operation, and therefore the original $$s_i$$ can be reduced to 0 using at most t m-operation.
2. There are less than m $$s_i$$ which are non-zero. We perform one m-operation on these numbers, hence the resulting $$s_i$$ will have a maximum of t-1, with sum at most K. Hence similar to case 1, we conclude that the original $$s_i$$ is reducible using at most t m-operation.

The base case would be K = 0, where the sum of $$s_i$$ must be equal to 0, hence maximum $$s_i$$ is 0, and it requires 0 time of m-operation to reduce all $$s_i$$ to 0.

With this results, the problem can be solved using a binary search as follows:

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

int a, b, n;
int l, t, m;
int main(){
scanf("%d%d%d",&a,&b,&n);
for(int i=0;i<n;++i){
scanf("%d%d%d",&l,&t,&m);
int lo = l, hi = (int)1e9, mid;
while(lo<=hi){
mid = (lo+hi)/2;
long long val = 1LL*(2LL*a + 1LL*(l+mid-2)*b)*(mid-l+1)/2LL;
if(1LL*a+1LL*b*(mid-1) > t ||
val > 1LL*m*t) {
hi = mid-1;
} else {
lo = mid+1;
}
}
if(hi >= l) printf("%d\n",hi);
else printf("-1\n");
}
return 0;
}