Thread: Intercollegiate programming contest problems

Yeah, I was just joking. Anyways, I had a question similar to that a few weeks ago, and wrote it up. After reading the question, mines not exactly what they want, but pretty close. Don't have the time to rewrite it. I'll post my version of it when I get home if you want it, I'm at work now.

Alright, thanks. I think I get it now, more or less. But, why aren't I supposed to use a Mac? WTF is that?!

Macs don't even have a console and we all know that macs were
programmed mostly in pascal.... The main advantage of
the macs is that the terminal emulator is pretty nice.

I can't believe this. They give me a syntax error on this code

Code:

#include <iostream>
using namespace std;

const int NUM_SKILLS         = 6;
const int MAX_SKILL_VAL      = 10;
const int MAX_WARRIORS       = 20;
const int MAX_TOTAL_WARRIORS = MAX_WARRIORS * 2;


double win_probability(int s[][NUM_SKILLS], int i, int j)
{
    int I, J, IP, JP;
    const int MAX_DIFF = 10000;
    double p;
    
    I = J = IP = JP = -MAX_DIFF;

    for (int k = 0; k < NUM_SKILLS; ++k) {
        int ds = s[i][k] - s[j][k];
        if (ds > IP) { 
            IP = ds;
        }

        ds = s[j][k] - s[i][k];
        if (ds > JP)
            JP = ds;
    }

    I = (IP >= 0)? IP : 0;
    J = (JP >= 0)? JP : 0;

    if (I + J == 0)
        p = 0.5;
    else
        p = I / double(I + J);

    return p;
}

void find_probabilites(double P[][MAX_WARRIORS],
                       int s[][NUM_SKILLS], int num_warriors)
{
    for (int i = 0; i < num_warriors; ++i) {
        for (int j = 0; j < num_warriors; ++j) {
            P[i][j] = win_probability(s, i, num_warriors + j);
        }
    }
}


void find_max_expected(double P[][MAX_WARRIORS], int T[], int num_warriors)
{
    double best_val = -10000.0;
    int nperm = 0;
    int n = 0;
    for (int i = 0; i < num_warriors; ++i)
        T[i] = i;

    while(next_permutation(&T[0], &T[num_warriors])) {
        double e = 0.0;
        for (int i = 0; i < num_warriors; ++i)
            e += P[i][T[i]];
        if (e > best_val) {
            best_val = e;
            nperm = n;
        }

        n++;
    }

    next_permutation(&T[0], &T[num_warriors]);    // back to orig
    for (int i = 0; i < nperm; ++i) {
        next_permutation(&T[0], &T[num_warriors]);
    }
}

int main(void)
{
    int s[MAX_TOTAL_WARRIORS][NUM_SKILLS];
    double P[MAX_WARRIORS][MAX_WARRIORS];
    int T[MAX_WARRIORS];
    bool quit = false;
    int num_warriors = 0;
    int instance = 0;
    
    while(!quit) {
        cin >> num_warriors;
        if (num_warriors < 0 || num_warriors > MAX_WARRIORS) {
            cerr << "Invalid number of warriors\n";
            exit(-1);
        } else if (num_warriors == 0) {
            quit = true;
        } else {
            for (int i = 0; i < num_warriors * 2; ++i) {
                for (int k = 0; k < NUM_SKILLS; ++k) {
                    if (!cin) {
                        cerr << "Invalid datafile\n";
                        exit(-1);
                    } else {
                        int n;
                        cin >> n;
                        if (n >= 0 && n <= MAX_SKILL_VAL)
                            s[i][k] = n;
                        else {
                            cerr << "Invalid datafile\n";
                            exit(-1);
                        }
                    }
                }
            }

            find_probabilites(P, s, num_warriors);
            find_max_expected(P, T, num_warriors);

            cout << "Instance " << ++instance << ": ";
            for (int i = 0; i < num_warriors; ++i) {
                cout << (T[i] + 1) << " ";
            }
            cout << endl;
        }
    }
    

    return 0;
}

This problem is harder than I thought since if
there 20 warriors it will try all 20! possible matches.