Subprnjl - editorial

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[i]);
        }

        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\n",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[i] = 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[i][j] = p[i][j-1]+(a[j]<=i?1:0);
            fre[i][j] = fre[i][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:

4 Likes

PBDS came quite handy for this problem. Solution

2 Likes

nice editorial!

PBDS and fenwick tree also works

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!

2 Likes

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

4 Likes

can’t believe 4 star user caught in plagiarism

as it was an easy problem… its neither cake walk nor medium according to codechef standards or admin’s/editorialist’s standards…

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.

1 Like

exactly… I did binary search over BIT… :smiley:

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

Both your solutions are really nice, @taran_1407. I could only think of a solution using a Fenwick tree.

1 Like


https://goo.gl/WVDL6g

it’s a kind of balanced binary search tree afaik…
you can consider it as a black box which does these operations in O(logn)

1 Like

seriously!

Then that standard needs to be rectified.

No need according to my opinion…
This was little above easy…

As per the editorial this problem is solved using segment tree or prefix array with binary search. Do you still think it should be categorized as easy problem?

Given the constraints, \mathcal{O}(n^2\log^2n) shouldn’t pass. Though, with a Fenwick tree, it can be done in \mathcal{O}(n^2\log n) too.

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

And @taran_1407 seems to be missing someone who used to encourage him on his editorials almost every time :frowning: