10142 - Australian Voting

2er0 · Post by **2er0** » Thu Sep 28, 2006 2:26 am

when i compile and run, what am i suppose to input?
or am i suppose to have a resource file or something?

Jan Ken · Post by **Jan Ken** » Mon Nov 20, 2006 2:15 am

I got this codes accept to PC, but I keep geting WA here, can anyone help me ?
source is java:

import java.io.InputStream;
import java.io.IOException;
import java.util.StringTokenizer;

final class MyBufferedReader {
    private InputStream in;

    public MyBufferedReader (InputStream in) {
        this.in = in;}

    public String readLine () throws IOException {
        final StringBuffer sb = new StringBuffer(80);
        int                i  = 0;
        while (((i = in.read()) != '\n') && (i != -1))
            if (i != '\r')
                sb.append((char) i);
        if (i == -1)
            return null;
        return sb.toString();}}


final class Main {
	
	static int [][] ballot;
	static int max;
	static int min;
	static int casenum;
	static int numvoters;
	static String card;
	static int x;
	static int y;
	static boolean end;
	static boolean firstround;
	static int temp;
	
	static String [] candidatesnam;
	
	static int[] votecount;
	static int cannum; 
private static final MyBufferedReader in = new MyBufferedReader(System.in);
	
	
	
	public static void main (String[] args) 
	{ 
		
		

		
		
			try {casenum = Integer.parseInt(in.readLine());}
             catch (IOException e){}
            try {in.readLine();}
             catch (IOException e){}
		     ballot = new int[1000][21];
             candidatesnam  = new String [21];            
		while(casenum > 0)
		{
			firstround = true;
			max =0; min = 1000;
			try {StringTokenizer st = new StringTokenizer(in.readLine());
			    cannum = Integer.parseInt(st.nextToken());
			}
			catch (IOException e) {
            }
			
            
        
        temp = cannum+1;
        votecount = new int [temp];
		
			
		
         
		
		 for(int z =1;  z<=cannum;++z )
		 {
			 try {candidatesnam[z] = in.readLine();}
	        catch (IOException e) {}
			
		 }
	     
		 
		 
		 y = 0;
		 end = false;		 
		 card = "";
		 numvoters =0; 
		 try {card = in.readLine();}
	        catch (IOException e) {end = true;}
	        if(card == null||card.length() == 0)
	        {end = true;}
	         if(!end)
	         {
		 while ( !end)
			{
			 ++numvoters; 
			 StringTokenizer st = new StringTokenizer(card);
		         for(int z = 1; z <=cannum;++z )
				{ballot[y][z] = Integer.parseInt(st.nextToken());
				
				ballot[y][0]= 1;
				}
		     
			    ++y;
			    
			    try {card = in.readLine();}
			        catch (IOException e) {
			            end = true;}
			        if(card == null||card.length() == 0)
			        {end = true;}
			        
			    
			}		
		
		 while(eval())		 	{
			 firstround = false;}
		
		 }
	         else{ 
	        	 for(int z = 1; z < cannum+1;z++)
				  {	
				 System.out.println(candidatesnam[z]);
				  }
	        	 
	             }  
	         if(casenum > 1)
			{
		
			}
		 -- casenum; 
		
			
		}
		
		
		
		
	}
	
	public static boolean eval()
	{ 
	 

	    y =0;
	   
		while( y<numvoters)
		   {
			if (firstround)
			{
				++votecount[ballot[y][1] ];
				
			}
			
		else if( votecount[ballot[y][ballot[y][0]]]<0)
		    {
		     while(votecount[ballot[y][ballot[y][0]]]<0)
		      {++ballot[y][0];
			  }
		       ++votecount[ballot[y][ballot[y][0]] ];
		    }
			 
			 ++y;
		    }
	
		
		 min = 1000;
			for(int z = 1; z<= cannum;z++)
			{
				if( votecount[z] > max)
				max = votecount[z];
			if((votecount[z]<min) && (votecount[z]!= -1))
				min = votecount[z];
				
				
			}
	
			
	
			
			if(max>numvoters/2)
			{y = 0;
					while(votecount[y] != max)
					{++y;}
					System.out.println(candidatesnam[y]);
					return false;
				}
			else if (max == min)
				{ for(int z = 1; z < (cannum+1);z++)
					{
					  if(votecount[z] == max)
						  System.out.println(candidatesnam[z]);
					}			
			  return false;
		     }
	  
	 
	
	 for(int z = 0; z < votecount.length;z++)
	 {
		 if(votecount[z] == min)
			 votecount[z] = -1;
	 }
	 
    return true;
	}
	
	
}

luison9999 · Post by **luison9999** » Tue Nov 28, 2006 7:02 pm

I got runtime error in 10142, but my arrays are of correct sizes.
Any idea?

Code: Select all

//10142
#include <stdio.h>
#include <string.h>

