asawa_harsh's blog

Explanation required for understanding Atcoder ARC133B Editorial
By asawa_harsh, history, 3 years ago, In English

Problem Link

Editorial Link

Samples —

3 1 4 2

4 2 1 3

According to the editorial we are taking pairs of indices which form a valid pair (Qj,Pi). All pairs are = (0,3)(1,0),(1,1)(1,2)(1,3)(2,0)(3,0)(3,1). [zero based indexing] Now we are sorting according to (i,-j).

New order of pairs is = (0,-3)(1,-3),(1,-2)(1,-1)(1,0)(2,0)(3,-1)(3,0). Now taking LIS considering only j's, we have ans as 4 but answer should be 2.

There is no clear explanation in the editorial, no C++ sample solution in the editorial and No english youtube video explaining this approach. I also tried to understand solutions of top rated coders but I think they have used fenwick tree.

Can anyone explain please I am stuck in this question since a day trying to understand this editorial.

  • Vote: I like it
  • +1
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You have to sort according to $$$(i, -j)$$$, but you have to find the LIS considering $$$j$$$ (not $$$-j$$$).

The LIS of $$$[3, 3, 2, 1, 0, 0, 1, 0]$$$ has length $$$2$$$.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks!

    Can you please explain the intuition behind using LIS dp approach in this question?

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How I came up to the solution during the contest:

      • We are interested in pairs $$$(a_i, b_i)$$$ where $$$b_i$$$ is a multiple of $$$a_i$$$. There are $$$O(n \log n)$$$ such pairs.
      • For each pair $$$(a_i, b_i)$$$ with $$$i \geq 2$$$, $$$a_{i-1} < a_i$$$ and $$$b_{i-1} < b_i$$$. So, the maximum length of a subsequence that finishes with $$$(a_i, b_i)$$$ is $$$1\phantom{'}+ $$$ the maximum length of a subsequence that finishes with any valid $$$(a_{i-1}, b_{i-1})$$$. We are calculating lengths using previous lengths, so let's use DP.
      • While calculating the DP, we have to guarantee $$$a_{i-1} < a_i$$$ and $$$b_{i-1} < b_i$$$. The first condition can be handled by considering the $$$a_i$$$ in increasing order. The second condition can be handled by using any data structure that calculates the maximum $$$x_i$$$ in a prefix (i.e. $$$1 \leq i \leq p$$$) and supports point updates. The simpler one is Fenwick tree.

      I actually didn't realize this is a LIS during the contest, but you could notice that while handling the second condition (i.e., after considering $$$a_i$$$ in increasing order, the $$$b_i$$$ should be increasing and as many as possible, so it's a LIS).

      → Reply