Friday, December 7, 2012

Codeforces Round #153 (Div. 2): B - Unsorting Array

// Codeforces Round #153 (Div. 2): B - Unsorting Array

import java.io.FileInputStream;
import java.io.IOException;
import java.math.*;
import java.util.*;

public class Main2 {
    private static Scanner in;

    public static void main(String[] args) throws IOException {
        // helpers for input/output
        boolean LOCAL_TEST = false;
        // LOCAL_TEST = true;// comment it before submitting
        in = new Scanner(System.in);
        if (LOCAL_TEST) {
            in = new Scanner(new FileInputStream("E:\\zin2.txt"));
        }

        int N = in.nextInt();
        int[] nums = new int[N];
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int i = 0; i < N; i++) {
            nums[i] = in.nextInt();
            if (nums[i] < min) {
                min = nums[i];
            }
            if (nums[i] > max) {
                max = nums[i];
            }
            if (!map.containsKey(nums[i]))
                map.put(nums[i], 1);
            else
                map.put(nums[i], map.get(nums[i]) + 1);
        }
        if (N <= 2) {
            System.out.println(-1);
            return;
        }
        if (map.size() == 1) {
            System.out.println(-1);
            return;
        }

        // for
        boolean isSortedAsc = isAscending(nums);
        boolean isSortedDesc = isDescending(nums);
        if (isSortedAsc || isSortedDesc) {
            for (int i = 0; i < N - 1; i++) {
                if (nums[i] != nums[i + 1]) {
                    System.out.println((i + 1) + " " + (i + 2));
                    return;
                }
            }
        }
        else {
            for (int i = 1; i < N - 1; i++) {
                int x = nums[i];
                if (x != min && x != max && x != nums[0]) {
                    System.out.println((i + 1) + " " + 1);
                    return;
                }
                if (x != min && x != max && x != nums[N - 1]) {
                    System.out.println((i + 1) + " " + (N));
                    return;
                }
            }
            for (int i = 0; i < N - 1; i++) {
                for (int j = i + 1; j < N; j++) {
                    if (nums[i] != nums[j]) {
                        int tmp = nums[i];
                        nums[i] = nums[j];
                        nums[j] = tmp;
                        if (!isSorted(nums)) {
                            System.out.println((i + 1) + " " + (j + 1));
                            return;
                        }
                        else {
                            tmp = nums[i];
                            nums[i] = nums[j];
                            nums[j] = tmp;
                        }
                    }
                }
            }
        }
        System.out.println(-1);
    }

    static boolean isSorted(int[] n)
    {
        return (isAscending(n) || isDescending(n));
    }

    static boolean isAscending(int[] n) {
        boolean isSortedAscending = true;
        for (int i = 1; i < n.length; i++) {
            if (n[i] < n[i - 1])
                isSortedAscending = false;
        }
        return isSortedAscending;
    }

    static boolean isDescending(int[] n) {
        boolean isSortedDescending = true;
        for (int i = 1; i < n.length; i++) {
            if (n[i] > n[i - 1])
                isSortedDescending = false;
        }
        return isSortedDescending;
    }
}

No comments:

Post a Comment