char nombre[30][100];
int voto[2000][30];
int votos[30];
bool eliminado[30];
int p[30];

int main(){
	int i, j, k, r;
	int N, V, e;
	int casos;
	for(scanf("%d", &casos);casos--; ){
		scanf("%d", &N);
		for(i=1;i<=N;i++){
			scanf("\n%[^\n]", nombre[i]);
		}
		memset(p, 0, sizeof(p));
		memset(votos, 0, sizeof(votos));
		memset(eliminado, 0, sizeof(eliminado));
		for(i=1; ;i++){
			j=getchar();
			j=getchar();
			if(j=='\n' || j==EOF || i>1000)
				break;
			ungetc(j, stdin);
			for(j=0;j<N;j++)
				scanf("%d", &voto[i][j]);
			scanf("%*[^\n]");
		}
		V=i;
		V--;
		for(i=0, e=0;i<N && e<N;i++){
			memset(votos, 0, sizeof(votos));
			for(j=1;j<=V;j++){
				while(eliminado[voto[j][p[j]]])
					p[j]++;
				votos[voto[j][p[j]]]++;
			}
			for(j=1, r=0, k=(1<<30);j<=N;j++)
			if(!eliminado[j]){
				if(votos[j]>V/2){
					printf("%s\n", nombre[j]);
					goto a;
				}
				k<?=votos[j];
				r>?=votos[j];
			}
			for(j=1;j<=N;j++)
				if(votos[j]==k){
					eliminado[j]=true;
					e++;
				}
		}
		a:
		if(i==N || e==N)
			for(i=1;i<=N;i++)
				if(votos[i]==r)
					printf("%s\n", nombre[i]);
		if(casos>0)
			printf("\n");
	}
}

chaturvedi · Post by **chaturvedi** » Tue Dec 19, 2006 9:12 am

Please check for some test case on the following link:
http://online-judge.uva.es/board/viewto ... 9650#49650

Hope this helps you

chaturvedi · Post by **chaturvedi** » Tue Dec 19, 2006 10:57 am

Hi,
I am getting RTE(signal 11) as the verdict of my program... I have read posts regarding the test cases and then corrected my program so that it gives the right output for more than one space between nos... I have tested for all the test data posted.. It gives the correct out.. I am a newbie so please help me with it...Here is my code

Code: Select all

#include<string.h>
#include<stdio.h>
struct details
   {
   char name[4000];
   int novotes;
   }elements[200];
void remove_leading(char *s);
void token(char *s, int re);   
void count (int b,int n);
void initial(int n);
void initial1(int n);
int maxmin(int n,char *maxname,int *min);
void eliminate(int min,int n);
void rem_end(char *s);
void print(int);
int a[50000][1000];
main()
   {
   int t,n,i,j,senti=0,max,min,k;
   char *maxname;
   char str1[10000];
   scanf("%d",&t);
   
      
   for(k=1;k<=t;k++)
      {
      senti=0;
      scanf("%d",&n);
      getchar();
      for(j=1;j<=n;j++)
      {
      gets(elements[j].name);
      remove_leading(elements[j].name);
      rem_end(elements[j].name);
      }


      initial1(n);
      i=1;j=1;
      a[1][1]=1;

      while(gets(str1))
         {
         if(strcmp(str1,"")==0)
         break;
         token(str1,i);
         i++;
         }
      
      while(senti==0)
         {
         count(i-1,n);
         max=maxmin(n,maxname,&min);

         
         if(max==min)
            {
            senti=1;
            print(n);
            }


         if(((float)max)>((float)((i-1)/2)) && senti==0)
            {
            puts(maxname);
            senti=1;
            }

         if(((float)max)<=((float)((i-1)/2)) && senti==0)
         {
         eliminate(min,n);
         initial(n);
         }
         }
      printf("\n\n");
      }
   }

void count(int b,int n)
   {
   int i,j;
   for(i=1;i<=b;i++)
      {
      for(j=1;j<=n;j++)
         {
         if(elements[a[i][j]].novotes!=-1)
            {
            elements[a[i][j]].novotes++;
            break;
            }
         }
      }
   }

int maxmin(int n,char *maxname,int *min)
   {
   int j,i,max=0;
   *min=5000;

   for(i=1;i<=n;i++)
      {
      if(elements[i].novotes>max)
      {
      max=elements[i].novotes;
      j=i;
      }

      if(elements[i].novotes<*min && elements[i].novotes!=-1)
      *min=elements[i].novotes;
      }
   strcpy(maxname,elements[j].name);
   return max;
   }

void print(int n)
   {
   int i;
   for(i=1;i<=n;i++)
      {
      if(elements[i].novotes!=-1)
      {
      if(i==1)
      puts(elements[i].name);
      else
      puts(elements[i].name);
      }
      }


   }

