Блог пользователя Fype

Автор Fype, 4 года назад, По-английски

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.

  • Проголосовать: нравится
  • +75
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

Why it is O(n)?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +20 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +21 Проголосовать: не нравится

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 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

The DP solution gives me strong KMP vibes.