Avoid Fixed Points solution codechef

Avoid Fixed Points solution codechef

 

SOLUTION:- CLICK HERE

 

Chef has a sequence of NN integers A=[A1,A2,,AN]A=[A1,A2,…,AN]. He can perform the following operation any number of times (possibly, zero):

  • Choose any positive integer KK and insert it at any position of the sequence (possibly the beginning or end of the sequence, or in between any two elements).

For example, if A=[5,3,4]A=[5,3,4] and Chef selects K=2K=2, then after the operation he can obtain one of the sequences [2,5,3,4],[5,2,3,4],[5,3,2,4][2_,5,3,4],[5,2_,3,4],[5,3,2_,4], or [5,3,4,2][5,3,4,2_].

Chef wants this sequence to satisfy the following condition: for each 1i≤∣A1≤i≤∣A∣AiiAi≠i. Here, A∣A∣ denotes the length of AA.

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.

Input Format

  • The first line of input contains an integer TT, denoting the number of test cases. The description of TT test cases follows.
  • The first line of each test case contains an integer NN.
  • The second line contains NN space-separated integers A1,A2,,ANA1,A2,…,AN.

Output Format

For each test case, print a single line containing one integer — the minimum number of operations that Chef has to perform to achieve the given condition.

Constraints

  • 1T1041≤T≤104
  • 1N1051≤N≤105
  • 1Ai1091≤Ai≤109
  • Sum of NN over all test caes does not exceed 21052⋅105.

Subtasks

Subtask #1 (100 points): Original constraints

Sample Input 1 

3
3
2 4 5
3
4 1 3
4
3 2 4 2

Sample Output 1 

0
1
2

Explanation

Test case 11: The given sequence does not contain any index ii such that Ai=iAi=i. Hence Chef does not have to perform any operation.

Test case 22: In the given sequence, A3=3A3=3. Chef can choose K=2K=2 and insert it before the first element, making the sequence A=[2,4,1,3]A=[2_,4,1,3], which does not contain any index ii for which Ai=iAi=i.

Test case 33: In the given sequence, A2=2A2=2. Chef can perform the following sequence of operations:

  • Choose K=5K=5 and insert it before the first element. The sequence becomes A=[5,3,2,4,2]A=[5_,3,2,4,2], and now A4=4A4=4.
  • Choose K=3K=3 and insert it between the third and fourth element. The sequence becomes A=[5,3,2,3,4,2]A=[5,3,2,3_,4,2], which does not contain any index ii for which Ai=iAi=i.

It can be verified that there is no way to satisfy the given condition in less than two operations.

SOLUTION:- CLICK HERE

Leave a Comment

Your email address will not be published.