PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Setter: Volodymyr Mykytsei
Tester: Encho Mishinev
Editorialist: Taranpreet Singh
DIFFICULTY:
Medium
PREREQUISITES:
Basic Maths and difference arrays.
PROBLEM:
In a queue with N people standing having anger levels given in an array A, find out the leftmost position Chef can stand in the queue without attracting more than K units of anger. If Chef joins the queue before Person p, He attracts total wrath \left\lfloor \frac{A[p]}{1} \right\rfloor + \left\lfloor \frac{A[p+1]}{2} \right\rfloor + \left\lfloor \frac{A[p+2]}{3} \right\rfloor + \ldots + \left\lfloor \frac{A[N]}{N-p+1} \right\rfloor which should not be more than K. If he cannot stand before any person, he stands at the end of queue.
QUICK EXPLANATION
- Instead of calculating the wrath level w[p] for position p directly, we try to find out how much anger of person at position p affect wrath levels at positions.
- Person at position p contribute \left\lfloor A[p]/1 \right\rfloor to w[p], \left\lfloor A[p]/2 \right\rfloor to w[p-1], \left\lfloor A[p]/3 \right\rfloor to w[p-2] and so on, till \left\lfloor A[p]/(p) \right\rfloor to w[1].
- We split this process into two parts. From position p to p-SQRT(A[p]), wea update the effect on wrath levels manually. For remaining positions, we can see, that the wrath levels don’t increase by a[p]/SQRT(A[p]), try all values x from 1 to a[p]/SQRT(A[p]) and find out range of elements whose wrath level is increased by x and store these results in difference array.
- We can take prefix sum array of the above difference array and add to it the wrath levels calculated naively. Now we have wrath levels for each position. Just check if any valid position exist and print the required position.
EXPLANATION
Let us define w[p] as the wrath level Chef has to face if he joins the queue just before the person p in the queue. We need to find the smallest p such that w[p] \leq K or determine if no such p exist.
The main trouble here is the calculation of w array, where w[p] is given by \left\lfloor \frac{A[p]}{1} \right\rfloor + \left\lfloor \frac{A[p+1]}{2} \right\rfloor + \left\lfloor \frac{A[p+2]}{3} \right\rfloor + \ldots + \left\lfloor \frac{A[N]}{N-p+1} \right\rfloor
Let us reverse the process. Instead of considering the wrath at each position separately, we try to find out the contribution of A[p] in wraths of various positions. It can be seen that the end result doesn’t change.
So, Let us observe with a few values, how they contribute to adjacent positions.
10: 1 1 1 1 1 2 2 3 5 10
16: 1 1 1 1 1 1 1 1 2 2 2 3 4 5 8 16
46: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 3 3 3 3 4 4 5 5 6 7 9 11 15 23 46
Reversing the rows now for understanding
10: 10 5 3 2 2 1 1 1 1 1
16: 16 8 5 4 3 2 2 2 1 1 1 1 1 1 1 1
46: 46 23 15 11 9 7 6 5 4 4 3 3 3 3 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
What we can notice from above is that initially, the values decrease very fast after reaching a limit, after which it reduces one by one till it becomes 1. It can also be seen by observing values of x/v - x/(v+1), the change in consecutive terms, as v grows large. Mathematical proof for this can also be derived in a similar manner.
It can be seen (and proved too) that after \left\lfloor x/v \right\rfloor reaches \left\lfloor \sqrt x \right\rfloor, The value changes by at most one while moving to the right. Let us find out the range of elements (In terms of distance from position p where we are trying to find the contribution of A[p]).
To find the number of values with contribution v, we find the last position where contribution is v and the last position where contribution is v+1 or higher. Last position having contribution at least v is at distance x/v from p. Similar explanation goes for v+1. Then, the number of occurrences of v is just the difference between the above two.
Consider example. Let x = 46 and we want to find the range of positions where contribution is 2. Last position where contribution is at least 2 is 46/2 = 23 while last position where contribution is at least (2+1) = 3 is 46/3 = 15. So, 23-15 = 8 positions have contribution 2, the positions at distance 16 to 23 from position of x in array A.
But handling contribution value by value also leads to O(N*max(A_i)) solution, since it requires us to calculate the contribution of each value from 1 to A_i.
So, We merge the naive solution with this one. Up to first \sqrt x positions from position p, we can update contribution value by value in O(\sqrt{A[i]}) complexity. Now, The remaining positions all have contribution from current position is up to \sqrt x, so for every value from 1 to \sqrt x, we find the ranges where contribution is exactly a given value. This also takes O(\sqrt{A[i]}) time per value.
So, our final solution looks like
For every position p, we try to calculate its contribution in wrath levels of all positions which are affected by A[p]. This we do in two steps. For positions within range p-\sqrt{A[p]}, we update each value manually using naive approach. For remaining positions, we find the range of positions which gets affected by the same value due to A[p]. Since there are only \sqrt{A[p]} different values left now, This step also takes O(N*\sqrt{A[i]}) time.
For implementation, we can use difference arrays. For incrementing range [l,r] by x, we increase diff[l] by x, reduce diff[r+1] by x. Now, When we take the summation array of this array as sum[i] = sum[i-1]+diff[i], we automatically have increased values in range [l,r] by x in sum array.
Hence, Overall solution has the time complexity O(N*\sqrt{max(A_i)}).
A note on Time Limit
I know the Time Limit for this problem was quite strict and many of you had to go for constant optimizations and reducing constant factors just to make that last TLE file to AC. The reason behind such tight TL is that to prevent non-intended solutions to pass. The solution which tries to calculate all wrath levels naively. To fit the time limit, you have to realize that division is a heavy operation as compared to other arithmetic operations and using it sparingly makes sense.
Time Complexity
Time complexity is O(N* \sqrt{max(A[i])}) per test case.
AUTHOR’S AND TESTER’S SOLUTIONS:
Setter’s solution
Click to view
Tester’s solution
Click to view
#include
#include
#include
using namespace std;
typedef long long llong;
int t;
int n;
llong k;
int a[100111];
llong ans[100111];
llong paint[100111];
void paintRange(int L,int R,llong val)
{
if (L < 1)
L = 1;
if (R < 1)
R = 0;
if (L <= R)
{
paint[L] += val;
paint[R+1] -= val;
}
}
int main()
{
int test;
int i,j;
scanf("%d",&t);
for (test=1;test<=t;test++)
{
scanf("%d %lld",&n,&k);
for (i=1;i<=n;i++)
{
ans[i] = 0LL;
paint[i] = 0LL;
}
for (i=1;i<=n;i++)
{
scanf("%d",&a[i]);
///One-time values
int lastval;
for (j=1;j*j<=a[i];j++)
{
int val = a[i] / j;
if (i - j + 1 >= 1)
ans[i - j + 1] += (llong)val;
lastval = val;
}
//Use-up last value
while(j <= a[i] && a[i] / j == lastval)
{
if (i - j + 1 >= 1)
ans[i - j + 1] += (llong)(a[i] / j);
j++;
}
if (j > a[i])
continue;
int v = a[i] / j;
for (j=v;j>=1;j--)
{
int L, R;
L = a[i] / (j + 1) + 1;
R = a[i] / j;
if (L <= R)
{
paintRange(i - R + 1, i - L + 1, j);
}
}
}
llong pt = 0;
for (i=1;i<=n;i++)
{
pt += paint[i];
ans[i] += pt;
}
for (i=1;i<=n;i++)
{
if (ans[i] <= k)
break;
}
printf("%d\n",i);
}
return 0;
}
Editorialist’s solution
Click to view
import java.util.*;
import java.io.*;
import java.text.*;
//Solution Credits: Taranpreet Singh
public class Main{
//SOLUTION BEGIN
void pre() throws Exception{}
void add(long[] sum, int l, int r, long val){
sum[l]+=val;
sum[r+1]-=val;
}
void solve(int TC) throws Exception{
int n = ni();long k = nl();
long[] ans = new long[1+n], sum = new long[2+n];
for(int i = 1; i<= n; i++){
int x = ni();
int pos = i;
for(int j = 1; pos>0 && j*j<= x; j++,pos--)ans[pos] += x/j;
if(pos==0)continue;
int prev = x/(i-pos);
for(;x/(i-pos+1)==prev;pos--)
ans[pos]+=x/(i-pos+1);
if(pos>0)for(int val = x/(i-pos+1);val>=1 && pos>0;val--){
int cnt = x/val-x/(val+1);
sum[Math.max(1,pos-cnt+1)]+=val;
sum[pos+1]-=val;
pos-=cnt;
}
}
int aa = n+1;
long suma = 0;
for(int i = 1; i<= n && aa==n+1; i++){
suma += sum[i];
if(ans[i]+suma<=k)aa=i;
}
pn(aa);
}
//SOLUTION END
void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
long mod = (long)1e9+7, IINF = (long)1e18;
final int INF = (int)1e9, MX = (int)2e3+1;
DecimalFormat df = new DecimalFormat("0.00000000000");
double PI = 3.1415926535897932384626433832792884197169399375105820974944, eps = 1e-8;
static boolean multipleTC = true, memory = false;
FastReader in;PrintWriter out;
void run() throws Exception{
in = new FastReader();
out = new PrintWriter(System.out);
int T = (multipleTC)?ni():1;
//Solution Credits: Taranpreet Singh
pre();for(int t = 1; t<= T; t++)solve(t);
out.flush();
out.close();
}
public static void main(String[] args) throws Exception{
if(memory)new Thread(null, new Runnable() {public void run(){try{new Main().run();}catch(Exception e){e.printStackTrace();}}}, "1", 1 << 28).start();
else new Main().run();
}
long gcd(long a, long b){return (b==0)?a:gcd(b,a%b);}
int gcd(int a, int b){return (b==0)?a:gcd(b,a%b);}
int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
void p(Object o){out.print(o);}
void pn(Object o){out.println(o);}
void pni(Object o){out.println(o);out.flush();}
String n()throws Exception{return in.next();}
String nln()throws Exception{return in.nextLine();}
int ni()throws Exception{return Integer.parseInt(in.next());}
long nl()throws Exception{return Long.parseLong(in.next());}
double nd()throws Exception{return Double.parseDouble(in.next());}
class FastReader{
BufferedReader br;
StringTokenizer st;
public FastReader(){
br = new BufferedReader(new InputStreamReader(System.in));
}
public FastReader(String s) throws Exception{
br = new BufferedReader(new FileReader(s));
}
String next() throws Exception{
while (st == null || !st.hasMoreElements()){
try{
st = new StringTokenizer(br.readLine());
}catch (IOException e){
throw new Exception(e.toString());
}
}
return st.nextToken();
}
String nextLine() throws Exception{
String str = "";
try{
str = br.readLine();
}catch (IOException e){
throw new Exception(e.toString());
}
return str;
}
}
}
Feel free to Share your approach, If it differs. Suggestions are always welcomed. 
