IPSC 2016 Problem K – Kill switch

IPSC 2016

Problem K – Kill switch

A kill switch is a mechanism used to shut off a device in an emergency situation.

Jeremy was hired as a contractor by a shady software company. After he finished his work the company pointed to a loophole in the contract and refused to pay him anything for his work. Little do they know that Jeremy suspected foul play and thus he hid a kill switch in his code.

Problem specification

You are given the implementation of a function that pretends to sort an array of 32-bit unsigned integers into a non-decreasing order. Find the shortest input the function fails to sort.

Input specification

In each subproblem there are two input files: one is a C++ implementation and the other a Python implementation of the same function.

(You may assume that if the answer is n, the two programs behave the same way at least on all valid inputs of size up to n + 47. Note that huge inputs may cause integer overflows in the C++ implementation. Such inputs are not a part of this problem and they can be safely ignored.)

Each subproblem should be solved separately.

Output specification

Your output file should contain two lines. The first line should contain a nonnegative integer n: the smallest possible length of an array that is not sorted correctly. The second line should contain one possible initial content of the array: the sequence A[0],…,A[n − 1]. These values must satisfy 0 ≤ A[i]<2³².

Example

Input:

void example_sort(vector<unsigned> &A) {
    int N = A.size();
    if (N >= 2 && A[0] > A[1])
        swap( A[0], A[1] );
    if (N >= 3 && A[0] > A[2])
        swap( A[0], A[2] );
    if (N >= 3 && A[0] > A[1])
        swap( A[0], A[1] );
}
-----------------------------------------
def example_sort(A):
    N = len(A)
    if N >= 2 and A[0] > A[1]:
        A[0], A[1] = A[1], A[0]
    if N >= 3 and A[0] > A[2]:
        A[0], A[2] = A[2], A[0]
    if N >= 3 and A[0] > A[1]:
        A[0], A[1] = A[1], A[0]

Output:

3
42 47 1