Why too late ?

Monday, July 28, 2008

I will make it quick. This is the C++ solution that I used to solve Google Code Jam Online Round 1C - Question 1. (it's so dumb, I know).


//
typedef long long int64;
typedef vector<int64> vi;

#define For(i,a,b) for (int i(a),_b(b); i <= _b; ++i)
#define Rep(i,n) for (int i(0),_n(n); i < _n; ++i)

int main() {

freopen("in.in", "rt", stdin);
freopen("out.out", "wt", stdout);

int t;
cin >> t;
For(test, 1, t) {

int P,K,L;
cin >> P >> K >> L;

vector<vi> kk;

Rep(i, K){
vi vec;
kk.push_back(vec);
}

int64 letters[L];

Rep(i, L){
cin >> letters[i];
}

sort(AllA(letters,L));

int kx = 0;
Rep(i, L){
int64 l = letters[(L-i)-1];
bool put = true;
do{
int s = kk[kx].size();
if( s < P){
kk[kx].push_back(l);
put = false;
}
kx++;
if(kx>=K){
kx=0;
}
}while(put);
}

int64 minpress = 0;

Rep(i, K){
Rep(ix, kk[i].size()){
minpress += ( (kk[i][ix]) * (ix+1) );
}
}

cout << "Case #" << test << ": " << minpress << endl;
}

exit(0);
}


and this is the C++ solution that I came up after few hours of the contest.

//
typedef long long int64;

#define For(i,a,b) for (int i(a),_b(b); i <= _b; ++i)
#define Rep(i,n) for (int i(0),_n(n); i < _n; ++i)

int main() {

freopen("in.in", "rt", stdin);
freopen("out.out", "wt", stdout);

int t;
cin >> t;
For(test, 1, t) {

int P,K,L;
cin >> P >> K >> L;

int64 letters[L];

Rep(i, L){
cin >> letters[i];
}

sort(AllA(letters,L));

int64 minpress = 0;
int store = 1;
Rep(i, L){
if(store>P)
store = 1;

int64 l = letters[(L-i)-1];
minpress += l * store;

if( (i+1)%K == 0)
store++;
}

cout << "Case #" << test << ": " << minpress << endl;
}

exit(0);
}

First solution is useless! and the second solution is far better than the first one. And both solutions provide the same output for the given input values. But I just couldn't code the easy and simple second solution during the contest. Why does it take too long.. ?

2 comments:

josua M said...

can you explain what is "Google Code Jam Online" that you are trying to solve here ???

Lahiru said...

Ah.. I'm talking about a question at Google Codejam, Online Round - 1. :)

http://code.google.com/codejam/contest/

Post a Comment