void initial(int n)
   {
   int i;
   for(i=1;i<=n;i++)
      {
      if(elements[i].novotes!=-1)
      elements[i].novotes=0;
      }
   }
void initial1(int n)
   {
   int i;
   for(i=1;i<=n;i++)
      {

      elements[i].novotes=0;
      }
   }

void eliminate(int min,int n)
   {
   int i;
   for(i=1;i<=n;i++)
      {
      if(min==elements[i].novotes)
      elements[i].novotes=-1;
      }
   }

void token(char *s, int re)
{
   int i,j=0,n=1;
   char str[50000],*temp;
   temp=s;
   
   while(strlen(s)!=0)
   {
      for(i=0;s[i]!=' '&&s[i]!='\0';i++);
      
      temp=s;   
      strncpy(str,s,i);
      
      str[i]='\0';
      
      remove_leading(s);
      remove_leading(str);
      rem_end(s);
      rem_end(str);
      temp=temp+i;
      strcpy(s,temp);
      
      
      remove_leading(s);
      
      remove_leading(str);
      
      rem_end(s);
      
      
      rem_end(str);
      
      a[re][n]=atoi(str);
      
      n++;
      
   }

}

void remove_leading(char *s)
{
   char *temp;
   int i;
   if(strlen(s)==0)
   return;
   temp=s;
   for(i=0;s[i]==' ';i++);
   temp=temp+i;
   strcpy(s,temp);

}
void rem_end(char *s)
{
   char *temp=s;
   int i;
   if(strlen(s)==0)
   return;
   for(i=(strlen(s)-1);s[i]==' ';i--);
   strncpy(s,temp,i);
   s[i+1]='\0';

}

helloneo · Post by **helloneo** » Tue Dec 19, 2006 11:11 am

blodstone · Post by **blodstone** » Wed Jan 10, 2007 5:10 pm

Hai guys!
I got TLE for this problem. What's wrong with it? Can somebody help me?

Code: Select all

#include <iostream>
#include <cstdio>
#include <list>
#include <vector>
#include <deque>
#include <algorithm>
#include <string>
#include <cctype>
#include <sstream>
#include <cstdlib>
using namespace std;

struct val{
	int value;
	int pos;
};
bool minFunc(val a, val b){
	return a.value<b.value;
}
void process(vector<deque<int> > ballot, vector<string> candidate){
	if(ballot.size()==0){
		for(int i=0;i<candidate.size();i++){
			cout<< candidate[i]<< endl;
		}
	}else{
		vector<val> count,countBuff;
		vector<vector<val>::iterator > pos;
		vector<bool> lose;
		for(int i=0;i<candidate.size();i++)
			lose.push_back(true);
		int total=0;
		val t;
		for(int i=0;i<candidate.size();i++){
			t.pos=i+1;
			t.value=0;
			count.push_back(t);
		}

		for(int i=0;i<ballot.size();i++){
			count[ballot[i][0]-1].value++;
			total++;
		}
		bool found = false;
		int maxEl=count[0].value,minEl=count[0].value;
		for(int i=1;i<count.size();i++){
			if(maxEl<count[i].value)
				maxEl=count[i].value;
			if(minEl>count[i].value)
				minEl=count[i].value;
		}
		while(!found){
			if(maxEl>total/2 || maxEl==minEl){
				found =true;
				for(vector<val>::iterator i=count.begin();i!=count.end();++i){
					val t2 = *i;
					if(t2.value==maxEl){
						cout << candidate[t2.pos-1] << endl;
					}
				}
				break;
			}else{
				minEl = count[0].value;
				for(int i=1;i<count.size();i++){
					if(minEl>count[i].value)
						minEl=count[i].value;
				}
				pos.clear();
				for(vector<val>::iterator i=count.begin();i!=count.end();++i){
					val t2 = *i;
					if(t2.value==minEl){
						lose[t2.pos-1]=false;
					}else
						countBuff.push_back(*i);
				}
				count = countBuff;
				countBuff.clear();
				pos.clear();
				for(int j=0;j<ballot.size();j++){
					while(!lose[ballot[j][0]-1]){
						ballot[j].pop_front();
						for(int k=0;k<count.size();k++){
							if(ballot[j].front()==count[k].pos && lose[ballot[j].front()-1]){
								count[k].value++;
								break;
							}
						}
					}
				}

				if(count.size()>0){
					maxEl=count[0].value;
					minEl=count[0].value;
				}
				for(int i=1;i<count.size();i++){
					if(maxEl<count[i].value)
						maxEl=count[i].value;
					if(minEl>count[i].value)
						minEl=count[i].value;
				}
			}
		}
	}
}
int main(){
	//freopen("input.in","r",stdin);
	//freopen("output.out","w",stdout);
	int n;
	vector<string> candidate;
	cin >> n;
	string buff;
	vector<deque<int> > ballot;
	deque<int> temp;
	getline(cin,buff);
	int x;
	while(true){
		cin >> x;
		getline(cin,buff);
		//Input Candidate name
		for(int i=0;i<x;i++){
			getline(cin,buff);
			candidate.push_back(buff);
		}
		//Input Ballot
		while(true){
			if(feof(stdin))break;
			getline(cin,buff);
			if(buff=="") break;
			istringstream is(buff);
			int buff2;
			temp.clear();
			while(is>>buff2){
				temp.push_back(buff2);
			}
			ballot.push_back(temp);
			if(feof(stdin)) break;
		}
		process(ballot,candidate);
		cout << endl;
		candidate.clear();
		ballot.clear();
		if(feof(stdin)) break;
	}
	return 0;
}

