SUBPRNJL - EDITORIAL

binary-search
easy
march19
partial-sums
segment-tree
subprnjl
taran_1407

#1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2

Setter: Pranjal Rai
Tester: Encho Mishinev
Editorialist: Taranpreet Singh

DIFFICULTY:

Easy

PREREQUISITES:

Partial Sum Arrays, Binary Search or Segment Tree (or sliding window with heaps).

PROBLEM:

Given an array A of length N and an integer K, find the number of beautiful subarrays where a subarray S_{l,r} = A_l,A_{l+1} \ldots A_{r-1},A_r is beautiful if following holds.

  • Define array B as S_{l,r} concatenated concatenated with itself m times, where m is the smallest integer such that m*(r-l+1) \geq K and sort B.
  • Let X = B_K, the Kth smallest element in B. Let F be frequency of X in S_{l,r}.
  • A subarray is beautiful if F is present in S_{l,r}.

QUICK EXPLANATION

  • We need to check each subarray separately. For each subarray, we can see that m = \lceil K/(r-l+1) \rceil.
  • Now, When we append S_{l,r} m times and sort it, the array looks like, a m occurrence of the smallest element in S_{l,r}, m occurrences of the second smallest element in S_{l,r} and so on. So, we know, that element at a k position in B is actually the element at \lceil k/m \rceil position when S_{l,r} is sorted.
  • Finding xth element in S_{l,r} can be done using binary search over prefix arrays or using segment trees.
  • Checking frequency of X is doable with partial sums. Then we can check if F is present in the array or not again using partial sums or segment tree.

EXPLANATION

So many prerequisites for the first problem? The editorialist must be having fun with us Yes, He’s having fun :D.

Testers solution is using Segment trees while editorialist solution uses prefix arrays and binary search which you may refer below.

Testers solution

We check for each subarray whether it is beautiful or not and increment answer if subarray is beautiful.

We need to find B_k where B is the array obtained by appending S_{l,r} to B till |B| < K and sorting array B. We can observe, since we append the same array m times, there shall be m occurrences of an element on B for every occurance of any element in S_{l,r}. Also, We know, that the smallest m such that m*(r-l+1) \geq K is m = \lceil K/(r-l+1) \rceil. So, when we sort B, First m elements of B are same as smallest element of S_{l,r}, next m elements are second smallest element of S_{l,r} and so on. We need to find xth smallest value in S_{l,r} such that (x-1)*m < K and x*m \geq K.

Suppose we make a segment tree ith element denoting the frequency of i in S_{l,r} where we can update the frequency of any element and query the number of elements having value in the range (l,r). If we want to find the xth element in range (l,r) represented by a node, we can move down the node by checking if left child node has, say z elements in its range, If z >= x, we know that our required element lies in range represented by left child. Otherwise, we move to the right child and try to find the (x-z)th element in the range given by the right child. More about such a segment tree in the box.

Click to view

Each leaf node representing range [x,x] store the frequency of x in the array. The non-leaf nodes representing range [l,r] contains the number of values which lie between [l,r]. While querying for the xth smallest element at a node representing range [l,r], if the left child has at least x values, we know xth smallest lie in left sub-range. But if the left child has less than x values, say z values, we know that after counting z smaller elements, the xth element in the range [l,r] is same as (x-z) element in the range given by the right child.

Moving forward, we have found X = B_K, now we check the freqency of X, say F in S_{l,r} using segment tree. Now, We check the frequency of F in subarray again with the same frequency segment tree and if F has a frequency at least one, we increase the number of beautiful subarrays.

Click to view

About Making such frequency segment tree, We fix a starting point say l, and consider subarrays S_{l,l} first, then S_{l,l+1} and so on. We can see that we just need to increase the frequency of A_r in frequency tree having all elements of subarray S_{l,r-1}. Hence, we can fix every possible start point and thus solving the problem.

Editorialist solution

Editorialist proceeds the same way as the tester, except for the part of finding out B_K. We make prefix arrays PRE[x][r] denoting the number of values in range [1,r] which have value \leq x.

Now, We can binary search on the number of elements smaller than the current element to find out the xth element such that (x-1)*m < K and x*m \geq K. For each iteration, we can compute in O(1) time the number of elements in the range [l,r] smaller or equal to the current mid element, hence finding the B_K in O(log(MAX)) time.

Now, checking the frequency of an element x in range can also be done from same prefix arrays.

Click to view

Frequency of x in range [l,r] is (PRE[x][r]-PRE[x][l]) - (PRE[x-1][r]-PRE[x-1][l]).

Another solution

Another possible solution is to iterate over the length of subarrays. For a given length, m does not change, and thus, P =\lceil K/m \rceil remain same. We can maintain two heaps, first being a max heap holding smallest p elements and other heap holding remaining elements. Whenever we move to the next starting position, we remove one element (at the previous starting point) and add another element (the rightmost element which got included), updating the heaps accordingly and finding the B_K easily. Remaining is left as an exercise.

People say I write long and scary editorials. I believe they are worth it! What do you say?

Time Complexity

Time complexity is O(N^2*log(N)) per test case. (Can you find a faster solution?)

AUTHOR’S AND TESTER’S SOLUTIONS:

Setter’s solution

Click to view

Tester’s solution

Click to view
#include 
#include 
#include 
using namespace std;

int n,k;
int a[2011];

int IT[5011];
int LEAFOFFSET = 2047;

void addValue(int val)
{
    int ind = val + LEAFOFFSET;

    IT[ind]++;

    ind /= 2;
    while(ind > 0)
    {
        IT[ind] = IT[2*ind] + IT[2*ind + 1];
        ind /= 2;
    }
}

