LFIVES - Editorial

cook57
dynamic-programming
editorial
fenwick
lfives
medium

#1

PROBLEM LINK:

Practice
Contest

Author: Konstantsin Sokol
Tester: Gedi Zheng
Editorialist: Miguel Oliveira

DIFFICULTY:

Medium-hard.

PREREQUISITES:

Dynamic Programming, Binary Indexed Trees.

PROBLEM:

You are given a sequence a_1, a_2, ..., a_N of non-negative integers. Your task is to process Q queries of the following format: each query is described by two integers L ≤ R and asks to calculate the number of triples (i, j, k), such that L  <  i  <  j  <  k  <  R and a_L > a_i < a_j > a_k < a_R.

EXPLANATION:

The first thing to notice is that there are repeating patterns in the subsequences. For example,

  • Increasing subsequences like a_i < a_j and a_k < a_R
  • Decreasing subsequences like a_L > a_i and a_j > a_k
  • Triples a_L > a_i < a_j and a_j > a_k < a_R

So, suppose we process the sequence from left to right. We can break down the triplets such that a_L  >  a_i  <  a_j  >  a_k  <  a_R, with L < i < j < k < R, in parts:

  • For a fixed R, the number of subsequences a_L  >  a_i  <  a_j  >  a_k  <  a_R is the number of subsequences a_L  >  a_i  <  a_j > a_k such that a_k < a_R
  • For a fixed k, the number of subsequences a_L  >  a_i  <  a_j  >  a_k is the number of subsequences a_L  >  a_i  <  a_j such that a_j > a_k
  • For a fixed j, the number of subsequences a_L  >  a_i  <  a_j is the number of subsequences a_L > a_i such that a_i < a_j
  • The number of subsequences such that a_L > a_i is the number of integers between L and j below a_L

Hence, we can build up on the smaller parts in order to find the solution for each query.

We can use a binary indexed tree (BIT) to keep counts for each part

  • BIT_r counts how many subsequences a_L  >  a_i  <  a_j > a_k are there where a_k equals a query value.
  • BIT_k counts subsequences a_L  >  a_i  <  a_j.
  • BIT_j counts subsequences a_L  >  a_i.
  • BIT_i counts the frequency of integers seen so far.

Suppose we fix L and process the elements from left to right until N. For each x up to N,

  • Use BIT_r to count the number of subsequences a_L  >  a_i  <  a_j > a_k up to x, such that a_k < a_x. The answer to a query in interval [L, x] is this value. Save this in a table.
  • Use BIT_k to count the number of subsequences a_L  >  a_i  <  a_j, such that a_k > a_x. Update BIT_r with this number.
  • Use BIT_j to count the number of subsequences a_L  >  a_i, such that a_j < a_x. Update BIT_k with this number.
  • Use BIT_i to count the number of integers such that a_i < a_j. Update BIT_j with this number.
  • Insert a_x to BIT_i

This pre-processing takes O(N^2 log N) time because we do 4 inserts and updates in BITs for each valid interval [L, R].
After this pre-processing, we can answer any query using the computed table in O(1) time.
Thus, the total time complexity is O(N^2 \log N + Q).

Implementation notes:

  • Since the input numbers can be up to 10^9, we should pre-process them and compress the values in a range [1, N] (we don’t care about the number itself, just their relative order)
  • Instead of implementing separate Binary Indexed Trees for increasing and decreasing subsequences, we can just check for increasing subsequences. To do this, note that we can transform a decreasing subsequence into an increasing one by changing each value a{_i} to maxvalue - a_i.

AUTHOR’S AND TESTER’S SOLUTIONS:

Setter’s solution
Tester’s solution


#2

Can anyone please tell me why did I get a TLE for my O(N*Q) solution : http://www.codechef.com/viewsolution/6798568 , when there is an accepted solution of the same complexity on the first page itself : http://www.codechef.com/viewsolution/6799042


#3

Hi @Tester !

I’m a newbie to advanced data-structres and I went through BIT explanations and understood it’s working. I read your solution and there was one section I couldn’t understand. :confused:

I’ll be glad if you can explain a little bit further :slight_smile:

I understood the working of the init() function. In the array a[] you have stored (all the elements of the input array that is <= ith element of the input array)

