Monday, July 28, 2008

Why too late ?

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

--------------------------------------------------------------------------------
   "So do all who live to see such times. But that is not for them to decide.
   All we have to decide is what to do with the time that is given to us."
						- Gandalf. ~Lord of the rings.
--------------------------------------------------------------------------------