You are not logged in. Please login at www.codechef.com to post your questions!

×

KETSWAP editorial

PROBLEM LINK:

Practice
Contest

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);
        }
    }
}

asked 06 Oct '16, 09:56

chandubaba's gravatar image

3★chandubaba ♢
713
accept rate: 0%

edited 06 Oct '16, 12:20

admin's gravatar image

0★admin ♦♦
17.1k347485513

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×12,076
×1,125
×84
×3
×2

question asked: 06 Oct '16, 09:56

question was seen: 448 times

last updated: 06 Oct '16, 12:20