CPP Program Winning Strategy- Adhoc Problems

by
  • Our college team is going to the sports fest to play a football match with our coach. There are n players in our team, numbered from 1 to n.
  • The coach will know the position of another team hence creating a winning strategy. He creates the position of every player in a specific order so that we will win and then he starts swapping two players at a time to form the positions.
  • He swaps payers in such a way that it can’t be understood by another team:
    • Any player can swap with the player directly in front of him
    • One player can swap at most with two other players
      If the specific order is formed then our team will win otherwise we will lose

Input Format

  • The First line contains the numbers of players in the team:
  • The second line contains n space-separated integers denoting the specific position of players: i-th integer denotes the position of Ai player in the winning strategy


Output Format

  • If our team wins print “YES”(without quotes) and in the next line print the minimum numbers of swapping required to form this specific order otherwise print “NO”(without quotes)

Constraints:

1 =< n <= 10^5
1 <= Ai <= n

Sample Input1:

5
2 1 5 3 4

Sample Output1:

YES
3

Sample Input2:

5
2 5 1 3 4

Sample Output3:

NO

Explanation:

In the First Sample case,
Initial state: 1 2 3 4 5
Three moves are required to form this order:
1 2 3 4 5 -> 1 2 3 5 4 -> 1 2 5 3 4 -> 2 1 5 3 4
In the second case, no way to form this specific order

Code:

#include<iostream>
using namespace std;
void printer(int *arr, int n)
{
	for(int i=0; i<n; i++)
	{
		cout << arr[i] << " ";
	}
}
int main()
{
	int n;
	cin >> n;
	int* arr = new int[n];
	for(int i=0; i<n; i++)
	{
		cin >> arr[i];
	}
	int count = 0;
	for(int i=n-1; i>=2; i--)
	{
		if(arr[i]==i+1)
		{
			continue;
		}
		else
		{
			if(arr[i-1]==i+1)
			{
				count += 1;
				int temp = arr[i];
				arr[i] = arr[i - 1];
				arr[i - 1] = temp;
			}
			else if(arr[i-2]==i+1)
			{
				count += 2;
				arr[i - 2] = arr[i - 1];
				arr[i - 1] = arr[i];
				arr[i] = i + 1;
			}
			else
			{
				cout << "NO";
				return 0;
			}
		}
	}
	if(arr[0]==2 && arr[1]==1)
	{
		arr[0] = 1;
		arr[1] = 2;
		count += 1;
		cout << "YES" << endl << count;
	}
	else if(arr[0]==1 && arr[1]==2)
	{
		cout << "YES" << endl << count;
	}
	else
	{
		cout << "NO";
	}
}
Code language: C++ (cpp)

Leave a Comment