RECNDROT - Editorial

PROBLEM LINK:

Practice
Contest

Author: Ritesh Gupta
Tester: Sachin Yadav
Editorialist: Ritesh Gupta

DIFFICULTY:

EASY

PREREQUISITES:

LOWER BOUND/UPPER BOUND, HASHING, GREEDY

PROBLEM:

You are given a sequence A_1, A_2, \ldots, A_N (1 \le N \le 2\cdot10^5 and 1 \le A_i \le 10^9). You define a sequence B_1, B_2, \ldots, B_{N*M} as the concatenation of array A, M times i.e. B = M * A, where M is a positive integer.

You have to find out the minimum value of M such that the length of the longest strictly increasing subsequence of the sequence B is maximum possible.

QUICK EXPLANATION:

If the given sequence contains the D distinct elements and let’s represent by them S = \{d_1, d_2, \ldots, d_D\} then we can calculate the answer as follows:

Step1: Find the valid prefix of S. A prefix is said to be valid if it is also the subsequence of the given sequence and length is maximum possible. If the length of the valid prefix is equal to S then stop else remove the valid prefix from the S and go back to Step1.

The answer is the number of times Step1 executed.

EXPLANATION:

OBSERVATION:

  • If the given sequence contains the D distinct elements then the value of M is at most D.
  • If the given sequence contains the D distinct elements then the length of the longest strictly increasing subsequence possible is equal to D.

We can approach the problem greedily. We assume the initial value of M is 1 as it is given M > 0, CurrElement is equal to the first minimum element, RightPart is equal to the given sequence, and the LefttPart is initially not defined.

  • Step1: We try to find the minimum possible index of CurrElement in RightPart. If there exists a value equal to CurrElement in RightPart and its index is k then we update the two parts and CurrElement as following and go to Step 1:

    • LeftPart = given sequence up to k^{th} index.
    • RightPart = given sequence from k^{th} index to end.
    • CurrElement = next minimum element (> CurrElement) of the given sequence.
  • Step2: If no value matches the CurrElement in RightPart then it should be present in the LeftPart. So, we try to find the minimum possible index of CurrElement in LeftPart. Let its index is k then we update the two parts, CurrElement and M as following and go to Step 1:

    • LeftPart = given sequence up to k^{th} index.
    • RightPart = given sequence from k^{th} index to end.
    • CurrElement = next minimum element (> CurrElement) of the given sequence.
    • M = M + 1

    If the CurrElement is equal to the maximum element of the given sequence then stop.

We can maintain the hash for each distinct value and perform the above-mentioned operations efficiently.

COMPLEXITY:

TIME: O(NlogN)
SPACE: O(N)

SOLUTIONS:

Setter's Solution
#include <bits/stdc++.h>
using namespace std;
 
int main()
{
    int t;
    cin >> t;
    
    while(t--) {
        int n,x;
        cin >> n;
        
        map <int,vector<int> > m;
        
        for(int i=0;i<n;i++) {
            cin >> x;
            m[x].push_back(i);
        }
        
        int prev_ind = n;
        int ans = 0;
        
        for(auto i:m) {
            if(i.second.back() < prev_ind) {
                ans++;
                prev_ind = i.second[0];
            }
            else
                prev_ind = *lower_bound(i.second.begin(),i.second.end(),prev_ind);
        }
        cout << ans << endl;
    }
}
Tester's Solution
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll const max_N=2e5+5;
ll T, N, arr[max_N];
unordered_map<ll,vector<ll>> umap;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>T;
    while(T--)
    {
        cin>>N;
        for(int i=0; i<N; i++)
        {
            cin>>arr[i];
            umap[arr[i]].emplace_back(i);
        }
        sort(arr,arr+N);
        ll ans=1, last=umap[arr[0]][0];
        for(int i=1; i<N; i++)
        {
            if(arr[i]==arr[i-1]) continue;
            vector<ll> &vect=umap[arr[i]];
            auto up_it=upper_bound(vect.begin(),vect.end(),last);
            if(up_it==vect.end())
            {
                last=vect[0];
                ans++;
            }
            else last=*up_it;
        }
        cout<<ans<<"\n";
        umap.clear();   
    }
    return 0;
}  
11 Likes

Can someone tell me whats wrong with this python solution? Struggled to find out the issue, checked other solutions that passed and could not spot the issue in logic

https://www.codechef.com/submit/RECNDROT
I tried lot of test cases and it was correct.when i submitted i got wrong can anyone please tell me where my code is getting wrong answer

Send your code link .

https://www.codechef.com/viewsolution/32365175

https://www.codechef.com/viewsolution/32367760
can anyone please tell me what is wrong with my solution ??I already tried many combinations but still didn’t get what is wrong.

Even I implemented the exact same logic as yours. Getting WA as well. Don’t know why…Help anyone…?
Solution

Why cant we say that the ans is equal to (n-Lis+1) where n is the number of distinct elements

https://www.codechef.com/viewsolution/32363944
I cant get the test case where my code is wrong ? , Can someone look at it once?

Can someone please point out where am I going wrong in this solution
https://www.codechef.com/viewsolution/32363838

what is ‘Lis’?

Longest Increasing subsequence

Longest increasing subsequence

check your code for the input : 2,1,3,2,4
you’ll find out the error

1 Like

[10,11,12,6,7,8,1,2,3,4,5]
Lis = 1,2,3,4,5
ans = 11-5+1=7
but actual ans must be 3.

1 Like

got it thanks

Thanks a lot.I got it

why actual ans must be 3? If M=2 we can get the LIS.

If u don’t append anything then M=1. so M must be 2+1

Oh! got it :sweat_smile: