Siirtojärjestäminen

Listassa on lukujen $1,2,\dots,n$ permutaatio, missä $n$ on parillinen. Tehtäväsi on selvittää, voiko listan järjestää seuraavan operaation avulla: valitaan kokonaisluku $i$ väliltä $1 \dots n/2$ ja vaihdetaan keskenään listan $i$ ensimmäistä ja $i$ viimeistä lukua järjestys säilyttäen.

Esimerkiksi kun $n=4$, listan $[3,1,4,2]$ voi järjestää seuraavasti:

$[3,1,4,2] \rightarrow [4,2,3,1] \rightarrow [1,2,3,4]$

Tässä tapauksessa ensimmäisessä operaatiossa $i=2$ ja toisessa operaatiossa $i=1$. Sen sijaan listaa $[3,1,2,4]$ ei ole mahdollista järjestää mitenkään operaation avulla.

Voit olettaa, että $n$ on välillä $2 \dots 10^5$. Tavoitteena on, että algoritmin aikavaativuus on $O(n)$ tai $O(n \log n)$.

Python

Toteuta tiedostoon movesort.py funktio check, joka tarkastaa, voiko listan järjestää.

def check(t):
    # TODO

if __name__ == "__main__":
    print(check([3,1,4,2])) # True
    print(check([3,1,2,4])) # False
    print(check([1,2])) # True
    print(check([4,5,6,1,2,3])) # True
    print(check([4,5,6,3,2,1])) # False

Java

Toteuta tiedostoon MoveSort.java metodi check, joka tarkastaa, voiko listan järjestää.

public class MoveSort {
    public boolean check(int[] t) {
        // TODO
    }

    public static void main(String[] args) {
        MoveSort m = new MoveSort();
        System.out.println(m.check(new int[] {3,1,4,2})); // true
        System.out.println(m.check(new int[] {3,1,2,4})); // false
        System.out.println(m.check(new int[] {1,2})); // true
        System.out.println(m.check(new int[] {4,5,6,1,2,3})); // true
        System.out.println(m.check(new int[] {4,5,6,3,2,1})); // false
    }
}