NOFIX- Editorial

editorial
, , ,
1

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;
}
1 Like
2

I did this question by traversing and comparing and then inserting a number if found equal, for that I used deque, at first, because it’s insertion has complexity of O(1) but in one of the hidden test case, i got TLE, Then i used list and it passed all the test cases.

Using list AC
Using Deque TLE

Why did this happen? when in both cases, i was traversing through the container and both insert has complexity of O(1).

why i did, what i did…
In some text, it is mentioned that the insertion and deletion is fast in list as compared to deque and some post mentions that it is better to use deque and vector over list because there is to much random accessing of memory involved in list…that’s why I used deque at first and got TLE.

Can somebody please clarify these, as in when i must use list and what was the case in this question?

1 Like
3

can anyone tell ,me my mistake||||

#include<bits/stdc++.h>
using namespace std;
int m = 1000000001;
int main()
{
int T;
cin>>T;
while(T–){
int n;
cin>>n;
int a[100001];
for(int i=1;i<=n;i++){
cin>>a[i];
}

int flag=0; sets;
for(int i=1;i<=n;i++){

if(a[i]==i){
flag=1;
s.insert(a[i]-i);
}
else if(flag==1 && a[i]>i)
s.insert(a[i]-i);
}

for(int i=0;i<= n;i++){
if(s.find(i)==s.end()){
cout<<i<<endl;
break;
}
}

}
return 0;
}

4
  1. What is ‘s’ in your program.
  2. what is sets?.. The ways you are defining it, even if it is a variable, it is wrong.
  3. a[i]-i will give 0, if there is 1 at first index.

and many more…

At least, at first try to debug it yourself and share code’s link or copy paste it using preformatted text, it will make it easier to look at the code.

1 Like