gfz87 · Post by **gfz87** » Thu Apr 26, 2007 6:23 am

Here is my C++ code, I tried with 20 cases, and it did just fine. Judge says:

Your program has died with signal 11 (SIGSEGV). Meaning:

Invalid memory reference

Before crash, it ran during 0.002 seconds.

Here is my code:

Code: Select all

#include <iostream>
#include <stdio.h>
#include <string.h>

using namespace std;

int main()
{
	int veces, i, j, c, k, m, t, **votos, *votos_c, menor, mayor, mitad;
	char **cand, *no, *tmp;
	bool caso;
	votos = new int *[20];
	tmp = new char[10000];

	cand = new char *[20];
	votos_c = new int[20];
	for (j = 0; j < 20; j++)
	{
		cand[j] = new char[100];
		votos[j] = new int;
	}

	cin >> veces;

	while (veces--)
	{
		cin >> i;
		if (i == 0)
			goto next;

		cin.getline(cand[0], 101);

		while(cand[0][0] == 0)
			cin.getline(cand[0], 101);

		for (j = 1; j < i; j++)
			cin.getline(cand[j], 101);

		for (j = 0; j < 20; j++)
			votos_c[j] = 0;

		cin.getline(tmp, 10001);
		if (tmp[0] == 0)
		{
			caso = 0;
			goto out;
		}
		c = 0;
		while(tmp[0] != 0)
		{
			j = 0;
			no = strtok(tmp, " ");
			sscanf(no, "%d", &votos[c][j++]);
			for (; j < i; j++)
			{
				no = strtok(NULL, " ");
				sscanf(no, "%d", &votos[c][j]);
			}
			cin.getline(tmp, 10001);
			c++;
		}

		while (1)
		{
			for (j = 0; j < 20; j++)
			{
				if (votos_c[j] != -1)
					votos_c[j] = 0;
			}
			for (j = 0; j < c; j++)
				if (votos[j][0] != (-1))
					votos_c[votos[j][0]-1]++;

			j = 0;
			while (votos_c[j] == -1)
				j++;
			menor = mayor = votos_c[j];

			for (j = 0; j < i; j++)
			{
				if (votos_c[j] != -1)
				{
					if (votos_c[j] < menor)
						menor = votos_c[j];
					if (votos_c[j] > mayor)
						mayor = votos_c[j];
				}
			}

			if (mayor == menor)
			{
				caso = 0;
				goto out;
			}

			mitad = c / 2;

			for (j = 0; j < i; j++)
			{
				if (votos_c[j] > mitad)
				{
					caso = 1;
					goto out;
				}
			}

			for (j = 0; j < i; j++)
			{
				if (votos_c[j] == menor)
				{
					votos_c[j] = -1;
					for(k = 0; k < c; k++)
						for (m = 0; m < i; m++)
							if (m == i-1 && votos[k][m] == j + 1)
								votos[k][m] = -1;
							else if (votos[k][m] == j + 1)
							{
								for (t = m; t < i - 1; t++)
									votos[k][t] = votos[k][t + 1];
								votos[k][t] = -1;
								m--;
							}
				}
			}
		}
out:
		if (caso == 0)
		{
			for (j = 0; j < i; j++)
			{
				if (votos_c[j] != -1)
					cout << cand[j] << endl;
			}
		}
		else
		{
			cout << cand[j] << endl;
		}
next:
		if (veces > 0)
		{
			cout << endl;
		}
	}
}

I tried with is in input:

Code: Select all

20

3
John Doe
Jane Smith
Jane Austen
1 2 3
2 1 3
2 3 1
1 2 3
3 1 2

3
A
B
C

3
A
B
C
1 2 3
2 1 3
3 1 2

3
A
B
C
1 2 3

14
A
B
C
D
E
F
G
H
I
J
K
L
M
N
12 5 11 8 6 13 3 2 10 1 7 9 14 4
8 14 1 13 11 12 5 4 3 10 2 6 7 9
13 12 14 5 7 11 3 10 2 1 9 8 4 6
12 3 7 11 2 10 13 5 9 1 6 14 8 4
11 14 13 1 7 4 2 12 5 3 8 10 9 6
4 3 12 8 5 1 2 7 13 11 10 14 6 9
6 14 3 11 1 5 10 7 13 2 12 4 8 9

