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

ZigZag Array
Автор daihan, 9 лет назад, По-английски

Hello codeforces community , problem ZigZag array is for distinct data , I solved this problem . But if data are duplicate(same data occur several times) problem become very complex . There has many corner case :

11

2 4 6 8 9 11 10 8 5 3 1

=>2 8 8 1 ( solution 1, remove 7 numbers)

=>2 11 1 (solution 2, remove 8 numbers)

so ans is 7

10

1 2 3 4 7 8 9 7 6 4

=>1 4 4 (solution 1, remove 7 numbers)

=>1 7 7 4 (solution 2, remove 6 numbers)

=>1 9 4 (solution 3, remove 7 numbers)

so ans is 6

6

1 2 3 4 5 4

=>1 4 4 (solution 1, remove 3 numbers)

=>1 5 4 (solution 2, remove 3 numbers)

so ans is 3

5

1 2 3 2 1

=>1 2 2 1 (solution 1, remove 1 number)

=>1 3 1 (solution 2,remove 2 numbers)

so ans is 1

If 1<=n<=10^5 , How to solve this problem ? and how to implement it efficiently ? I implement it but code become very complex : https://pastebin.com/QrhWgdEj

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

»
9 лет назад, скрыть # |
← Rev. 11  
Проголосовать: нравится +18 Проголосовать: не нравится

You are not using DP on this problem, but you can solve simply with using DP in O(n2) (because n ≤ 100). First, the problem is asking "minimum number of deletion", but it is same value to n — "maximum length of zigzag subsequence". Second, let dp[i][0] = "the maximum length of subsequence that ends in i and satisfying (the second element from the last) > (the last element), and dp[i][1] is almost same definition but (the second last) < (the last). And, the DP relation is: dp[i][0] = max(1, maxj < i, a[j] > a[i]{dp[j][1] + 1}), and dp[i][1] = max(1, maxj < i, a[j] < a[i]{dp[j][0] + 1}). Finally the answer is n - max(dp[n - 1][0], dp[n - 1][1]). My code is here (16-line in C++)
This is a main idea, but if the array has same values, you have to add dp[i][2] for equal and change DP relation a little.
EDIT: It's n ≤ 100 (real contest constraints) solution (It's O(n2) and of course if n ≤ 10000 you can solve it). I know you edited the blog and changed the constraints to n ≤ 100000.

→ Ответить
»
9 лет назад, скрыть # |
 
Проголосовать: нравится +11 Проголосовать: не нравится 
just check left & right of the vector if somewhere condition will true.

#include <bits/stdc++.h>
using namespace std;

vector<int>v;

bool solve(int x, int y, int z)
{
    if(x >= v.size() || y >= v.size() || z >= v.size() || !x || !y || !z)
        return false;
    if( v[x] > v[y] && v[y] > v[z] )
        return true;
    if( v[x] < v[y] && v[y] < v[z] )
        return true;
    return false;
}

int main()
{
    int n, i, x, cnt=0;
    cin >> n;

    v.push_back(0);

    for(i=1; i<=n; i++)
    {
        cin >> x;
        v.push_back(x);
    }
    for(i=1; i<=v.size()-2; i++)
    {
        if( solve(i, i+1, i+2) && v.size() >= 3 )
        {
            cnt++;
            if( solve(i+1, i+2, i+3) )
                v.erase(v.begin()+i+2);
            else if( solve(i-1, i, i+1) )
                v.erase(v.begin()+i);
            else
                v.erase(v.begin()+i+1);
            i--;
        }
    }
    cout << cnt << endl;
    return 0;
}
→ Ответить