PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Setter: Soumyadeep Pal
Tester: Manan Grover, Tejas Pandey
Editorialist: Kanhaiya Mohan
DIFFICULTY:
Simple
PREREQUISITES:
None
PROBLEM:
Chef has a sequence of N integers A = [A_1, A_2, …, A_N]. He can perform the following operation any number of times (possibly, zero):
- Choose any positive integer K and insert it at any position of the sequence (possibly the beginning or end of the sequence, or in between any two elements).
Chef wants this sequence to satisfy the following condition:
- For each 1 \leq i \leq |A|, A_i \neq i. Here |A| denotes the length of A.
Help Chef to find the minimum number of operations that he has to perform to achieve this goal. It can be proved that under the constraints of the problem, it’s always possible to achieve this goal in a finite number of operations.
EXPLANATION:
Observation 1
For a given element A_i which was initially present at position i, if there were X number of insertions made before position i, the new position of A_i is (i+X).
Observation 2
Note that the position of an element can never be decreased. In other words, an element can only be shifted to its right.
Solution
We refer to an element by its original position.
We traverse the array from left to right. Suppose we are at the i^{th} position and we have already made X operations by now to satisfy the given condition for all indices from 1 to i-1. This means that the new position of the i^{th} element is (i+X). There are two possible cases:
- A_i \neq (i+X): This means that we do not need to perform any operation for this element as its updated position already satisfies the condition. For any elements with index >i, we make perform operations such that the position of this element does not change anymore.
-
A_i = (i+X): This means that we need to change the position of this element. We can do this by performing only 1 operation.
We insert a number Y\neq (i+X) at position (i+X). The position of A_i now becomes (i+X+1) and the condition is satisfied. Note that we have now performed (X+1) operations in total and all the elements from positions 1 to i satisfy the given condition now.
We keep updating X (the count of operations) in each iteration and the value of X at the end is our final answer.
TIME COMPLEXITY:
The time complexity is O(N) per test case.
SOLUTION:
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while(t--){
int n;
cin >> n;
int ans = 0;
for(int i = 1; i <= n; i++){
int x;
cin >> x;
if(i + ans == x){
ans++;
}
}
cout << ans << '\n';
}
}
Tester's Solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while(t--) {
int n; cin >> n;
int a[n];
for(int i = 0; i < n; i++) cin >> a[i];
int ans = 1;
for(int i = 0; i < n; i++)
if(a[i] == i + ans)
ans++;
cout << ans - 1 << "\n";
}
return 0;
}
Editorialist's Solution
#include <iostream>
using namespace std;
int main() {
int t;
cin>>t;
while(t--){
int n;
cin>>n;
int a[n+1];
for(int i = 1; i<=n; i++){
cin>>a[i];
}
int inserted = 0;
for(int i = 1; i<=n; i++){
if(a[i] == (i+inserted)){
inserted++;
}
}
cout<<inserted<<endl;
}
return 0;
}