6
A
B
C
D
E
F
2 1 6 5 3 4
6 3 2 5 4 1
5 2 6 1 3 4
3 6 1 5 2 4
1 2 4 6 3 5
3 2 5 6 1 4
5 6 2 4 3 1
5 3 1 4 2 6
2 4 5 6 3 1
2 5 3 4 6 1

2
i am jalal
he is Hasan
1    2
2  1


3
L
P
M
1 2   3
1 3 2
2   3 1
2 1 3
1  3 2
2 3  1

6
A
B
C
D
E
F
2 1     6 5 3 4
6 3 2 5 4 1
5   2 6 1 3 4
3 6 1    5 2 4
1  2   4 6   3 5
3 2 5   6 1 4
5 6 2 4 3 1
5 3   1 4 2   6
2 4 5 6   3 1
2   5   3 4 6 1

4
jalal
hasan
bijon
saiket
1 2 3 4
3 1 2 4
1 2      3 4
2 1  3 4
3 1 2 4
4 3        1 3

3
John Doe
Jane Smith
Sirhan Sirhan
1 2 3
2 1 3
2 3 1
1 2 3
3 1 2

3
John Doe
Jane Smith
Sirhan Sirhan
1 2 3
2 1 3
2 3 1
1 2 3
3 1 2

4
jalal
hasan
bijon
saiket
1 2 3 4
2 1 3 4
1 2 3 4
2 1 3 4
3 1 2 4
4 2 1 3

6
A
B
C
D
E
F
2  1 6    5 3 4
6 3  2 5   4 1
5  2   6   1    3 4
3 6  1 5     2 4
1 2  4                   6 3 5
3 2 5 6 1 4
5 6    2 4 3 1
5    3  1         4  2   6
2     4 5 6 3 1
2 5  3 4  6     1

3
L
P
M
1 2 3
1 3 2
2 3 1
2 1 3
1 3 2
2 3 1

4
jalal
hasan
bijon
saiket
1 2 3 4
3 1 2 4
1 2      3 4
2 1  3 4
3 1 2 4
4 3        1 3

3
John Doe
Jane Smith
Sirhan Sirhan
1 2 3
2 1 3
2 3 1
1 2 3
3 1 2

3
John Doe
Jane Smith
Sirhan Sirhan
1 2 3
2 1 3
2 3 1
1 2 3
3 1 2

4
jalal
hasan
bijon
saiket
1 2 3 4
2 1 3 4
1 2 3 4
2 1 3 4
3 1 2 4
4 2 1 3

6
A
B
C
D
E
F
2  1 6    5 3 4
6 3  2 5   4 1
5  2   6   1    3 4
3 6  1 5     2 4
1 2  4                   6 3 5
3 2 5 6 1 4
5 6    2 4 3 1
5    3  1         4  2   6
2     4 5 6 3 1
2 5  3 4  6     1

3
L
P
M
1 2 3
1 3 2
2 3 1
2 1 3
1 3 2
2 3 1

and gives me the output:

Code: Select all

John Doe

A
B
C

A
B
C

A

L

B

i am jalal
he is Hasan

L
P

B

jalal
bijon

John Doe

John Doe

jalal
hasan

B

L
P

jalal
bijon

John Doe

John Doe

jalal
hasan

B

I don't know what I'm doing wrong... I set the char buffers to like 10000 in case that judge inputs my program with a very large vote string... Still it does not work.... To all of you AC people... Please help me out!!!

Greetings

fabiofabris · Post by **fabiofabris** » Mon Oct 15, 2007 5:08 pm

There an error in this loop:
Check the EOF flag and array limits;
Are you using a UNIX-like environment?

while(tmp[0] != 0)
{
j = 0;
no = strtok(tmp, " ");
sscanf(no, "%d", &votos[c][j++]);
for (; j < i; j++)
{
no = strtok(NULL, " ");
sscanf(no, "%d", &votos[c][j]);
}
cin.getline(tmp, 10001);
c++;
}

gfz87 · Post by **gfz87** » Mon Oct 15, 2007 7:54 pm

Hi.. I already finished this problem a long time ago... I don't remember what was the problem, but I think it was something like that.. Thank you for posting anyway

evandrix · Post by **evandrix** » Thu Oct 25, 2007 4:55 pm

EDIT: removed.ACC!!

Darko · Post by **Darko** » Fri Oct 26, 2007 2:22 am

That first case is invalid - read the problem statement.

I didn't read the "discussion" you had for the first input, but for the second one, I really don't see what the problem is. You miss the fact that 4 gets eliminated right away (because there were no first-choice votes for 4), and then, yes, 1 and 6. At that point, you have B with 4 votes and C and E with 3. So C and E get eliminated in the next step and B remains with 10 votes. You reintroduce a few of the eliminated candidates in your last count, which is clearly wrong.

