Intercollegiate programming contest problems

This is a discussion on Intercollegiate programming contest problems within the A Brief History of Cprogramming.com forums, part of the Community Boards category; Alright, thanks. I think I get it now, more or less. But, why aren't I supposed to use a Mac? ...

  1. #16
    Senior Member joshdick's Avatar
    Join Date
    Nov 2002
    Location
    Phildelphia, PA
    Posts
    1,146
    Alright, thanks. I think I get it now, more or less. But, why aren't I supposed to use a Mac? WTF is that?!

    Oh, and I don't care so much about being able to win a contest as I am completing a personal challenge.
    FAQ

    "The computer programmer is a creator of universes for which he alone is responsible. Universes of virtually unlimited complexity can be created in the form of computer programs." -- Joseph Weizenbaum.

    "If you cannot grok the overall structure of a program while taking a shower, you are not ready to code it." -- Richard Pattis.

  2. #17
    terrance11
    Guest

    Smile

    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.

  3. #18
    Senior Member joshdick's Avatar
    Join Date
    Nov 2002
    Location
    Phildelphia, PA
    Posts
    1,146
    Thanks for the offer, Terrance, but I'd like to code it out myself. That is, if I ever have the time
    FAQ

    "The computer programmer is a creator of universes for which he alone is responsible. Universes of virtually unlimited complexity can be created in the form of computer programs." -- Joseph Weizenbaum.

    "If you cannot grok the overall structure of a program while taking a shower, you are not ready to code it." -- Richard Pattis.

  4. #19
    Blank
    Join Date
    Aug 2001
    Posts
    1,034
    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.

  5. #20
    Blank
    Join Date
    Aug 2001
    Posts
    1,034
    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;
    }

  6. #21
    Blank
    Join Date
    Aug 2001
    Posts
    1,034
    This problem is harder than I thought since if
    there 20 warriors it will try all 20! possible matches.

Page 2 of 2 FirstFirst 12
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. New Monthly Contest!
    By PJYelton in forum Contests Board
    Replies: 50
    Last Post: 03-22-2005, 08:27 PM
  2. contest problems on my site
    By DavidP in forum Contests Board
    Replies: 4
    Last Post: 01-10-2004, 09:19 PM
  3. WANTED: Contest Master
    By kermi3 in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-23-2003, 10:15 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21