Editorial for PokeCard

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

English

The problem asks us the biggest sequence of non-decreasing numbers that does not have the same number used more than K times. Lets call the given input Sequence SEQin. To solve this problem we can look at it from a different perspective since finding a non-decreasing sequence of numbers inside SEQin is same as finding the longest common subsequence of SEQin and the sorted version of SEQin(which will now be called SEQsort).

The important thing about this problem is that a number can be at most selected K times. So if the both of the sequences have the same number more than K times than the LCS result can also include the same number more than K times. To solve this problem we remove the repeating numbers after K from the SEQsort and use LCS.

Turkish

Problem bize aynı sayının K kereden daha fazla kullanılmadığı en büyük azalan sayı dizisini sormakta. Verilen girdiyi SEQin olarak adlandıralım. Bu soruyu çözmek için farklı bir perspektiften bakabiliriz, çünkü SEQin içinde azalmayan bir sayı dizisi bulmak, SEQin'in ve SEQin'in sorted versiyonunun LCS'ini(longest common subsequence) bulmakla aynı analama geliyor.

Bu problemle ilgili önemli olan nokta ise, seçilen bir sayının en fazla K kez tekrar edebileceğidir. Dolayısıyla, her iki dizi de K defadan fazla aynı sayıya sahipse,LCS sonucu da aynı sayıyı K defadan fazla içerebilir. Bu yüzden K'dan fazla tekrar eden sayıları SEQsort'tan çıkarıp LCS kullanarak en K'dan fazla tekrar etmeyen azalmayan en uzun diziyi ve böylece sonucu bulabiliriz.

Code

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

int main(){
    int n,k;
    cin>>n>>k;
    int arr1[n],arrTemp[n];
    for(int i=0;i<n;i++){
        cin>>arr1[i];
        arrTemp[i]=arr1[i];
    }
    sort(arrTemp,arrTemp+n);

    //--------------setting second array for LCS--------------
        //decreasing number of max use to k
    int M=0;
    for(int i=k;i<n;i++){
        if(arrTemp[i]==arrTemp[i-k])M++;            //finding number of repetations after k  
    }
    M=n-M;                                          //calculating number of unrepeated elements up to k
    int arr2[M];
    for(int i=0;i<k;i++)arr2[i]=arrTemp[i];         //adding first k elements
    for(int i=k,j=k;i<n;i++){                       //adding elements up to same k elements
        if(arrTemp[i]!=arrTemp[i-k]){
            arr2[j]=arrTemp[i];
            j++;
        }           
    }
    //--------------------------------------------------------




    int dyn[n][M];

    //-------base case-------------
    if(arr1[0]==arr2[0])dyn[0][0]=1;
    else dyn[0][0]=0;

    for(int i=1;i<n;i++){
        if(arr1[i]==arr2[0])dyn[i][0]=1;
        else dyn[i][0]=dyn[i-1][0];
    }
    for(int i=1;i<M;i++){
        if(arr1[0]==arr2[i])dyn[0][i]=1;
        else dyn[0][i]=dyn[0][i-1];
    }
    //-----------------------------

    for(int i=1;i<n;i++){
        for(int j=1;j<M;j++){
            int temp;

            if(arr1[i]==arr2[j])temp=dyn[i-1][j-1]+1;
            else temp=dyn[i-1][j-1];
            dyn[i][j]=max(temp,max(dyn[i][j-1],dyn[i-1][j]));
        }
    }

    cout<<dyn[n-1][M-1]<<endl;

}