This is not a hard problem, just read the statement a bit more carefully. It was one of the first ones I did - it still had a header with my ID, wrong I/O and stuff like that.

As for one of your questions - say you have 9 candidates, 3 have 3 votes each, rest have 0 votes - you eliminate all of those with 0's in one step, nothing changes, and you have a 3-way tie. (Note that the situation that you describe cannot occur - if there are 10 ballots, you cannot have 3 tied and 7 0's)

roman_10 · Post by **roman_10** » Tue Dec 11, 2007 10:28 am

Hi,

I've read all the threads for this problem and tried all the test cases. But I just can't find the bug. Can anybody help me figure it out?

Code: Select all

/*if a candidate is elminated, the choices is updated by set the candidate number to 0*/
#include <iostream>
#include <vector>
#include <string>
#include <cstdlib>
#include <algorithm>
#include <sstream>
#include <cstdio>
#include <cstring>

using namespace std;

string cans[25];	//names of the candidates
int cnts[25];		//number of votes obtained
int ch[1100][25];	//choices
int current_ch[1100];	//current choices
int current_in[1100];	//the order of current choices
int ncans;		//number of candidates
int ch_count;		//total number of votes
bool outs[25] = {true};

void ini() {
	for (int i = 0; i < 21; ++i) {
		cans[i] = "";
		cnts[i] = 0;
		outs[i] = false;	
	}
	for (int i = 0; i < 1001; ++i) {
		current_in[i] = 1;
		current_ch[i] = 0;
	}
	ncans = 0;
	ch_count = 0;
}

/*proc: find the tickets the current choice is eliminated candidate, then update it*/ 
void proc() {
	int min = 1001;
	vector<int> eli;
	/*find the candidate numbers to be eliminated*/
	for (int i = 1; i <= ncans; ++i) {
		if (!outs[i]) {
			if (cnts[i] < min) {
				min = cnts[i];
				eli.clear();
				eli.push_back(i);
			}
			else if (cnts[i] == min) 
				eli.push_back(i);
		}
	}
	/*update everything*/
	for (vector<int>::size_type j = 0; j < eli.size(); ++j) {
		int i = eli[j];
		cnts[i] = 0;  //out, i is the candidate number
		outs[i] = true;
		for (int j = 1; j <= ch_count; ++j) {	//j is the votes number
			if (current_ch[j] == i) {	//find the votes needs to update
				current_in[j]++;
				int k = current_in[j];
				current_ch[j] = ch[j][k];
				cnts[current_ch[j]]++;
			}
		}
	}
}

bool check() {
	bool tie = true;
	int tie_num; 	//if tie, the number of votes each candidate get
	int j = 1;
	while (outs[j])
		j++;
	tie_num = cnts[j];
	for (int i = 1; i <= ncans; ++i) {
		if (!outs[i]) {  //remaining candidates
			if (cnts[i]*2 > ch_count) {
				cout << cans[i] << endl;
				return true;
			}
			else if (cnts[i] != tie_num) 
				tie = false;
		}
	}
	if (tie == true) {
		for (int i = 1; i <= ncans; ++i)
			if (!outs[i])
				cout << cans[i] << endl;
		return true;
	}
	return false;
}

int main(void) {
	int ncase;
	cin >> ncase;
	while (ncase--) {
		ini();
		cin >> ncans;
		string tmp;
		getline(cin, tmp);  //eliminate the new line left behind
		for (int i = 1; i <= ncans; ++i) 
			getline(cin, cans[i]);
		string s;
		while (getline(cin, s)) {
			if (s == "")
				break;
			istringstream input(s);
			ch_count++;
			for (int j = 1; j <= ncans; ++j) {
				input >> ch[ch_count][j];
				if (j == 1)
					cnts[ch[ch_count][j]]++;	//count the initial choices
			}
			current_ch[ch_count] = ch[ch_count][1];  //initialize the current choice		
		}
		/*begin to process*/
		while (!check()) 
			proc();
		if (ncase)
			cout << endl;
	}
}

krkhan · Post by **krkhan** » Mon Jul 07, 2008 11:52 pm

Since I was just practicing STL, this code is ugly. I don't expect anyone to read through it. However, even though I have tried every (valid) test-case I have been able to found and it worked perfectly, the judge says time limit exceeds on this one

. I'll be thankful if someone can point out some quirky test-case:

Code: Select all

#include <iostream>
#include <iomanip>
#include <string>
#include <sstream>
#include <vector>
#include <iterator>
#include <map>

using namespace std;

#define NBALLOTS 1000

typedef vector< vector< int > > twod_vector;

