Google codejam qualification round question no 2 solution

TROUBLE SORT:

Problem:

Deep in Code Jam's secret algorithm labs, we devote countless hours to wrestling with one of the most complex problems of our time: efficiently sorting a list of integers into non-decreasing order. We have taken a careful look at the classic bubble sort algorithm, and we are pleased to announce a new variant.

The basic operation of the standard bubble sort algorithm is to examine a pair of adjacent numbers, and reverse that pair if the left number is larger than the right number. But our algorithm examines a group of threeadjacent numbers, and if the leftmost number is larger than the rightmost number, it reverses that entire group. Because our algorithm is a "triplet bubble sort", we have named it Trouble Sort for short.

  TroubleSort(L): // L is a 0-indexed list of integers
    let done := false
    while not done:
      done = true
      for i := 0; i < len(L)-2; i++:
        if L[i] > L[i+2]:
          done = false
          reverse the sublist from L[i] to L[i+2], inclusive

For example, for L = 5 6 6 4 3, Trouble Sort would proceed as follows:

First pass:
- inspect 5 6 6, do nothing: 5 6 6 4 3
- inspect 6 6 4, see that 6 > 4, reverse the triplet: 5 4 6 6 3
- inspect 6 6 3, see that 6 > 3, reverse the triplet: 5 4 3 6 6
Second pass:
- inspect 5 4 3, see that 5 > 3, reverse the triplet: 3 4 5 6 6
- inspect 4 5 6, do nothing: 3 4 5 6 6
- inspect 5 6 6, do nothing: 3 4 5 6 6
Then the third pass inspects the three triplets and does nothing, so the algorithm terminates.

We were looking forward to presenting Trouble Sort at the Special Interest Group in Sorting conference in Hawaii, but one of our interns has just pointed out a problem: it is possible that Trouble Sort does not correctly sort the list! Consider the list 8 9 7, for example.

We need your help with some further research. Given a list of N integers, determine whether Trouble Sort will successfully sort the list into non-decreasing order. If it will not, find the index (counting starting from 0) of the first sorting error after the algorithm has finished: that is, the first value that is larger than the value that comes directly after it when the algorithm is done.

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case consists of two lines: one line with an integer N, the number of values in the list, and then another line with N integers V_i, the list of values.

Output

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is OK if Trouble Sort correctly sorts the list, or the index (counting starting from 0) of the first sorting error, as described above.

Limits

1 ≤ T ≤ 100.
0 ≤ V_i ≤ 10⁹, for all i.
Memory limit: 1GB.

Test set 1 (Visible)

3 ≤ N ≤ 100.
Time limit (for the entire test set): 10 seconds.

Test set 2 (Hidden)

3 ≤ N ≤ 10⁵.
Time limit (for the entire test set): 20 seconds.

Special Note

Notice that test set 2 for this problem has a large amount of input, so using a non-buffered reader might lead to slower input reading. In addition, keep in mind that certain languages have a small input buffer size by default.

Sample

Input	Output
2 5 5 6 8 4 3 3 8 9 7	Case #1: OK Case #2: 1

Sample Case #1 is similar to the first one described in the problem statement. Trouble Sort correctly sorts this list, so the answer is OK.

Sample Case #2 is the second one described in the problem statement. Trouble Sort does not correctly sort this list, since it terminates with the list 7 9 8. The 9 is the first value in the list that is larger than the next value, so the index of the first sorting error is 1.

SOLUTION: CPP

// SUBLIME HAX

