Fype's blog

By Fype, 4 years ago, In English

Problem : You have an array a of size $$$n$$$. for each $$$i$$$ ($$${i \le n}$$$) you have to find maximum $$$j$$$ such that $$${1 \le j < i}$$$ and $$${a_j > a_i}$$$ and if there is no $$$j$$$, consider the answer for $$$i$$$ equal to $$$0$$$, solve the problem with total complexity $$${O(n)}$$$.

Solution 1 : Of course there is an easy solution using stack.

for (int i = 1; i <= n; i++) {
    while (s.size() && a[s.top()] <= a[i])
        s.pop();
    if (s.size())
        L[i] = s.top();
    s.push(i);
}

Solution 2 : About 2-3 month ago I suggested a dp solution for this problem and i never thought that it would be $$${O(n)}$$$ but here I am sharing it with you :D
$$${dp_i = }$$$ answer for i.
So how can we update this dp?!, let's check maximum $$$j$$$ that can be the answer for $$$dp_i$$$. It's obvious that if $$${a_{i - 1} > a_i}$$$ the answer is $$$i - 1$$$.
what if $$${a_{i - 1} \le a_i}$$$ : then the answer isn't in range $$$(dp_{i - 1}, i]$$$ so the next number we should check is $$$dp_{i - 1}$$$ and if it wasn't answer that we need we should check $$$dp_{dp_{i - 1}}$$$, and then $$$dp_{dp_{dp_{i - 1}}}$$$ and so on.
Do you see the pattern?! :D

int find_ans(int i, int j) {
    if (!j)
        return j;
    return (a[j] > a[i]? j: find_ans(i, dp[j]));
}
for (int i = 1; i <= n; i++)
    dp[i] = find_ans(i, i - 1);

some problems :

Task Postering (pla)
Psychos in a Line
Task Little Bird (pta)
These problems aren't necessarily the exact problem but the main idea is same.

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

| Write comment?
»
4 years ago, # |
  Vote: I like it -8 Vote: I do not like it

Why it is O(n)?

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

    If you go through some $$$dp_x$$$ one time in find_ans function you will never check it again.

»
4 years ago, # |
  Vote: I like it +21 Vote: I do not like it

I think the idea between the two solutions is the exact same. It just so happens that the implementation of the stack is different (instead of explicitly maintaining the stack, you simulate it through back pointers). This is also described here.

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    yeah, I know and it was cool the first time I came up with it. I didn't check if it was in Wikipedia or not, I just checked codeforces, sorry :D

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The DP solution gives me strong KMP vibes.