PROBLEM LINK:Practice Setter: Pranjal Rai 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_{r1},A_r$ is beautiful if following holds.
QUICK EXPLANATION
EXPLANATIONSo 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*(rl+1) \geq K$ is $m = \lceil K/(rl+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 $(x1)*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 (xz)th element in the range given by the right child. More about such a segment tree in the box. 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. 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 $(x1)*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. 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 ComplexityTime 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 Tester's solution Editorialist's solution Feel free to Share your approach, If it differs. Suggestions are always welcomed. :)
This question is marked "community wiki".
asked 13 Mar, 18:36

@admin Can you explain please how this problem categorized as Easy problem? answered 13 Mar, 23:32
as it was an easy problem... its neither cake walk nor medium according to codechef standards or admin's/editorialist's standards...
(13 Mar, 23:34)
Then that standard needs to be rectified.
(13 Mar, 23:46)
No need according to my opinion...
(13 Mar, 23:48)
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?
(13 Mar, 23:54)
I agree, this is definitely not an easy problem.
(14 Mar, 01:18)
2
The reason why this is classified as easy is because its classical. We can reduce the problem to "Finding $k'th$ largest element in an unsorted array, which is one of the classical (and well known/basic) problem of order statistical tree. If you know the data structure, then its just
(14 Mar, 01:21)
That's kind of excuse. Sorry. Ordered statistics tree is not something beginner wants to know at first. I hope easy problems are actually easy to solve for beginners. Otherwise it seems that the platform discriminates the participants since this problem looks easier for experienced participants.
(14 Mar, 22:01)
Dont be, lul. Neither I owe you any explanation nor do you. Its anyways my own opinion and not the setter/admins.
Thats a very subjective thing. I can argue the same for other data structures like heap, segment tree, set etc. and say they should not be given as "Beginners will want a easy problem which they can solve."
Which is alright lol. Lastly, if everyone solves easy problem means they are learning nothing. Personally against that.
(15 Mar, 17:51)
Hmm that all mean we shouldn't have any category in Practice section like Easy, Medium, etc! Something related to segment tree or BIT shouldn't be in easy in that case.
(15 Mar, 19:30)
Hello @prmondal the test cases were weak and you can even solve this question with any tree and hence it's an easy question... Okay fine ?
(16 Mar, 08:09)
Here is an sample soln https://www.codechef.com/viewsolution/23473452
(16 Mar, 08:09)
And btw I hope u know that all problems gets 100 points regardless of difficulty and it's only setter who gets different amount of payment on basis of difficulty.. I don't see any point that u should have any problem... And the O(n^3) soln passes which shows it's an easy problem
(16 Mar, 08:11)
It can be solved by simple sum query Segment tree also and if you don't even know segment tree then I don't think you are a competitive programmer yet... It's very popular tree... You should learn it by now then... And even if u don't know it... It's still solvable without it..
(16 Mar, 08:14)
Chef and soccer has 1/8 times submission than this problem and it was categorised as easy medium... So what difficulty do you expect for this one ? Same ? Or medium ?
(16 Mar, 08:27)
Well I know about segment tree. But for this problem I solved using BIT but after the contest though. https://www.codechef.com/viewsolution/23587323 One thing I can agree since the constraint is weak it can be solved without any tree. But editorial does not say about it clearly.
(16 Mar, 16:32)
Okay :) @prmondal
(18 Mar, 07:37)
showing 5 of 16
show all

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. answered 13 Mar, 23:30
can't believe 4 star user caught in plagiarism
(13 Mar, 23:32)
seriously!
(13 Mar, 23:45)
No shit! Guy has been caught cheating twice in past contests.. See the history!
(14 Mar, 12:48)

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. answered 13 Mar, 23:35
exactly.. I did binary search over BIT... :D
(13 Mar, 23:36)
1
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.
(14 Mar, 00:10)
Why not? $n$ is only 2000 and you are given 2 seconds. https://www.codechef.com/viewsolution/23329611
(14 Mar, 01:29)
For $n = 2000$, $n^2\log^2n$ is approximately $4.8 \times 10^8$. Also there are five test cases, which makes it $2.4 \times 10^9$. But I guess the actual number of operations done is much less than this value, which is why $\mathcal {O}(n^2\log^2n)$ passes.
(14 Mar, 02:55)
1
I see people discussing about $O(T*n^2*log^2(n))$
(14 Mar, 08:00)
I tried using a Merge Sort Tree (Java) with time complexity $O(nlogn)^2$, though it timed out. I used fast io and precomputation for getting count in O(1). PBDS in C++ ofc provides O(logn) operations which gave final TC of $O(n^2logn)$
(14 Mar, 08:14)
That is so lol. CHONQ had very tight constraints and O(T∗n3) passes for this problem.
(14 Mar, 09:56)
yes @udayan14 XD
(14 Mar, 15:21)
1
<3 for $O(T*n^3)$
(15 Mar, 07:34)
showing 5 of 9
show all