/*nope

cat

// sixteen chars// sixteen chars// sixteen chars// sixteen chars// sixteen chars// sixteen chars// sixteen chars// sixteen chars// sixteen chars// sixteen chars// sixteen chars// sixteen chars// sixteen chars// sixteen chars// sixteen chars// sixteen chars// sixteen chars// sixteen chars// sixteen chars// sixteen chars// sixteen chars// sixteen chars// sixteen chars// sixteen chars// sixteen chars// sixteen chars// sixteen chars// sixteen chars// sixteen chars// sixteen chars// sixteen chars// sixteen chars// sixteen chars// sixteen chars// sixteen chars// sixteen chars// sixteen chars// sixteen chars// sixteen chars// sixteen chars// sixteen chars// sixteen chars// sixteen chars// sixteen chars// sixteen chars// sixteen chars// sixteen chars// sixteen chars// sixteen chars// sixteen chars// sixteen chars// sixteen chars// sixteen chars// sixteen chars// sixteen chars// sixteen chars// sixteen chars// sixteen chars// sixteen chars// sixteen chars// sixteen chars// sixteen chars// sixteen chars// sixteen chars

// ayy

// ' lamo

#include <algorithm>

#include <bitset>

#include <complex>

#include <deque>

#include <fstream>

#include <functional>

#include <initializer_list>

#include <iomanip>

#include <ios>

#include <iosfwd>

#include <iostream>

#include <iterator>

#include <limits>

#include <list>

#include <map>

#include <numeric>

#include <queue>

#include <random>

#include <ratio>

#include <regex>

#include <set>

#include <sstream>

#include <stack>

#include <string>

#include <tuple>

#include <unordered_map>

#include <unordered_set>

#include <utility>

#include <valarray>

#include <vector>

using namespace std;

template<class T,class U>

ostream &operator<<(ostream &os,const pair<T,U> &x) {

return os<<"("<<x.first<<","<<x.second<<")";

}

namespace dbg_ns {

template<typename C>

struct is_iterable {

template<class T> static long check(...);

template<class T> static char check(int,

typename T::const_iterator = C().end());

enum {

value = sizeof(check<C>(0)) == sizeof(char),

neg_value = sizeof(check<C>(0)) != sizeof(char)

};

template<class T> ostream &_out_str(ostream &os,const T &x) {

return os<<'"'<<x<<'"';

}

template<class T> ostream &_dbg2_5(ostream &,const T &);

template<bool B,typename T=void> using eit=typename enable_if<B,T>::type;

template<class T>

inline ostream &_dbg3(ostream &os,eit<is_iterable<T>::neg_value,const T> &x) {

return os<<x;

}

template<class T>

inline ostream &_dbg3(ostream &os,eit<is_iterable<T>::value,const T> &V) {

os<<"{";

bool ff=0;

for(const auto &E:V) _dbg2_5(ff?os<<",":os,E), ff=1;

return os<<"}";

}

template<>

inline ostream &_dbg3<string>(ostream &os,const string &x) {

return _out_str(os,x);

}

template<>

inline ostream &_dbg3<const char *>(ostream &os,const char *const &x) {

return _out_str(os,x);

}

template<class T> inline ostream &_dbg2_5(ostream &os,const T &x) {

return _dbg3<T>(os,x);

}

template<class T,typename... Args> ostream &_dbg2(ostream &os,vector<string>::iterator nm,const T &x,Args&&... args);

inline ostream &_dbg2(ostream &os,vector<string>::iterator) { return os; }

template<typename... Args>

inline ostream &_dbg2(ostream &os,vector<string>::iterator nm,const char *x,Args&&... args) {

return _dbg2(_dbg3<const char *>(os<<" ",x),nm+1,args...);

}

template<class T,typename... Args>

inline ostream &_dbg2(ostream &os,vector<string>::iterator nm,const T &x,Args&&... args) {

return _dbg2(_dbg3<T>(os<<" "<<*nm<<"=",x),nm+1,args...);

}

vector<string> split(string s) {

vector<string> Z;

string z="";

s+=',';

int dep=0;

for(char c:s) {

if(c==',' && !dep) Z.push_back(z),z="";

else z+=c;

if(c=='(') ++dep;

if(c==')') --dep;

}

return Z;

}

template<typename... Args> inline ostream &_dbg1(int ln,const string &nm,Args&&... args) {

auto nms=split(nm);

return _dbg2(cerr<<"L"<<ln<<":",nms.begin(),args...)<<endl;

}

#define dbg(...) dbg_ns::_dbg1(__LINE__,#__VA_ARGS__,__VA_ARGS__)

#define sz(x) (int(x.size()))

#define eprintf(...) fprintf(stderr,__VA_ARGS__)

#define fi first

#define se second

#define pb push_back

// END SUBLIME HAX

// #include <bits/extc++.h>

// using namespace __gnu_pbds;

typedef unsigned long long ull;

typedef long long ll;

typedef long double ld; //CARE

typedef complex<ld> pt;

const ld eps=(ld)1e-8;

const ld tau=2*(ld)acosl(-1);

const int inf=1e9+99;

const ll linf=1e18+99;

const int P=1e9+7;

const int N=100<<10;

int n,a[N],b[N],c[N];

int an=0,bn=0;

void go(int tn) {

scanf("%d",&n);

an=bn=0;

for(int i=0;i<n;i++) {

if(!(i&1)) scanf("%d",a+an++);

else scanf("%d",b+bn++);

}

sort(a,a+an);

sort(b,b+bn);

for(int i=0;i<an;i++) c[i+i]=a[i];

for(int i=0;i<bn;i++) c[i+i+1]=b[i];

printf("Case #%d: ",tn);

for(int i=0;i+1<n;i++) {

if(c[i]>c[i+1]) {

printf("%d\n",i);

return;

}

printf("OK\n");

}

int32_t main() {

int T; scanf("%d",&T); for(int t=1;t<=T;t++) go(t);

}

Search This Blog

program_X