You are not logged in. Please login at www.codechef.com to post your questions!

×

SUBPRNJL - EDITORIAL

4
2

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.

View Content

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.

View Content

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.

View Content

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

View Content

Tester's solution

View Content

Editorialist's solution

View Content

Feel free to Share your approach, If it differs. Suggestions are always welcomed. :)

This question is marked "community wiki".

asked 13 Mar, 18:36

taran_1407's gravatar image

6★taran_1407
4.0k31104
accept rate: 22%

edited 13 Mar, 20:33

vijju123's gravatar image

5★vijju123 ♦♦
15.5k12066

PBDS and fenwick tree also works

(13 Mar, 22:29) l_returns5★
1

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

(13 Mar, 23:40) the_extractor4★

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 :(

(14 Mar, 00:11) vijju123 ♦♦5★

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

link

answered 13 Mar, 23:32

prmondal's gravatar image

3★prmondal
512
accept rate: 0%

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) l_returns5★

Then that standard needs to be rectified.

(13 Mar, 23:46) prmondal3★

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

(13 Mar, 23:48) l_returns5★

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) prmondal3★

I agree, this is definitely not an easy problem.

(14 Mar, 01:18) kmampent4★
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 tree.insert(k); tree.find_k'th_largest(); . If you dont know the data structure...life becomes messier :3

(14 Mar, 01:21) vijju123 ♦♦5★

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) prmondal3★

That's kind of excuse. Sorry.

Dont be, lul. Neither I owe you any explanation nor do you. Its anyways my own opinion and not the setter/admins.

Ordered statistics tree is not something beginner wants to know at first.

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."

looks easier for experienced participants.

Which is alright lol.

Lastly, if everyone solves easy problem means they are learning nothing. Personally against that.

(15 Mar, 17:51) vijju123 ♦♦5★

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) prmondal3★

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) l_returns5★
(16 Mar, 08:09) l_returns5★

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) l_returns5★

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) l_returns5★

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) l_returns5★

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) prmondal3★

Okay :) @prmondal
That's great...

(18 Mar, 07:37) l_returns5★
showing 5 of 16 show all

PBDS came quite handy for this problem. Solution

link

answered 13 Mar, 20:20

nilesh8757's gravatar image

4★nilesh8757
413
accept rate: 0%

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!

link

answered 13 Mar, 23:30

on_top's gravatar image

0★on_top
211
accept rate: 0%

can't believe 4 star user caught in plagiarism

(13 Mar, 23:32) l_returns5★

seriously!

(13 Mar, 23:45) on_top0★

No shit! Guy has been caught cheating twice in past contests.. See the history!

(14 Mar, 12:48) kukreja_vlk3★

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.

link

answered 13 Mar, 23:35

prnjl_rai's gravatar image

5★prnjl_rai
746
accept rate: 0%

exactly.. I did binary search over BIT... :D

(13 Mar, 23:36) l_returns5★
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) the_extractor4★

Why not? $n$ is only 2000 and you are given 2 seconds. https://www.codechef.com/viewsolution/23329611

(14 Mar, 01:29) kmampent4★

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) the_extractor4★
1

I see people discussing about $O(T*n^2*log^2(n))$
How about $O(T*n^3)$ ??
Have a look...
https://www.codechef.com/viewsolution/23473452

(14 Mar, 08:00) l_returns5★

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) kukreja_vlk3★

That is so lol. CHONQ had very tight constraints and O(T∗n3) passes for this problem.

(14 Mar, 09:56) udayan143★

yes @udayan14 XD

(14 Mar, 15:21) l_returns5★
1

<3 for $O(T*n^3)$

(15 Mar, 07:34) aryanc4035★
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

link

answered 14 Mar, 02:00

akkivarma's gravatar image

4★akkivarma
112
accept rate: 0%

edited 14 Mar, 02:10

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 :)

link

answered 14 Mar, 11:36

brain_axe's gravatar image

3★brain_axe
111
accept rate: 0%

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.

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

link

answered 15 Mar, 16:19

tagrawal's gravatar image

5★tagrawal
111
accept rate: 0%

nice editorial!

link

answered 13 Mar, 20:26

elgawtihcra's gravatar image