istream& operator>>(istream& in, twod_vector &v)
{
	for(twod_vector::iterator p = v.begin(); p < v.end(); p++) {
		for(vector< int >::iterator pr = (*p).begin();
				pr < (*p).end();
				pr++) {
			*pr = *istream_iterator<
				twod_vector::value_type::value_type
				>(in);
		}
	}

	return in;
}

ostream& operator<<(ostream &out, twod_vector v)
{
	twod_vector::const_iterator p;

	for(p = v.begin(); p < v.end(); p++) {
		vector< int >::const_iterator pp;
		for(pp = (*p).begin(); pp < (*p).end(); pp++) {
			out<<setw(5)<<*pp<<" ";
		}
		out<<endl;
	}

	return out;
}

vector< int > calculate(vector< int > votes, int ncand, bool atleast_50)
{
	vector< int > winners;

	int total = votes.size();
	int max = 0;
	for(int i = 0; i < ncand; i++) {
		int id = i + 1;
		int vote_count = count(votes.begin(), votes.end(), id);
		bool cond = !atleast_50 || (vote_count > total / 2);
		if(vote_count > 0 &&
				vote_count >= max &&
				cond) {
			max = vote_count;
			winners.push_back(i);
		}
	}

	return winners;
}

bool compare(pair< int, int > a, pair< int, int > b)
{
	return a.second < b.second;
}

map< int, int > vote_map(vector< int > votes)
{	map< int, int > table;
	vector< int >::iterator p;

	for(p = votes.begin(); p < votes.end(); p++) {
		if(table.count(*p) > 0) {
			table[*p]++;
		} else {
			table[*p] = 1;
		}
	}

	return table;
}

vector< int > least_votes(vector< int > votes)
{
	map< int, int > table = vote_map(votes);
	vector< int > min_keys;
	int min_value =
		min_element(table.begin(), table.end(), compare)->second;

	map< int, int >::iterator p;
	for( p = table.begin(); p != table.end(); p++ ) {
		if(p->second == min_value) {
			min_keys.push_back(p->first);
		}
	}

	return min_keys;
}

twod_vector shift(twod_vector ballots)
{
	vector< int > &first = ballots.at(0);
	vector< int > min_values = least_votes(ballots.at(0));

	vector< int >::iterator pi;
	for(pi = min_values.begin(); pi != min_values.end(); pi++) {
		int min_value = *pi;
		vector< int >::iterator p;
		while((p = find(first.begin(), first.end(), min_value)) 
			!= first.end()) {
			int index = p - first.begin();
			int tmp = ballots.at(0).at(index);
			ballots.at(0).at(index) = ballots.at(1).at(index);
			int i;
			for(i = 1; i < (int) ballots.size() - 1; i++) {
				ballots.at(i).at(index)
					= ballots.at(i + 1).at(index);
			}
			ballots.at(i).at(index) = tmp;
		}
	}

	return ballots;
}

bool draw(vector< int > votes)
{
	if(!votes.size()) {
		return true;
	}

	map< int, int > table = vote_map(votes);
	map< int, int >::iterator p = table.begin();
	int n = p->second;
	p++;
	for(; p != table.end(); p++) {
		if( n != p->second ) {
			return false;
		}
	}

	return true;
}

int main(int argc, char *argv[])
{
	twod_vector ballots;
	int ncases;
	cin>>ncases;
	cin.ignore();
	string dummy;
	getline(cin, dummy);

	for(int i = 0; i < ncases; i++) {
		int ncand;
		cin>>ncand;
		cin.ignore();

		vector< string > candidates(ncand);
		for(int j = 0; j < ncand; j++) {
			getline(cin, candidates.at(j));
		}

		twod_vector ballots(ncand);
		for(int j = 0; j < NBALLOTS; j++) {
			string str;

			getline(cin, str);
			if(str == "") {
				break;
			}

			istringstream iss(str);
			vector< int > v;
			for(int k = 0; k < ncand; k++) {
				int value = *istream_iterator< int >(iss);
				if(find(v.begin(), v.end(), value)
					== v.end()) {
					v.push_back(value);
				}
			}

			if((int) v.size() < ncand) {
				continue;
			}
			for(int k = 0; k < ncand; k++) {
				ballots.at(k).push_back(
						v.at(k)
						);
			}
		}

		vector< int > winners;
		int j = 0;
		while(winners.size() == 0) {
			if(j > 0) {
				if(draw(ballots.at(0))) {
					winners = calculate(
							ballots.at(0),
							ncand,
							false);
					break;
				}
				ballots = shift(ballots);
			}

			winners = calculate(ballots.at(0), ncand, true);
			j++;
		}

		if(!ballots.at(0).size()) {
			for(int k = 0; k < ncand; k++) {
				winners.push_back(k);
			}
		}

		sort(winners.begin(), winners.end());
		if(i > 0) {
			cout<<endl;
		}
		vector< int >::const_iterator p;
		for(p = winners.begin(); p < winners.end(); p++) {
			cout<<candidates.at(*p)<<endl;
		}
	}

	return 0;
}

krkhan · Post by **krkhan** » Thu Jul 10, 2008 2:55 am

I finally got my program to be accepted at Programming Challenges' website. In my previous code, I wasn't "eliminating" candidates the right way.

However, the program still exceeds time-limit at UVa judge

:

Code: Select all

#include <iostream>
#include <iomanip>
#include <string>
#include <sstream>
#include <vector>
#include <iterator>
#include <map>

using namespace std;

#define NBALLOTS 1000

typedef vector< vector< int > > twod_vector;

vector< int > calculate(vector< int > &votes, int ncand, bool atleast_50)
{
	vector< int > winners;

	int total = votes.size();
	int max = 0;
	for(int i = 0; i < ncand; i++) {
		int id = i + 1;
		int vote_count = count(votes.begin(), votes.end(), id);
		bool cond = !atleast_50 || (vote_count > total / 2);
		if(vote_count > 0 &&
				vote_count >= max &&
				cond) {
			max = vote_count;
			winners.push_back(i);
		}
	}

	return winners;
}

bool compare(pair< int, int > a, pair< int, int > b)
{
	return a.second < b.second;
}

map< int, int > vote_map(vector< int > &votes)
{
	map< int, int > table;
	vector< int >::iterator p;

	for(p = votes.begin(); p < votes.end(); p++) {
		if(table.count(*p) > 0) {
			table[*p]++;
		} else {
			table[*p] = 1;
		}
	}

	return table;
}

vector< int > least_votes(vector< int > &votes)
{
	map< int, int > table = vote_map(votes);
	vector< int > min_keys;
	int min_value =
		min_element(table.begin(), table.end(), compare)->second;

	map< int, int >::iterator p;
	for( p = table.begin(); p != table.end(); p++ ) {
		if(p->second == min_value) {
			min_keys.push_back(p->first);
		}
	}

	return min_keys;
}

void eliminate(twod_vector &ballots, int value)
{
	for(int i = 0; i < (int) ballots.size(); i++) {
		for(int j = 0; j < (int) ballots.at(i).size(); j++) {
			if(ballots.at(i).at(j) == value) {
				for(int k = i;
					k < (int) ballots.size() - 1;
					k++) {
					ballots.at(k).at(j)
						= ballots.at(k + 1).at(j);
				}
			}
		}
	}
}

void eliminate(twod_vector &ballots)
{
	vector< int > min_values = least_votes(ballots.at(0));

	for(vector< int >::iterator p = min_values.begin();
			p != min_values.end();
			p++) {
		eliminate(ballots, *p);
	}
}

bool draw(vector< int > &votes)
{
	if(!votes.size()) {
		return true;
	}

	map< int, int > table = vote_map(votes);
	map< int, int >::iterator p = table.begin();
	int n = p->second;
	p++;
	for(; p != table.end(); p++) {
		if( n != p->second ) {
			return false;
		}
	}

	return true;
}

int main(int argc, char *argv[])
{
	twod_vector ballots;
	int ncases;
	cin>>ncases;
	cin.ignore();
	string dummy;
	getline(cin, dummy);

	for(int i = 0; i < ncases; i++) {
		int ncand;
		cin>>ncand;
		cin.ignore();

		vector< string > candidates(ncand);
		for(int j = 0; j < ncand; j++) {
			getline(cin, candidates.at(j));
		}

		twod_vector ballots(ncand);
		for(int j = 0; j < NBALLOTS; j++) {
			string str;

			getline(cin, str);
			if(str == "") {
				break;
			}

			istringstream iss(str);
			vector< int > v;
			for(int k = 0; k < ncand; k++) {
				int value = *istream_iterator< int >(iss);
				ballots.at(k).push_back(
						value
						);
			}
		}

		vector< int > winners;
		int j = 0;
		while(winners.size() == 0) {
			if(j > 0) {
				if(draw(ballots.at(0))) {
					winners = calculate(
							ballots.at(0),
							ncand,
							false);
					break;
				}
				eliminate(ballots);
			}

			winners = calculate(ballots.at(0), ncand, true);
			j++;
		}

		if(!ballots.at(0).size()) {
			for(int k = 0; k < ncand; k++) {
				winners.push_back(k);
			}
		}

		sort(winners.begin(), winners.end());
		if(i > 0) {
			cout<<endl;
		}
		vector< int >::const_iterator p;
		for(p = winners.begin(); p < winners.end(); p++) {
			cout<<candidates.at(*p)<<endl;
		}
	}

	return 0;
}

OJ Board

10142 - Australian Voting

how to test?

10142- wa

10142 RE!!!

Hi!

10142... RTE (Signal 11).. Please help

10142 TLE(Help Needed!!)

Bug

WA, depressed.

Re: 10142 - Australian Voting

Re: 10142 - Australian Voting