int kthFreq(int ver,int pos)
{
    if (ver >= LEAFOFFSET)
        return IT[ver];

    if (IT[2*ver+1] == 0 || IT[2*ver] >= pos)
        return kthFreq(2*ver, pos);
    else
        return kthFreq(2*ver+1, pos - IT[2*ver]);
}

int intCeil(int a, int b)
{
    if (a % b == 0)
        return a/b;
    else
        return a/b + 1;
}

bool query(int ln)
{
    int replicas = intCeil(k,ln);
    int pos = intCeil(k,replicas);

    int freq = kthFreq(1,pos);

    return IT[freq+LEAFOFFSET] > 0;
}

int main()
{
    int i,j;
    int ans = 0;
    int t,test;

    scanf("%d",&t);

    for (test=1;test<=t;test++)
    {
        ans = 0;

        scanf("%d %d",&n,&k);

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

        for (i=1;i<=n;i++)
        {
            memset(IT,0,sizeof(IT));

            for (j=i;j<=n;j++)
            {
                addValue(a[j]);

                if (query(j - i + 1))
                    ans++;
            }
        }

        printf("%d
",ans);
    }

    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 solve(int TC) throws Exception{
        int n = ni();long k = nl();
        int[] a = new int[1+n];
        for(int i = 1; i<= n; i++)a* = ni();
        int[][] p = new int[MX][1+n], fre = new int[MX][1+n];
        for(int i = 1; i< MX; i++)for(int j = 1; j<= n; j++){
            p*[j] = p*[j-1]+(a[j]<=i?1:0);
            fre*[j] = fre*[j-1]+(a[j]==i?1:0);
        }
        int ans = 0;
        for(int l = 1; l<= n; l++){
            for(int r = l; r<= n; r++){
                long len = r-l+1;
                long fi = (k+len-1)/len;
                long K = (k+fi-1)/fi;
                int lo = 1, hi = 2000;
                while(lo+1= K)hi = mid;
                    else lo = mid+1;
                }
                if(p[lo][r]-p[lo][l-1]>=K)hi = lo;
                int f = fre[hi][r]-fre[hi][l-1];
                if(fre[f][r]-fre[f][l-1]>0)ans++;
            }
        }
        pn(ans);
    }
    //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:


#2

PBDS came quite handy for this problem. Solution


#3

nice editorial!


#4

I was really amazed to see this question and the optimizations that were to be done to get an AC.
The hints of constraints were really tricky and PBDS could be the only method to solve them.
However, out of nowhere, I was checking some codes of Subprnjl after Contest ended and came to see this.

  1. https://www.codechef.com/viewsolution/23483846
  2. https://www.codechef.com/viewsolution/23491310

    These two solutions are same, LOL!

#5

@admin Can you explain please how this problem categorized as Easy problem?


#6

The editorial is pretty fine. There can be one more solution which is more or less similar to the editorialist’s solution that applies binary search over segment tree/bit and this was the intended solution when I created the problem. Later seeing so many other solutions was also amazing. The complexity for this approach will be O(n*logn)^2 which will pass in given time limit.


#7

What is PBDS and can you please share a good link to read and study them?


#8

Just to share another approach.I solved it without using tree, through count sort.As sorting of subarrays ws required afew times as count was maintained.
Here is my solution.


#9

Hey guys, found this solution from @shubhammitt in java. Seems like the fastest one. : )
Solution

Also my solution without using segment tree. My Solution


#10

I tried implementing a Merge Sort Tree in JAVA to solve this, but the time complexity of that was O((nlogn)^2). PBDS was super easier in C++. Thanks to author for this problem. Learnt quite a lot (and shifted to C++).


#11

Two submissions of mine, one with prefix sum ( same as in the editorial ) took 0.47 sec and another one with treap took 1.49 sec, LOL!

Solution 1 : https://www.codechef.com/viewsolution/23362784

Solution 2 : https://www.codechef.com/viewsolution/23582294


#12

I used Wavelet Tree for solving the problem.Great to see such different approaches being used for solving the question.

Here’s the link to my solution : https://www.codechef.com/viewsolution/23403845

Kudos to Problem Setter :slight_smile:


#13

I’m amazed by all the different approaches out here, I believe this will help me learn a lot once I implement them myself. As for my solution, I maintained a count array for each subarray I generated, and then traversed the count array. I subtracted count for every element until the value reaches zero or below.
I believe this is an O(N^3) solution in the worst case, but with a couple of observations, it passed within 0.4 seconds.

Observations:

  • If all the elements in the subarray are distinct, no matter what the kth element is, it’s count will always be 1, so we just have to check for the count of 1.
  • If k \geq s^2 , then the kth element will always be the last element in the subarray, so all we need to maintain is the largest element found so far.
    s is the size of the subarray, i.e s = (r-l+1)

I hope the code will be self explanatory. :slight_smile:

Link


#14

Did anyone get complete AC using balanced trees?


#15

this question can be solve using Binary Index Tree.
As there were required to find Kth smallest element in unsorted array, so by using of Binary Index Tree we can do it.

SUBPRNJL


#16

O(N^2) per test case solution with frequency array in 0.04 sec.
https://www.codechef.com/viewsolution/23583890


#17

What is wrong in my solution? Please help…
https://www.codechef.com/viewsolution/23421387


#18

I think the test cases were weak. O(N^3) solutions also got accepted. Check this one.
Link


#19

nice editorial!


#20

Worth mentioning that the BS solution can be sped up substantially by initializing M to the previously found B_x. Amazingly, I still could not get this to pass TL in python :frowning: