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. 
