WEIRD2 - EDITORIAL

amortization
data-structure
easy
ltime65
order-statistic
taran_1407
weird2

#1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2

Setter: Hasan Jaddouh
Tester: Teja Vardhan Reddy
Editorialist: Taranpreet Singh

DIFFICULTY:

Easy-Medium

PREREQUISITES:

Observation, Amortized analysis and data structures.

PROBLEM:

Given an array A of length N, find out the number of ordered pairs (a,b) such that a appears at least b times in array while b appears at least a times in the array.

QUICK EXPLANATION

  • Sort the given array, and for every position, iterate over the positions having less than the frequency of current element.
  • Above solution works in overall O(N) time because, at every iteration, we iterate over at most F* elements in each iteration where F* is the frequency of A*. Since \sum F* = N, Overall complexity is O(N).

EXPLANATION

For this problem, I have two solutions to offer, First the intended solution, which is used by Setter and Tester, while the other one is my solution.

Let us make input in form of frequency mapping tuples (A*,F*), where F* denote frequency of A* in input array.

Bruteforce Solution: Iterate over every ordered pair (i,j), i \leq j of values and check if F[j] \geq A* and F* \geq A[j] holds.

Since we iterate over all pairs of values, this solution has complexity O(N^2).

Now, let us rewrite the conditions of a valid pair. For pair (A*, A[j]) to be valid, we need F[j] \geq A* and F* \geq A[j].

Let us sort these tuples in increasing order of A* and run the same loops as BruteForce. Now, notice, that for any (A*, F*), if we get the position A[j] > F* for any position j, we can safely see, that No position k, k > j will satisfy F* \geq A[k]. Hence, we can break out from internal loop as soon as we reach a value A[j] > F*.

Now, What is the time complexity of this solution? This is where Amortized Analysis comes into play.

See, For every position, we iterate over at max F* element in inner loop. Since N = \sum F*, The overall solution complexity is bounded by N, resulting in overall O(N*logN) solution due to sorting.

Now, Let’s discuss Editorialist solution in brief, who didn’t get the observation at first.

Make frequency tuples same way as above solution and sort tuples by non-decreasing order of F*. If we focus on condition A* \leq F[j], we know that this condition will hold for a suffix of the array due to the non-decreasing order of F. This way, Now we need to count the number of positions in Suffix [j, N-1] for which A[j] \leq F*. Let’s call (j, F*) a query, and j is the left end of query range, right end being the end of the array.

There exist a more general problem which can be applied here. Given an array of length N, Perform two type of operations. First is to update a single element. Other is to count number of elements \leq x in range [l, r].

Editorialist just uses Order statistic tree, along with sorting queries (j, F*) by decreasing order of j, and answer queries and add elements to order statistic tree as the j decreases, and making queries when the current range of added elements correspond to query range.

The time complexity of this solution too is O(N*logN) but is probably slower than the first solution due to the constant factor.

This was a lesson, that observations matter. :stuck_out_tongue:

Related problem

The problem Tufurama seems a lot similar to this problem, though have quite a different solution which is worth a try.

Also, The problems KQUERY and KQUERY2 are nice problems to practice if you tried the second solution.

Time Complexity

The time complexity of both solutions is O(N*logN) but the first one has lower constant factor than the second 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. :slight_smile:


#2

Yeah, I tried using the tufurama approach, but the complexity was too much. Is there a different way of applying mergesort tree to solve this problem?


#3

OMG I also used the setters approach without knowing! Its a lot of fun when you realize you did it in setters method :). Thank you for editorial taran!


#4

this is my code that pass all test cases.however when i use unordered_map it gives wrong answer.suggest some
test case where it fails.

link to my solution:
https://www.codechef.com/viewsolution/21247254


#5

“”"
Now we need to count the number of positions in Suffix [j,N−1] for which A[j]≤F*
“”"

Cannot this be done in a simple way like this instead of using order Statistic Tree?

Just maintain a set (cpp STL) of all elements from j to N-1 .for knowing the number of positions or which A[j]≤F* just use upperbound on that set.

when we want for i-1 just add ith element to that set and use upperbound again.
This takes logn time for each i .


#6

I think there are weak test cases because n^2 approach is working for 100 points . just make array of all different numbers then use two loops for checking all i and j .
here is my solution . .
https://www.codechef.com/viewsolution/21256684


#7

@motif
Lazy tester that what I can say.
If I were in place of tester, this counter tc would have been the first tc which I would have included. :frowning:
From past seven rated contest I’m seeing complains about weak tc :frowning:

P.S. - Posting as the separate answer instead of the comment. Hoping @admin will see this.


#8

Yep you are right , this should be the first counter test case because if this problem can be solved in n^2,then the problem is a cakewalk and the whole story of this editorial ( that sort the array , f* , O(n) , observation etc…) makes no sense ,I hope that next time @admin will take care of this.


#9

I prefer short python solutions. XD


#10

Well, we need to answer queries of type KQUERY, whichever method you may apply.


#11

HERE is my solution.
which is O(n+10^6)
Seems to be same as setter… but this is not O(n*log(n))
Still confused about time complexity… can anyone help ?


#12

reader functions and huge templates and assert statements annoys a lot in checking solutions :frowning:


#13

I agree. So many random defines hinder readibility >_<


#14

@l_returns hacked your soln. Check Hacked Soln.

TC is hard coded instead of reading. Takes 1.5 sec and TL is 1 sec.


#15

Your complexity is omega(T*1e6) but inner loop is not executed many times so it passed.


#16

Such a difference doesnt really matter @aryanc403 …XD


#17

I failed to understand setter soln. So link of your well-commented soln, please. xD


#18

Her (or his…?) profile doesnt show any submission XD


#19

This reminds me of that moment … :stuck_out_tongue:


#20

In the ordered map, all tuples are ordered by key, while in unordered, they can appear in any order, making your solution incorrect, when an unordered map is used.