That was nice, rank 29-th is most likely my best rank ever in a GCJ round that is not the qualification one.
Preparation
I improved my multithreaded template. It now has much less overhead and uses proper Unix threads.
Problem A - The one with math
It must be a miracle that one ml of paint is good enough to paint exactly π cm2. This makes it so, the amount of paint needed to paint a black ring of larger radius R and smaller radius r is exactly: R2 - r2.
This problem is a constructive one. Do it step by step.
We want to find the maximum value of x such that: t >= costToPaint(x). Where costToPaint(x) is the cost to paint x black rings. The value of x can be very large, but it does not matter, because we can use binary search.
So the new problem is to find a quick way to calculate costToPaint(x), in order to solve the large input, we need o(x) time (Note that this is small-o notation, not big O). Let us look for a O(1) one...
The first black ring needs ( r + 1 )^2 - r^2, the second one needs ( r + 3 )^2 - (r + 2)^2, the third one (r + 5)^2 - (r + 4)^2 and so and so. We need to find the sum for 1 <= i <= x of :
( r + 2*i - 1 )^2 - ( r + 2*i - 2 )^2
Sounds difficult? Not really. Let us get clever and...
(r + 2*i - 1)^2 - ( (r + 2*i - 1) - 1 )^2Then...
= (r + 2*i - 1)^2 - (r + 2*i - 1)^2 + 2*(r + 2*i - 1) - 1 = 2*r + 4*i - 3 = (2*r - 3) + 4*i ... sum(1 <= i <= x, (2*r - 3) + 4*i ) = (2*r - 3)*x + 4*x*(x+1) / 2
So we just need to find (2*r - 3)*x + 2*x*(x+1)
Be careful with overflow... I actually took most of those 40+ minutes being perhaps too careful about it...
long r, t;
// we only need to know if the result of f(x) is greater than t,
// so if we surpass INF, we can just stay there...
long mul(long a, long b)
{
if (a >= INF / b) {
return INF;
}
return a*b;
}
long add(long a, long b)
{
if (a >= INF - b) {
return INF;
}
return a + b;
}
long f(long x)
{
// sum 1 <= i <= x : 2*r + 4*i - 3
// = (2*r - 3)*x + 4*x*(x+1) / 2
// = (2*r - 3)*x + 2*x*(x+1)
// = x * (2*r - 3 + 2*x + 2)
// = x * (2*r - 1 + 2*x) // 2*r is at least 2
return mul(x, add(2*r - 1, 2*x) );
}
long solve()
{
// max x: t >= f(x)
long hi = t + 1, lo = 0;
while (lo + 1 < hi) {
long ha = hi - (hi - lo) / 2;
if ( f(ha) <= t) {
lo = ha;
} else {
hi = ha;
}
}
return lo;
}
Problem C-small the one with guessing
Is GCJ jumping the shark? They seem to be trying unusual stuff too much lately. Ok, it is fun though. It reminds me of IPSC, and IPSC is just the best yearly contest ever.
My approach was to find every possible combination of cards (order does not matter), and find the probability that such setting happens. Then, for each list of products, try each combination of cards and calculate the probability that IF the card combination was picked, the products are those. After doing all that, pick the combination of cards that has the best total probability (Probability to get the combination) * (Probability to get the product). This got correct in the first try.
Problem B - the one with the schedule and energy
I estimated that as long as I solved B-small I would likely advance, so I focused on the easy problem instead of spending time in the large one.
At any point, you have between 0 and E energy, so you can never spend more than E energy in any activity. In the small input, E is at most 5, and the number of activities is at most 10, so brute force for the amount of energy you spend in each activity is good enough. 510 choices in the worst case.
int E, R, N;
int v[10];
int solve()
{
vector<int> spend(N, 0);
int best = 0;
while (true) {
//cout<<"="; for (int i=0; i<N; i++) cout << spend[i]; cout<<endl;
// simulate
int e = E;
int gain = 0;
for (int i = 0; i < N; i++) {
int s = std::min(e, spend[i]);
gain += s * v[i];
// I had min(e, e - s + R) instead of min(E, e - s + R) :(
e = std::min(E, e - s + R);
}
best = std::max(best, gain);
// next choice
int j = N - 1;
while (j>=0) {
spend[j]++;
if (spend[j] > E) {
spend[j] = 0;
j--;
} else {
break;
}
}
if (j < 0) {
break;
}
}
return best;
}
C small 2
After solving that B-small, I wanted to solve more. I could spend my remaining 40+ minutes in B-large, or the harder C-small. C-small-2 has many advantages, it gives more points, and since it is a small input, you will be able to know for sure if you when you got it correct. I also had a sudden idea for C...
It turns out that:
a) My generation of combinations was slow, it is possible to generate the combinations (sorted) directly and then calculate their probabilities.
b) Plenty of combinations are unlikely, you can consider the X combinations with the largest probabilities such that the sum of their probabilities is something large. At first I tried 0.5, but apparently it wasn't large enough. At the end I tried 0.99, ignoring the improbable combinations that add up to 0.01 probability is actually a significant optimization. And this omission will reduce your success rate only by 1%. The success rate has to be about 1/8 in C-small-2.
My first attempt was a time out. It turns out that my approach was not fast enough. I found a way to precalculate the product probabilities for each combination, so that I only needed an O(K) loop per combination per list of products. Second attempt was wrong (0.5 is apparently not good enough). Third attempt: I noticed that 0.99 is good and fast. Correct!
Incidentally, I needed 1.5 minutes to run the final solution. If not for multi threading, I may have needed 5 minutes or more...
int cardProduct[7];
string curr;
double fact[13];
double TOTAL;
set< pair< double, string> > possibility;
set< pair< double, string> > probable;
map<string, map<int, double> > probableProduct;
void rec(int x, char ch)
{
if (x == N) {
// calculate the probability
double p = fact[N];
int i = 0;
while (i < N) {
int j = i;
while ( (j < N) && (curr[j] == curr[i] ) ) {
j++;
}
p /= fact[j - i];
i = j;
}
p /= TOTAL;
possibility.insert( make_pair(p, curr) );
} else {
for (char b = ch; b <= '0' + M; b++) {
curr[x] = b;
rec(x + 1, b);
}
}
}
void init()
{
TOTAL = 1;
for (int i=0; i<N; i++) {
TOTAL *= M - 1;
}
fact[0] = 1;
for (int i=1; i <= 12; i++) {
fact[i] = i * fact[i-1];
}
curr = string(N, '?');
rec(0, '2');
double P = 0.001;
for_each(q, possibility) {
P -= q->first;
if (P < 0) {
probable.insert( make_pair(q->first, q->second));
string x = q->second;
map<int, double> product;
for (int i=0; i<(1<<N); i++) {
int p = 1;
for (int j=0; j<N; j++) {
if (i & (1<<j)) {
p *= x[j] - '0';
}
}
product[p] += p / (double)(1<<N);
}
probableProduct[x] = product;
}
}
}
string solve()
{
pair<double, string> best = make_pair(-1.0, string(N,'2') );
for_each( q, probable) {
string x = q->second; //a combination of cards
double p = q->first; //probability to get those cards
//calculate the probability to get each product
map<int, double> & product = probableProduct[x];
// probability to get all K products
for (int i=0; i<K; i++) {
if ( product.count(cardProduct[i])) {
p *= product[ cardProduct[i] ];
} else {
p = 0;
}
}
best = std::max( best, make_pair(p, x) );
}
return best.second;
}
void read() {
5 comments :
Congrats for good gcj rank!!
was a quite easy round as compared to last year's 1 A
You may be right that the problems were easier than last year. But they were easier for everyone . It was still difficult to get an advancing score, probably harder than last year because there were more contestants.
some stupid question !
which software you use to draw pictures of topcoder problems ?
Inkscape
Post a Comment