CHONQ - EDITORIAL

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*}) 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*}) 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*}) 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* = sum[i-1]+diff*, 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*)}) 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* = 0LL;
            paint* = 0LL;
        }

        for (i=1;i<=n;i++)
        {
            scanf("%d",&a*);

            ///One-time values
            int lastval;

            for (j=1;j*j<=a*;j++)
            {
                int val = a* / j;

                if (i - j + 1 >= 1)
                    ans[i - j + 1] += (llong)val;

                lastval = val;
            }

            //Use-up last value
            while(j <= a* && a* / j == lastval)
            {
                if (i - j + 1 >= 1)
                    ans[i - j + 1] += (llong)(a* / j);

                j++;
            }

            if (j > a*)
                continue;

            int v = a* / j;

            for (j=v;j>=1;j--)
            {
                int L, R;

                L = a* / (j + 1) + 1;
                R = a* / j;

                if (L <= R)
                {
                    paintRange(i - R + 1, i - L + 1, j);
                }
            }
        }

        llong pt = 0;
        for (i=1;i<=n;i++)
        {
            pt += paint*;

            ans* += pt;
        }

        for (i=1;i<=n;i++)
        {
            if (ans* <= k)
                break;
        }

        printf("%d
",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*;
            if(ans*+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. :slight_smile:

6 Likes

When will the editorial of PTREE be out ?

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.

My solution uses only 2 divisions and still gets TLE.

Link - https://www.codechef.com/viewsolution/23487508

Any tips/tricks/tutorials for optimizing this further :p. I am pretty sure I cannot reduce more divisions.

Kudos to problem setter and also to editorialist for such a nice editorial.

Although the problem uses basic concept but I didn’t get it during contest time :stuck_out_tongue:

Thanks again!

“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.”

I kind of bypassed that by calculating the wrath levels naively, but only those that are actually required. And it passed. So I think the test cases didn’t have anything like
5
1 100000
1 2 … 10^5
1 100000
1 2 … 10^5
1 100000
1 2 … 10^5
1 100000
1 2 … 10^5
1 100000
1 2 … 10^5

  1. Open Editorial
  2. Look at expected time complexity.
  3. Hit DownVote.
  4. Close Tab.

The reason behind such tight TL is that to prevent non-intended solutions to pass. replace it with “The reason behind such tight TL is that to prevent intended solutions to pass.”

2 Likes

It would be helpful if you can tell the time complexity of my solution.

https://www.codechef.com/viewsolution/23384243

Optimizations at it’s peak.
This Long Challenge was a complete lesson of Time Complexities. :smiley:

1 Like

This Problem taught me that division is a costly opertaion

Can this be done in O(N log(N))?

We use the fact that circulant matrix multiplication with a vector is fast if we use FFT. I could do it if instead of the floor function, there was normal division(floating points). Any known fix for this? This constraints at first glance seemed to be asking to implement this O(N log(N)) solution

2 Likes

have a look at my solution: it taking 1.5*10^8 loops in the worst case, with three divisions

https://pastebin.com/qZkGRXrk

Last two TC for my solution is something… My solution

Mine runs in 1.58 seconds out of 4 seconds in java.

Cool. How do I optimize my code though? You can have all the bragging rights, just help this noob in learning some basic optimizations :stuck_out_tongue:

2 Likes

https://codeforces.com/problemset/problem/616/E this problem is based on same idea

1 Like

XD… (dots due to char limits)

1 Like

you should create a blog on “vijju’s optimization techniques” …
U convert int to long long int and switch to java from c++ for removing TLE XDD

1 Like

If i am not wrong you are doing the same thing as this solution

https://www.codechef.com/viewsolution/23480958

I could not get it passed. It too has only 2 divisons, but the inner loops runs 2*root(N) time instead of root(N), same as yours I believe

@vijju Just preprocess that sqrt(value) loop for each value and it will pass…
HERE is my soln… passes in 1.07 secs

same optimization advice to both of you