Now, you have created 4 fenwick / BIT trees according to the above mentioned rules in the editorial.
but I don’t understand the working of the following code:

 
for (int l = 0; l < n; ++l) {
memset(tree, 0, sizeof(tree));
Insert(lim - a[l], 1, tree[0]);
for (int j = l + 1; j < n; ++j) {
ans[l][j] = Query(a[j] - 1, tree[3]);
Insert(a[j], Query(lim - a[j] - 1, tree[2]), tree[3]);
Insert(lim - a[j], Query(a[j] - 1, tree[1]), tree[2]);
Insert(a[j], Query(lim - a[j] - 1, tree[0]), tree[1]);
}
}

I’ll be glad if you can help me in this. :slight_smile:

Thanks.


#4

I tried solving in N*Q operations the queries with a processing of N^2 logN .But I continuously got WA.
Can anyone tell me the mistake??
My code : http://www.codechef.com/viewsolution/6799654


#5

@tester
I am new at advanced data structures and I am trying to understand this program. I got most of it but I have a few queries.
What does the Insert statement of the outer for loop tell? Why we take Insert(lim-a[l],1,tree[0])?


#6

just an opinion … for future questions, please don’t keep such constraints…
O(NQ) passes with fast IO … keeping Q to be 5*10^5 would have been perfect i guess.


#7

can someone please give more insight on how the 4 binary indexed trees coordinate to get the correct answer.


#8

There are a lot of optimizations in the accepted solution that you have shown.


#9

Part1/2

A BIT query(x) allows us to know how many items are there up to “x”.

Suppose we want to count increasing subsequences like “a < b”. We have b = 10, so we just need to know how many numbers are in the BIT that are less than 10, which is Query(b-1) = Query(9).

Suppose now that we want to count decreasing subsequences. “a > b”. We want how many numbers are there larger than 10. This is not so convenient using a BIT. One option would be to have the total amount of numbers and subtract the numbers up to 10, like “Total - Query(b)”.

(continue in next comment)


#10

Part2/2

A simpler option is to transform the numbers. Say the maximum number is 100. If we had [100, 2, 50, 10],
For b = 10, the numbers higher than b are 100 and 50.
Let’s transform the numbers into Max - v* + 1, getting [1, 99, 51, 91]. now the former 10 is 91 (100-10+1).
The numbers lower than 91 are the numbers that were > 10 in the original sequence, 100 is 1 and 50 is 51.

So, we can now use the same technique as for increasing subsequences.


#11

Hi,

Thanks for your explanation but I’m still having some doubts in it.
Let me ask you pointwise:-

  1. Can you please define which tree is for which relation? For ex: tree[0] = ai < aj, tree[1] for … etc

  2. It will also be very helpful if you can explain this code line by line.

Insert(lim - a[l], 1, tree[0]);
for (int j = l + 1; j < n; ++j) {
ans[l][j] = Query(a[j] - 1, tree[3]);
Insert(a[j], Query(lim - a[j] - 1, tree[2]), tree[3]);
Insert(lim - a[j], Query(a[j] - 1, tree[1]), tree[2]);
Insert(a[j], Query(lim - a[j] - 1, tree[0]), tree[1]);
}

Thanks.


#12

About 1) BIT_r is tree[3], BIT_k is tree[2], BIT_j is tree[1] and BIT_i is tree[0]

About 2) each line of code does what the editorial mentions in the bullet points after “Suppose we fix L”. Could you be more specific on what you didn’t understand?


#13

I’m sorry to trouble you so much with my doubts. I’m really thankful for your help. :slight_smile:

I don’t understand this part specifically in the editorial I guess.


Use BIT_i to count the number of integers such that ai<aj. Update BIT_j with this number.

Insert ax to BIT_i


How exactly are we using BIT_i to count the number of integers such that ai < aj. What is i and j here? Are they any two indices between L and index[ax] ?

If I get this then I guess it must be the same for updating other trees.


#14

Ah, I see. We are processing the elements from left to right. Something like

for (L = 0; L < N; L++) {

for (x = L+1; L < N; x++) {

 // work on BITs at position x

}

}

“ax” is a[ x ] and by “ai” I mean any index between in [L+1 , x-1].

Inserting “ax” in the BIT is a normal BIT update increasing the frequency of integer a[ x ] by 1.

To know the number of integers less than a[ x ], we can use Query(a[ x ] - 1) on the BIT.