Z Sort

Problem Write-up

http://codeforces.com/problemset/problem/652/B

Solution

We see from the problem description that every number at an even array index i = 2, 4, 6,… must be greater than or equal to the number at the odd index preceding it. Similarly, every number at an odd array index must be less than or equal to the number at the index preceding it.

Based on these constraints, we can deduce that any array with numbers at even indices being greater than or equal to the numbers on either side of it satisfies the necessary conditions.

When is it impossible to z-sort an array? Consider the following:

Sort any array a of length n. The first ceiling(n/2) elements must be greater than the remaining floor(n/2) elements in the array (where ceiling() rounds any decimal number up to the next integer value and floor() rounds any decimal number down to the next integer value). Therefore, by inserting the last floor(n/2) elements of the sorted array in between the first ceiling(n/2) elements of the array in the following manner:

element 1, element ceiling(n/2)+1, element 2, element ceiling(n/2) + 2, …

we can ensure that a z-sorted array can always be created from any array a. Therefore, it is always possible to z-sort an array as required in the problem description.

Code

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;


public class ZSort {
    Scanner in = new Scanner(System.in);
    ArrayList<Integer> a = new ArrayList<>();
    int n;


    private void read(){
        n = in.nextInt();
        for (int i = 0; i < n; i++) {
            a.add(in.nextInt());
        }
    }

    private void solve(){
        List<Integer> odds; // numbers at odd indices (array starts with index 1)
        List<Integer> evens; // numbers at even indices (array starts with index 1)

        Collections.sort(a);

        odds = a.subList(0, (int)Math.ceil(n/2.0));
        evens = a.subList((int)Math.ceil(n/2.0), n);

        for (int i = 0; i < n/2;i++){
            System.out.print(odds.get(i) + " ");
            System.out.print(evens.get(i) + " ");
        }
        if (n%2 != 0) {
            System.out.print(odds.get(n/2));
        }

        System.out.println();

    }


    public static void main(String[] args) {
        ZSort z = new ZSort();
        z.read();
        z.solve();

    }
}