Thread: ACM Programming Contest.... Seeking Answers!

  1. #1
    young grasshopper jwroblewski44's Avatar
    Join Date
    May 2012
    Location
    Where the sidewalk ends
    Posts
    294

    ACM Programming Contest.... Seeking Answers!

    Hello, all!

    First off, this is program from the ACM programming contest, of which today I and two teammates competed. We managed to solve two of nine correctly, but sadly the two programs I was responsible for were never accepted.

    I am hoping that someone here can help me understand what I overlooked. Don't worry, the contest is over, so you are not helping me cheat. We had no access to the internet during the contest.

    The program I will focus on in this thread is as follows:

    Rank Order

    Your team has been retained by the director of a competition who supervises a panel of judges. The competition asks the judges to assign integer scores to competitors -- the higher the score, the better. Although the event has standards for what score values mean, each judge is likely to interpret those standards differently. A score of 100, say, may mean different things to different judges.

    The director's main objective is to determine which competitors should receive prizes for the top positions. Although absolute scores may differ from judge to judge, the director realizes that relative rankings provide the needed information -- if two judges rank the some competitors first, second, third, ... then they agree on who should receive the prizes.

    Your team is to write a program to assist the director by comparing the scores of pairs of judges. The program is to read two lists of integer scores in competitor order and determine the highest ranking place (first place being highest) at which the judges disagree.

    Input

    Input to your program will be a series of score list pairs. Each pair begins with a single integer giving the number of competitors N, 1 < N < 1,000,000. The next N integers are the scores from the first judge in competitor order. The are followed by the second judge's scores -- N more integers, also in competitor order. Scores are in the range 0 to 100,000,000 inclusive. Judges are not allowed to give ties, so each judge's scores will be unique. Values are separated from each other by one or more spaces and/or newlines. The last score list pair is followed by the end-of-file indicator.

    Output

    For each score pair, print a line with the integer representing the highest-ranking place at which the judges do not agree. If the judges agree on ever place, print a line containing only the word 'agree'. Use the format below: "Case", one space, the case number, a colon and one space, and the answer for that case with no trailing spaces.

    Sample Input

    4
    3 8 6 2
    15 37 17 3
    8
    80 60 40 20 10 30 50 70
    160 100 120 80 20 60 90 135

    Sample Output

    Case 1: agree
    Case 2: 3


    The following is (roughly, I'm retyping now my memory):

    Code:
    #include <iostream>
    
    
    using namespace std;
    
    
    struct contestant
    {
       int score,
           cont_num;
    };
    
    
    void swap( contestant a[], int i, int j );
    void qsort( contestant a[], int left, int right );
    
    
    int num_of_conts;
    int case_num = 1;
    
    
    int main(){
    
    
       cin >> num_of_conts;
    
    
       while( cin )
       {
          contestant * judge1 = new contestant[num_of_conts];  // list for each judges scores
          contestant * judge2 = new contestant[num_of_conts];  // same index means same contestant, just score from diff judge
    
    
          for( int i = 0; i < num_of_conts; i++ )
          {
             cin >> judge1[i].score;
             judge1[i].cont_num = i;
          }
    
    
          for( int i = 0; i < num_of_conts; i++ )
          {
             cin >> judge2[i].score;
             judge2[i].cont_num = i;
          }
    
    
          // sort both arrays of contestants by score, from lowest score to highest
          qsort( judge1, 0, num_of_conts - 1 );
          qsort( judge2, 0, num_of_conts - 1 );
    
    
          int i;
          for( i = num_of_conts - 1; i >= 0; i-- )
             if( judge1[i].cont_num != judge2[i].cont_num )
                break;
          cout << "Case " << case_num++ << ": ";
          if( i == -1 )
             cout << "agree" << endl;
          else
             cout << num_of_conts - i << endl;
    
    
          delete [] judge1;
          delete [] judge2;
    
    
          cin >> num_of_conts;
       }
    
    
       return 0;
    }
    
    
    void swap( contestant a[], int i, int j )
    {
       contestant temp = a[i];
       a[i] = a[j];
       a[j] = temp;
    }
    
    
    void qsort( contestant a[], int left, int right )
    {
       int i, last;
    
    
       if( left >= right )
          return;
    
    
       swap( a, left, ( left + right ) / 2 );
       last = left;
       for( i = left + 1; i <= right; i++ )
          if( a[i].score < a[left].score )
             swap( a, ++last, i );
       swap( a, left, last );
       qsort( a, left, last - 1 );
       qsort( a, last + 1, right );
    }
    The logic is fairly simple:
    *chug in the scores
    *sort contestants based on scores
    *iterate along the list of contestants, from best to worst, breaking on
    mismatch

    The judges never accepted any iteration of this code. All I could think of doing was switching most/all the ints to long and then long longs in case of any overflows.

    Any thoughts on why it was never accepted?
    Last edited by jwroblewski44; 11-08-2014 at 08:03 PM.
    "Simplicity is the ultimate sophistication." - Leonardo da Vinci

  2. #2
    Registered User
    Join Date
    May 2009
    Posts
    3,772
    Did you ever try NOT using "using namespace std;" I am thinking a name collision issue on swap or qsort.
    No idea if it is likely or not; I am a C programmer who from time to time tries to learn C++.

    Tim S.
    "...a computer is a stupid machine with the ability to do incredibly smart things, while computer programmers are smart people with the ability to do incredibly stupid things. They are,in short, a perfect match.." Bill Bryson

  3. #3
    Registered User
    Join Date
    Jun 2005
    Posts
    6,815
    The problem is that the exercise required you to compare rankings that each judge gives each contestant. Your approach doesn't do that.


    Even with that, your code is a hybrid of C and C++. Even if the judges are unfussed by what language you use, using a hybrid of two is not good form.
    Right 98% of the time, and don't care about the other 3%.

    If I seem grumpy or unhelpful in reply to you, or tell you you need to demonstrate more effort before you can expect help, it is likely you deserve it. Suck it up, Buttercup, and read this, this, and this before posting again.

  4. #4
    young grasshopper jwroblewski44's Avatar
    Join Date
    May 2012
    Location
    Where the sidewalk ends
    Posts
    294
    @grumpy

    If you could be more specific as to how I'm failing to do what the program asked.

    From the last paragraph of the description:
    "Your team is to write a program to assist the director by comparing the scores of pairs of judges. The program is to read two lists of integer scores in competitor order and determine the highest ranking place (first place being highest) at which the judges disagree."

    I read in the scores, while giving each person an id. Then once they are sorted based on score, I start with the highest ranked contestant (far end of the arrays). If the have the same id, the same contestant received the same ranking. I progress on until the end of array or a mismatch is found, then printed.

    What am I missing?

    Also, when you say I'm using a mix of C and C++, what are you exactly referring to? As in, what is C in the source that would not be considered C++?

    EDIT:
    Also, you do realize that my programs output matches that of the sample output for the given sample input? Is this just a coincidence?
    Last edited by jwroblewski44; 11-08-2014 at 09:20 PM.
    "Simplicity is the ultimate sophistication." - Leonardo da Vinci

  5. #5
    Registered User
    Join Date
    Jun 2005
    Posts
    6,815
    Quote Originally Posted by jwroblewski44 View Post
    From the last paragraph of the description:
    "[COLOR=#333333]Your team is to write a program to assist the director by comparing the scores of pairs of judges. The program is to read two lists of integer scores in competitor order and determine the highest ranking place (first place being highest) at which the judges disagree."
    The approach you described is sorting contestants by scores. That is different from checking if judges ordered contestants in the same way.

    Quote Originally Posted by jwroblewski44 View Post
    Also, when you say I'm using a mix of C and C++, what are you exactly referring to? As in, what is C in the source that would not be considered C++?
    Depends on your definition of C++. From a "C++ as a sort-of superset of C" perspective, your code might be said to quality. From a "using idiomatic C++" perspective it does not.

    Expert judges will look for idiomatic code in whatever programming language is used - it shows technical discipline by the author of that code.

    The point of idioms in any programming language is using facilities of that language and its library effectively, without having to roll your own. Idiomatic code tends to be smaller (since it uses facilities that are provided by the language AND its standard library), easier to get right (reusing something that is specified in a standard is less error prone than writing new code to do the same thing).

    Idiomatic C++ very rarely makes use of pointers, at least not directly. It also makes more use of - or extends if needed - facilities in the standard library. Your usage of pointers, the usage of new/delete to create an array (instead of a standard container), writing a function to do sorting (instead of an appropriate algorithm that works with iterators from a standard container), and writing a swap function are all hallmarks of hybrid C/C++.

    Quote Originally Posted by jwroblewski44 View Post
    Also, you do realize that my programs output matches that of the sample output for the given sample input? Is this just a coincidence?
    Maybe it is. I don't know. I certainly can't exclude that possibility.

    When I saw that your description of approach was not consistent with what was asked for, I didn't bother to examine the code to see if it did something different. I only looked at the code enough to recognise it was not idiomatic C++.

    Producing a given set of outputs from a given set of inputs does not demonstrate you have used the right approach to get there. I've seen lots of software that passes test cases, despite actually using a completely wrong approach.



    All I'm saying is that, given the information you provided, I can understand why the judges did not accept any iteration of your code. If I was a judge (and, no, I wasn't) I would have done the same, for the reasons I explained.
    Last edited by grumpy; 11-09-2014 at 12:14 AM.
    Right 98% of the time, and don't care about the other 3%.

    If I seem grumpy or unhelpful in reply to you, or tell you you need to demonstrate more effort before you can expect help, it is likely you deserve it. Suck it up, Buttercup, and read this, this, and this before posting again.

  6. #6
    Registered User
    Join Date
    Nov 2012
    Posts
    1,393
    Quote Originally Posted by jwroblewski44 View Post
    Also, when you say I'm using a mix of C and C++, what are you exactly referring to? As in, what is C in the source that would not be considered C++?
    To see why it might not be considered "idiomatic C++" it might be instructive to try and change this program to make it a valid C program and see which lines needed to be changed. In your example, only a few trivial changes must be made, such as changing cin/out to scanf/printf, changing new/delete to malloc/free, etc. Also, unless you need to make your own sorting algorithm, why not use the standard library rather than defining your own? C standard library defines qsort and C++ standard library defines std::sort.

  7. #7
    young grasshopper jwroblewski44's Avatar
    Join Date
    May 2012
    Location
    Where the sidewalk ends
    Posts
    294
    Yes. I agree that writing my own sort was not the best approach. Simply, I don't have much experience using the standard system sorts, but I did have access to a book with a sort method I was familiar with. So rather than flail about trying to show my command of the language, I simply used what I knew to accomplish the main objective. Also, I'm a C guy at heart, so it's hard not to stray.

    I can't think of any other way of seeing if judges ranked each contestant relatively the same.... Could you point me in the right direction?
    "Simplicity is the ultimate sophistication." - Leonardo da Vinci

  8. #8
    Ultraviolence Connoisseur
    Join Date
    Mar 2004
    Posts
    555
    I'm learning C++11 here's my attempt at this contest (using your same logic...not sure if they want you to instead normalize scores between each judge...the result is the same though.
    Code:
    #include <iostream>
    #include <string>
    #include <vector>
    #include <set>
    #include <boost/regex.hpp>
     
    struct contestant {
        unsigned long score, cont_num;
        bool operator<(const contestant& b) const { return score < b.score; }
    };
    
    inline bool matches_re(const std::string& s, const std::string& exp)
    {
        boost::regex re;
        try {
            re.assign(exp);
        } catch (const boost::regex_error& e) {
            std::cout << "regex error: " << e.what() << " code: " << e.code() << "\n";
            return false;
        }
        return boost::regex_match(s, re);
    }
    
    inline std::string perform_judgement(unsigned long& contestants, std::vector<std::multiset<contestant>>& judge) 
    {
        unsigned long count;
    
        for (count = 0; count < contestants; ++count) {
            for ( const auto& j : judge ) { // Sorted by scores 
                // Ugly but iterator doesn't support addition apparently grumble..
                auto iter = j.begin();
                for (unsigned long i = 0; iter != j.end() && i < count; ++i) ++iter;
    
                if (iter->cont_num != count) 
                    return std::to_string(count);
            }
        }
        return count == contestants ? "agree" : "0";
    }
     
    int main(void)
    {
        unsigned long contestants = 0;
        unsigned long caseno = 0;
        std::vector<std::multiset<contestant>> judges;
    
        do {
            std::string line;
            const auto& ok = std::getline(std::cin, line);
            std::stringstream ss{line};
    
            if (!ok || matches_re(line, "^\\s*\\d+\\s*"))  {
                /* Report our case results */
                if (contestants) { 
                    std::cout << "Case #" 
                        << ++caseno 
                        << ": " 
                        << perform_judgement(contestants, judges) 
                        << "\n";
                    judges.clear(); // clear judge list for next case
                }
                
                // Received contestant count, install it
                ss >> contestants;
            } else if (matches_re(line, "^\\s*(?:(?:\\d+)\\s?)+")) {
                unsigned long count = 0;
                contestant ct;
                std::multiset<contestant> scores;
    
                // Read contestant scores into sorted order
                // and remember their original number
                while ( count < contestants && ss >> ct.score ) {
                    ct.cont_num = count++;
                    scores.insert((contestant){ct.score, ct.cont_num});
                }
    
                // Add these scores to the judge list
                judges.emplace_back(scores);
            } else {
                std::cerr << "[invalid input]: " << line << "\n";
            }
    
        } while(std::cin);
    
        return 0;
    }

  9. #9
    young grasshopper jwroblewski44's Avatar
    Join Date
    May 2012
    Location
    Where the sidewalk ends
    Posts
    294
    @nonpuz

    I spoke with my department chair(he was a judge during the comp) and he gave me the test cases for the problem. When I have some free time ( thanksgiving break? ), I'm going to check test my program with their test cases and see what I missed. After this, I will test your code and let you know whether or not they would have given your program 'the nod'.
    "Simplicity is the ultimate sophistication." - Leonardo da Vinci

  10. #10
    young grasshopper jwroblewski44's Avatar
    Join Date
    May 2012
    Location
    Where the sidewalk ends
    Posts
    294
    Well once I went through and changed all the int's to long's, the program gave all the correct outputs. The issue was that I neglected to replace the int's used for the counters in the for loops.

    @nonpuz

    when I try to compile your code, my system can't find the "boost/regex.hpp" file.
    "Simplicity is the ultimate sophistication." - Leonardo da Vinci

  11. #11
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    Quote Originally Posted by jwroblewski44 View Post
    when I try to compile your code, my system can't find the "boost/regex.hpp" file.
    That's part of the boost library. You would have to download and install it. Which would not a bad idea certainly, as it's shock full of useful stuff.
    But then again, it might probably be better off just using std::regex instead, allowing you to skip the dependency on boost.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Programming newbie seeking help!
    By jaja009 in forum C Programming
    Replies: 2
    Last Post: 02-19-2010, 12:12 PM
  2. Seeking avice from an expert in programming
    By i_wanna_ in forum C++ Programming
    Replies: 2
    Last Post: 04-08-2005, 01:27 PM
  3. Programming Contest
    By Contest_Master in forum A Brief History of Cprogramming.com
    Replies: 1
    Last Post: 02-22-2003, 01:59 PM
  4. ACM Programming Contest
    By MrWizard in forum A Brief History of Cprogramming.com
    Replies: 2
    Last Post: 10-17-2002, 12:01 AM