LFIVES - Editorial

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

3 Likes

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

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.

1 Like

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

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]);
}
}

 </b>

I'll be glad if you can help me in this. :)

Thanks.

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

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

2 Likes

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[i] + 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.

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)

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.

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?

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.

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.

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