UVA: 10142 Programming Challenges (Skiena & Revilla) Volume-1

UVA: 10142 : Australian Voting

Background- Here we need to come-up with the solution for Australian Voting system, some kind of majority algorithm. More on the problem description visit  UVA: 10142 : Australian Voting . I tried to implement this but discovered that there is ambiguity in the problem description and the test data, causing wrong answer on submission. It is not clear whether we should keep or remove the invalid vote having duplicate choices when I generated the output from http://uvatoolkit.com/ for this problem, surprisingly it was taking invalid votes also into consideration. Therefore I left this problem and not working further on this. Anyway my unoptimized and first attempt is for your scrutiny   

C++ Implementation -

#include <iostream>
#include <map>
#include <bitset>
#include <vector>
#include <string>
#include <sstream>
#include <iterator>
#include <algorithm>
#include <functional>
#include <utility>
#include <cctype>
#include <cstdlib>
#include <stdio.h>

using namespace std;
typedef vector<short> vectorshort;

#define _SKIP_LINE_ do{scanf("%*[^\n]"); getc(stdin);}while(0)

void Hash(const vector<vectorshort>& in, map<short, vectorshort>& out) {
    for(short i=0; i < in.size(); ++i) 
        out[in[i][0]].push_back(i);
    
}

void Majority(short size, const map<short, vectorshort>& out, vector<short>&winner, vector<short>& eliminate) {
    map<short,vectorshort>::const_iterator it = out.begin();
    short min = it->second.size();
    short maj = it->first;    
    short max = min;
    eliminate.push_back(maj);
    while(++it != out.end()) {
        if(min > it->second.size()) {
            eliminate.clear();
            eliminate.push_back(it->first);
            min = it->second.size();
        } else if(min == it->second.size()) {
            eliminate.push_back(it->first);
        }
        if(max < it->second.size()) {
            max = it->second.size();
            maj = it->first;
        }
    }
    double ratio = (double)((max * 1.0) / double(size))*100.0;
    if(size == out.size() * out.find(eliminate.front())->second.size()) winner = eliminate;
    else if(ratio > (double)50.0) winner.push_back(maj);
    return;
}

void Majority(const vector<vectorshort>& in, map<short, vectorshort>& out, vector<short>&winner, vector<short>& eliminate) {
    Hash(in, out);
    // Get eliminations
    map<short,vectorshort>::iterator it = out.begin();
    short min = it->second.size();
    short maj = it->first;    
    short max = min;
    eliminate.push_back(maj);
    while(++it != out.end()) {
        if(min > it->second.size()) {
            eliminate.clear();
            eliminate.push_back(it->first);
            min = it->second.size();
        } else if(min == it->second.size()) {
            eliminate.push_back(it->first);
        }
        if(max < it->second.size()) {
            max = it->second.size();
            maj = it->first;
        }
    }
    double ratio = (double)((max * 1.0) / double(in.size()))*100.0;
    if(in.size() == out.size() * out[eliminate.front()].size()) winner = eliminate;
    else if(ratio > (double)50.0) winner.push_back(maj);
    return;
}

void Contest(vector<vectorshort>& ballots, vector<short>& winner) {
    map<short, vectorshort> hash;
    vector<short> elimination;
    map<short, short> rotation_count;
    Majority(ballots, hash, winner, elimination);
    while(true) {
        if(winner.size() > 0) break;
        else {
            vector<short>::iterator it = elimination.begin();
            while(it != elimination.end()) {
                vector<short>::iterator indexes = hash[(*it)].begin();
                while(indexes != hash[(*it)].end()) {
                    if(rotation_count[*indexes] >= ballots[*indexes].size()) { 
                        winner.clear();
                        return;
                    }
                    rotation_count[*indexes] += 1;    
                    rotate(ballots[*indexes].begin(), ballots[*indexes].begin()+1, ballots[*indexes].end());
                    // update hash
                    hash[ballots[*indexes][0]].push_back(*indexes);
                    indexes++;
                }
                hash.erase(*it);
                it++;
            }
        }
        winner.clear();
        elimination.clear();
        Majority(ballots.size(), hash, winner, elimination);
    }
    return;
}

int main() {
    unsigned short nCases = 0;
    unsigned short nCandidate = 0;
    string line;
    vector<string> names;
    vector<vectorshort> ballots;
    vector<short> choices;
    bitset<32> uChoices;
    cin >> nCases;
    stringstream tokens(stringstream::in | stringstream::out);
    while(nCases-- > 0 && cin.eof() != true) {
        cin >> nCandidate;
        _SKIP_LINE_;
        names.clear();
        names.resize(nCandidate);
        for(short i =0; i < nCandidate; ++i) {
            getline(cin, names[i]);
#ifndef ONLINE_JUDGE
            names[i] = names[i].substr(0, names[i].size()-1);
#endif
        }
        
        ballots.clear();
        while(cin.eof() == false) {
            getline(cin, line);
#ifndef ONLINE_JUDGE
            if(line.find_first_not_of(" \r\t") == string::npos) break;
#else
            if(line.find_first_not_of(" ") == string::npos) break;
#endif
            tokens.clear();
            tokens << line;
            choices.resize(nCandidate, 0);
            uChoices.reset();
            bool skip = false;
            for( short i =0; i < nCandidate; ++i) {
                tokens >> choices[i];
                choices[i] -= 1;
                if(choices[i] < 0 || choices[i] >= nCandidate || uChoices.test(choices[i]) == true) { 
                    skip = true;
                    break;
                }
                uChoices.set(choices[i]);
            }
            if(skip == false) ballots.push_back(choices);
        }

        vector<short> winner;
        if(ballots.size() > 0) Contest(ballots, winner);
        if(winner.size() > 0) 
            for(short i =0; i < winner.size(); i++)
                cout << names[winner[i]] << endl;
        else copy(names.begin(), names.end(), ostream_iterator<string>(cout, "\n"));

        if(nCases > 0) cout << endl;
    }
    return 0;    
}

Afterthoughts  -

1. There is plenty of scope for optimization but I am struggling to get the solution accepted.

2. It is unsolved, giving wrong answer on submission 

If you know the problem with this implementation, Please do share