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

×

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

This question is marked "community wiki".

asked 19 Apr '15, 22:00

mogers's gravatar image

5★mogers
659716
accept rate: 25%

edited 11 Feb '16, 17:54

admin's gravatar image

0★admin ♦♦
19.7k350498541

1

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.

(20 Apr '15, 13:24) himanshujaju6★

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

(20 Apr '15, 23:09) chandan7212★

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

link

answered 20 Apr '15, 02:57

luckfove's gravatar image

4★luckfove
11
accept rate: 0%

2

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

(21 Apr '15, 13:28) pushkarmishra4★

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. :/
I'll be glad if you can explain a little bit further :)

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

Thanks.

link

answered 21 Apr '15, 11:38

codedecode0111's gravatar image

5★codedecode0111
3201215
accept rate: 0%

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.

(21 Apr '15, 15:45) mogers5★

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)

(21 Apr '15, 15:45) mogers5★

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.

(21 Apr '15, 18:12) codedecode01115★

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?

(21 Apr '15, 19:04) mogers5★

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

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.

(21 Apr '15, 21:01) codedecode01115★

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.

(21 Apr '15, 21:23) mogers5★
showing 5 of 6 show all

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

link

answered 21 Apr '15, 12:06

shivam%20duggal's gravatar image

6★shivam duggal
11
accept rate: 0%

can someone tell why I am getting a wa for this solution http://www.codechef.com/viewsolution/6937555

link

answered 15 May '15, 02:46

codedog29's gravatar image

3★codedog29
556
accept rate: 0%

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

link

answered 23 Oct '15, 10:23

sarang235's gravatar image

1★sarang235
1
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:

×15,482
×2,557
×2,086
×146
×62
×2

question asked: 19 Apr '15, 22:00

question was seen: 4,934 times

last updated: 11 Feb '16, 17:54