Hey guys, found this solution from @shubhammitt in java. Seems like the fastest one. : ) Solution Also my solution without using segment tree. My Solution answered 14 Mar, 02:00

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 :) answered 14 Mar, 11:36

Solution of Another Solution mentioned in Editorial. Just Instead of Two heaps I maintained one Max Heap and one Array. I got AC in 0.58 seconds. answered 15 Mar, 16:19

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. answered 14 Mar, 01:51

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++). answered 14 Mar, 08:09

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! answered 14 Mar, 11:05

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:
I hope the code will be self explanatory. :) answered 14 Mar, 13:08

Did anyone get complete AC using balanced trees? answered 14 Mar, 13:21
Yup I got. I used treap. https://discuss.codechef.com/questions/146555/subprnjleditorial/146653
(14 Mar, 20:36)

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. SUBPRNJLanswered 14 Mar, 15:45

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

What is wrong in my solution? Please help.... https://www.codechef.com/viewsolution/23421387 answered 14 Mar, 20:12

nice editorial! answered 14 Mar, 21:23
https://discuss.codechef.com/questions/97820/iwanttoaskaquestionaskthemallhere
(14 Mar, 21:56)
Look what I found while checking some solutions.
(15 Mar, 11:32)

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 :( answered 15 Mar, 00:14

@admin: How a solution gets complete AC when it takes 3.74 sec for some test cases and written in Java? What is the time limit for this problem for JAVA? answered 15 Mar, 00:18
java and python are slow languages that's why codechef and all OJs provide time multipliers for them. for java its x2, and for python its x5
(15 Mar, 11:54)
I know they are slower but its not mentioned anywhere in the problem. Isn't it?
(15 Mar, 14:40)

I passed the testcases using a persistent segment tree to know the value of the kth element in a range [l,r]. Each query takes log2(N), so passes all the testcases in N * N * log2(N). Nice question if you want to learn different methods to find the kth element in range [l,r] in different complexities. I referred Merge Sort Tree, Order Statistics Tree, and an old Codeforces blog. Beautiful problem :D answered 16 Mar, 01:07

I used the Persistence segment tree for finding kth smallest element. Is this is what the editorial is talking about? answered 16 Mar, 02:00

I am getting tle for my solution. https://www.codechef.com/viewsolution/23590284 answered 16 Mar, 17:32

what is the use of TREEOFFSET there in the tester solution? will anyone, please explain to me. thanks in advance answered 17 Mar, 20:03

someone, please give the links of the resources of
1. finding kth smallest element in an array for a range answered 18 Mar, 01:25

I applied the last approach of Heap using priority queue. Can anyone tell me where I was going wrong? https://www.codechef.com/viewsolution/23482405 answered 18 Mar, 03:04

I maintained an array throughout the problem and used insertion sort and tweaked a bit of binary search to find the position to insert an element. once array is sorted, everything will be easy.
Got an AC ;) hahah answered 18 Mar, 22:24

Why am I unable to add a comment to other users' answers? answered 18 Mar, 22:57

It will be really helpful if anybody could assist me where I am going wrong? I have used pbrs approach. link to solution:https://www.codechef.com/viewsolution/23641513 answered 5 hours ago

PBDS and fenwick tree also works
Both your solutions are really nice, @taran_1407. I could only think of a solution using a Fenwick tree.
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 :(