A. Shandom Ruffle SOLUTION

A. Shandom Ruffle Algorithms Thread Treaps Contest

Those of you who use Java (or are subscribed to SecondThread) likely know that calling Arrays.sort() on an array of primitives in Java can lead to TLE verdicts on Codeforces contests because there are some very specific cases in which quicksort runs in n2 time. There are a couple solutions to this: one is to use Collections.sort() on an ArrayList. This uses mergesort and is always n∗log(n).
Another solution is to shandomly ruffle [aka randomly shuffle] the array before sorting so that it is very very very unlikely that it is still in some undesirable order. One way of doing this is to do the following:
shandom_ruffle(int a, int b, int[] array) {
  int bStart=b;
  while (a<bStart && b<=array.length) {
    swap(array[a], array[b]); //swap the values at indecies a and b
In Java and the psuedocode above, arrays are pass-by-reference. Suppose David starts with the array [1,2,3,4,…n], and calls this method n times on the array, the ith time passing in ai and bi. What will the array look like after these n method calls?
The first line will contain a single integer n. (1≤n≤5∗105)
The following n lines will each contain two integers ai and bi. (1≤a,b≤n) Note that b may be less than or equal to a, in which case the method will not do anything.
Print a single line containing n space-separated integers: the array after it has been shandomly ruffled all n times.
3 1
1 3
3 2
2 3
3 1 4 2
4 1
5 4
3 5
4 5
5 2
1 2 5 3 4
There’s a much easier way to shandom_ruffle that takes O(n), but that makes for a less interesting problem.

Related :

Related :

Leave a Comment

one × four =