PROBLEM LINK:
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;
}
