PROBLEM LINK:
Author: Chandan Boruah
Tester: Chandan Boruah
Editorialist: Chandan Boruah
DIFFICULTY:
CAKEWALK
PREREQUISITES:
Sorting, Understanding of indexes of array.
PROBLEM:
Given a few numbers in ascending order, from 1 to N, according to to its own value. And given another array(lets call it V) where each number is sorted in ascending order according to its value. Example: 2 1 3, here 2<1<3 in value. Thus, the number has two values one its own and another according to the list given. Sort the items(or numbers) according to list given and find the count of swaps required while doing a bubble sort on the numbers. Print that count of swaps.
Advanced EXPLANATION:
Do sorting on the items and sort them by finding the index of the number on the given array and do the sorting accordingly. You can alternatively sort the given array and count the number of swaps there. Because this will also count the number of swaps to get the given array from the original list of numbers.
EXPLANATION:
//value list is the list 2<1<3…and original list is 1<2<3
N is number of items in the array V of value list given
for i 0 to N
for j 0 to N-1
ind1=index of number[j] in array V
ind2=index of number[j+1] in array V
if(ind1>ind2)
swap number[j] and number[j+1]
swaps++
print swaps;
Here what we did a bubble sort and every inner loop we found the index of the number at index j and j+1 (bubble sorting), in the value array V. If its not ascending according to it, then we swap it and increament swap by 1.
Another approach is
//V is the value array 2<1<3
for i 0 to N
for j 0 to N-1
if(V[j]>V[i])
swap V[j] and V[j+1]
swaps++
print swaps;
Here since the original array is sorted in ascending order according to own value 1<2<3, so when we do bubble sort on the value array V to get sorted array will have same number of swaps as finding swaps from original to value sorted.
AUTHOR’S AND TESTER’S SOLUTIONS:
using System;
using System.Collections.Generic;
class some
{
public static void Main()
{
int n=Int32.Parse(Console.ReadLine());
for(int t=0;t<n;t++)
{
int rem=Int32.Parse(Console.ReadLine());
string[]ss=Console.ReadLine().Split();
int[]arr=new int[rem];
int[]or=new int[rem];
for(int i=0;i<arr.Length;i++){arr[i]=i+1;or[i]=Int32.Parse(ss[i]);}
int swaps=0;
for(int i=0;i<ss.Length;i++)
{
for(int j=0;j<ss.Length-1;j++)
{
int a=Array.IndexOf(or,arr[j]);
int b=Array.IndexOf(or,arr[j+1]);
if(a>b)
{
int temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
swaps++;
}
}
}
Console.WriteLine(swaps);
}
}
}