4★elgawtihcra
11
accept rate: 0%

Thanks a lot!

(15 Mar, 06:36) taran_14076★

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

link

answered 13 Mar, 23:40

dilbwag1's gravatar image

3★dilbwag1
1
accept rate: 0%

1

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)

(13 Mar, 23:43) l_returns5★

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.

link

answered 14 Mar, 01:51

manthan133's gravatar image

4★manthan133
1
accept rate: 0%

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++).

link

answered 14 Mar, 08:09

kukreja_vlk's gravatar image

3★kukreja_vlk
604
accept rate: 22%

NVM i think TreeSet in java also does smth similar

(14 Mar, 08:44) kukreja_vlk3★

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

link

answered 14 Mar, 11:05

malviyanshiv's gravatar image

4★malviyanshiv
1205
accept rate: 14%

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. :)

Link

link

answered 14 Mar, 13:08

epsilonalpha's gravatar image

4★epsilonalpha
10516
accept rate: 25%

edited 14 Mar, 13:25

Did anyone get complete AC using balanced trees?

link

answered 14 Mar, 13:21

thesmartguy's gravatar image

4★thesmartguy
786
accept rate: 7%

edited 14 Mar, 13:21

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

link

answered 14 Mar, 15:45

darshangohel's gravatar image

4★darshangohel
1
accept rate: 0%

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

link

answered 14 Mar, 16:35

kartik_tiwari's gravatar image

4★kartik_tiwari
1
accept rate: 0%

Can you explain it please?

(15 Mar, 00:35) the_extractor4★

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

link

answered 14 Mar, 20:12

tonystark007's gravatar image

3★tonystark007
11
accept rate: 0%

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

link

answered 14 Mar, 20:41

jha_gaurav98's gravatar image

5★jha_gaurav98
1
accept rate: 0%

nice editorial!

link

answered 14 Mar, 21:23

marky_joey's gravatar image

2★marky_joey
11
accept rate: 0%

edited 15 Mar, 07:37

aryanc403's gravatar image

5★aryanc403
2.7k1618

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 :(

link

answered 15 Mar, 00:14

schiebermc's gravatar image

4★schiebermc
161
accept rate: 25%

@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?

link

answered 15 Mar, 00:18

prmondal's gravatar image

3★prmondal
512
accept rate: 0%

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) thesmartguy4★

I know they are slower but its not mentioned anywhere in the problem. Isn't it?

(15 Mar, 14:40) prmondal3★

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

link

answered 16 Mar, 01:07

buzz_95's gravatar image

4★buzz_95
1
accept rate: 0%

I used the Persistence segment tree for finding kth smallest element. Is this is what the editorial is talking about?

link

answered 16 Mar, 02:00

mgautam98's gravatar image

4★mgautam98
0
accept rate: 0%

I am getting tle for my solution. https://www.codechef.com/viewsolution/23590284

link

answered 16 Mar, 17:32

sanketagarwal's gravatar image

3★sanketagarwal
1
accept rate: 0%

what is the use of TREEOFFSET there in the tester solution? will anyone, please explain to me. thanks in advance

link

answered 17 Mar, 20:03

andyy143's gravatar image

3★andyy143
1
accept rate: 0%

someone, please give the links of the resources of 1. finding kth smallest element in an array for a range
2. frequency find in a range

link

answered 18 Mar, 01:25

cap_coder's gravatar image

2★cap_coder
1
accept rate: 0%

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

link

answered 18 Mar, 03:04

alfran_ali's gravatar image

3★alfran_ali
11
accept rate: 0%

edited 18 Mar, 03:06

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
Have a look here solution

link

answered 18 Mar, 22:24

forevermanu's gravatar image

3★forevermanu
11
accept rate: 0%

edited 18 Mar, 22:24

Why am I unable to add a comment to other users' answers?

link

answered 18 Mar, 22:57

schiebermc's gravatar image

4★schiebermc
161
accept rate: 25%

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

link

answered 5 hours ago

bk54's gravatar image

3★bk54
93
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×3,820
×1,768
×1,056
×724
×83
×75
×19

question asked: 13 Mar, 18:36

question was seen: 5,515 times

last updated: 5 hours ago