10142 - Australian Voting

All about problems in Volume 101. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

AndyGee
New poster
Posts: 8
Joined: Sat Nov 13, 2004 3:11 pm
Location: KG
Contact:

10142 - Australian Voting WA

Post by AndyGee » Fri Sep 23, 2005 11:45 am

Can anybody help me, what is wrong with my code?
I got AC in http://www.programming-challenges.com/, but WA in UVA.
Or give me some critical i/o please.

Thanks in advance.

Code: Select all

/* ACM Problem Set */

/* Problem 10142 */
/* Australian Voting */ 

#include <cstdio>
#include <string.h>
using namespace std; 

int main()
{
   int t;
   scanf("%d\n", &t);
   scanf("\n");
   for ( ; t > 0; t--)
   {
      char names[20][100];
      bool skipped[20];
      char votes[1000][20];
      int cursors[1000];
      memset (names, (char)0, sizeof(char) * 20 * 100);
      memset (skipped, (bool)0, sizeof(bool) * 20);
      memset (votes, (char)0, sizeof(char) * 20 * 1000);
      memset (cursors, (char)0, sizeof(char) * 1000);
      int count;
      scanf("%d\n", &count);
      for (int i = 0; i < count; i++) gets(names[i]);
      int vote_count = -1;
      char s[6000];
      strcpy(s,"");
      while (gets(s))
      {
         if (strlen(s) == 0) break;
         vote_count++;
         char s1[6000];
         for (int i = 0; i < count; i++)
         {
            sscanf(s, "%d %6000c", &votes[vote_count][i], &s1);
            strcpy(s, s1);
         }
      }
      vote_count++;
      int skip_count = 0;
      while (skip_count < count)
      {
         //calculate votes
         int votes_for_name[20];
         memset (votes_for_name, (int)0, sizeof(int) * 20);
         for (int i = 0; i < vote_count; i++)
            votes_for_name[votes[i][cursors[i]]-1]++;
         int min = vote_count, min_count = 0, max = 0;

         for (int i = 0; i < count; i++)
         {
            if (skipped[i]) continue;
            if (votes_for_name[i] < min) 
            {
               min_count = 0;
               min = votes_for_name[i]; 
            }
            if (votes_for_name[i] == min) min_count++;
         }

         //check for draw
         if (min_count == (count - skip_count))
         {
            for (int i = 0; i < count; i++)
               if (!skipped[i]) puts(names[i]);
            break;
         }
         //skip ballots
         for (int i = 0; i < count; i++)
            if (votes_for_name[i] == min) skipped[i] = true;
         //move cursors
         for (int i = 0; i < vote_count; i++)
            while (skipped[votes[i][cursors[i]]-1]) cursors[i]++;
         skip_count += min_count;
      }
      if (t > 1) printf("\n");
   }
}

sectroyer
New poster
Posts: 8
Joined: Mon Nov 28, 2005 4:55 pm

Post by sectroyer » Sun Dec 04, 2005 9:46 pm

I have a problem my code has WA at PC and RE here.
But I am not able to find a bug :(
Please help

#include <stdio.h>

int main(int argc, char *argv[])
{
int i1,i2,i3,i4,n,ilosc,next,igls,kon,naj,inaj,najm,inajm,akt;
short int wyn[30];
char dupa[1000000];
char kan[30][1000];
char gls[1010][30];
scanf("%d",&ilosc);
gets(dupa);
next=0;
for(i4=0;i4<ilosc;i4++)
{
if(next==0)
{
scanf("%d",&n);
gets(dupa);
}
else
n=next;
next=0;
for(i1=0;i1<n;i1++)
{
gets(kan[i1]);
}
kon=0;
for(igls=0;;igls++)
{
for(i1=0;i1<n;i1++)
{
if((akt=scanf("%d",&gls[igls][i1]))==EOF)
{
kon=1;
break;
}
else if(akt==0)
{
if(i1==1)
{
next=gls[igls][0];
kon=1;
break;
}
}
}
if(kon==1)
break;
if(igls>10000)
break;
}
akt=igls;
for(i1=0;i1<30;i1++)
wyn[i1]=0;
for(i1=0;i1<igls;i1++)
{
wyn[gls[i1][0]-1]++;
}
naj=0;
inaj=0;
najm=2000;
inajm=0;
while(1)
{
naj=0;
inaj=0;
inajm=0;
najm=2000;
for(i1=0;i1<n;i1++)
{
if((wyn[i1]<najm) && (wyn[i1] >=0))
{
najm=wyn[i1];
inajm=1;
}
else if(wyn[i1]==najm)
inajm++;
if(wyn[i1]>naj)
{
naj=wyn[i1];
inaj=1;
}
else if(wyn[i1]==naj)
inaj++;
}
if(inaj > 10000)
break;
if((inaj==1) || (inaj==akt))
break;
if(naj==akt)
break;
for(i1=0;i1<n;i1++)
{
if(wyn[i1]==najm)
{
wyn[i1]=-1;
akt--;
}
}
for(i1=0;i1<n;i1++)
{
if(wyn[i1]==-1)
{
for(i2=0;i2<igls;i2++)
{
if(gls[i2][0]==(i1+1))
{
for(i3=0;i3<n;i3++)
{
if(wyn[gls[i2][i3]-1]!=-1)
{
wyn[gls[i2][i3]-1]++;
break;
printf("%d\n",gls[i2][i3]);
}
}
}
}
}
}
}
for(i1=0;i1<n;i1++)
{
if(wyn[i1]==naj)
printf("%s\n",kan[i1]);
}
putchar('\n');
}
return 0;
}
Thanks in advance

User avatar
Roby
Experienced poster
Posts: 101
Joined: Wed May 04, 2005 4:33 pm
Location: Tangerang, Banten, Indonesia
Contact:

Post by Roby » Mon Dec 05, 2005 6:03 am

Can someone explain to me how to simulate this voting system? I don't understand the problem description, especially with the way to get the winner.

Thanx in advance.

bharatj
New poster
Posts: 3
Joined: Sun Jan 15, 2006 8:38 am

10142 : AC at PC site but RE here

Post by bharatj » Sun Jan 15, 2006 8:58 am

My code got a "Solved" (AC) at http://www.programming-challenges.com but getting an RE at uVa.
Could anyone of you plz help in finding a potential bug in my code or some test cases bcoz of which i'm getting an RE here.

edit: removed code.
Last edited by bharatj on Tue May 23, 2006 3:40 pm, edited 2 times in total.

chunyi81
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore

Post by chunyi81 » Sun Jan 15, 2006 11:22 am

I have not solved this problem but your code goes into an infinite loop with this test case:

Code: Select all

1

3
L
P
M
1 2 3
1 3 2
2 3 1
2 1 3
1 3 2
2 3 1
Correct output is:

Code: Select all

L
P

bharatj
New poster
Posts: 3
Joined: Sun Jan 15, 2006 8:38 am

Post by bharatj » Sun Jan 15, 2006 11:59 am

oh sorry but i did the copy-paste wrong. there was a comment before the the line:
REP (j, num) if (!votes[j]) votes[j]=-1; (55th line from the beginning)

with that it passes the test case u have provided with.

any other case might be helpful.

thanx

User avatar
willima
New poster
Posts: 13
Joined: Wed Dec 07, 2005 1:19 pm
Location: Brazil

I didn't understand this names!

Post by willima » Thu Jan 19, 2006 7:36 pm

Hellow N|no, I'm sorry but I didn't understand some names of variables you've used in you source code, so, I couldn't understand that. Could you possibly translate these names for names in English more common?

Thanx, goodbye. :wink:

petrov
New poster
Posts: 1
Joined: Wed Mar 01, 2006 9:31 pm

10142 - passed PC but got WA here

Post by petrov » Tue Jul 11, 2006 1:43 pm

OK, the strangest thing happened. People say that the input on the PC site is tougher than that of uva. I submitted there and got AC, but here I got WA. I've tried all the test cases posted on the forums, the program produces correct answers, but still WA... can anybody help me, maybe I have overlooked something small or something...

Code: Select all

#include <cstdio>
#include <cstdlib>
#include <algorithm>

using namespace std;

#define MAXN 1024
#define MAXC 32
#define MAXNAME 85

int a[MAXN][MAXC];
int have[MAXC];
char names[MAXC][MAXNAME];
bool out[MAXC];
int num_can;
int temp;
int pos;
int gmin;

int count(int n) {
    temp = 0;
    while (n) {
        n /= 10;
        temp++;
    }
    return temp;
}

void process(char * szBuffer, int pos) {
    for (int i = 0; i < num_can - 1; i++) {
        a[pos][i] = atoi(szBuffer) - 1;
        strcpy(szBuffer, szBuffer + count(a[pos][i]) + 1);
    }
    a[pos][num_can-1] = atoi(szBuffer) - 1;
    return;
}

bool judge(void) {
    int max;
    int tmin = 1024;
    int tmax = -1;
    int count = 0;
    max = 0;
    
    for (int i = 0; i < num_can; i++) {
        if (!out[i]) {
            if (have[i] > tmax) {
                max = i;
                tmax = have[i];
                count = 1;
            }
            else if (have[i] == tmax) {
                count++;
            }
            if (have[i] < tmin) {
                tmin = have[i];
            }
        }
    }
    if (count == 1 && ((double)have[max])/pos > 0.5) {
        puts(names[max]);
        return false;
    }
    if (tmin == tmax) {
        for (int i = 0; i < num_can; i++) {
            if (!out[i]) {
                puts(names[i]);
            }
        }
        return false;
    }
    gmin = tmin;
    return true;
}

void recalculate(void) {
    int i, j;
    for (i = 0; i < num_can; i++) {
        if (have[i] == gmin) {
            out[i] = true;
        }
    }
    for (i = 0; i < num_can; i++) {
        have[i] = 0;
    }
    for (j = 0; j < pos; j++) {
        i = 0;
        while (out[a[j][i]]) {
            i++;
        }
        have[a[j][i]]++;
    }
    return;
}

int main() {
    int num_test_cases;
    char szBuffer[MAXN];
    
    scanf("%d", &num_test_cases);
    
    for (int i = 0; i < num_test_cases; i++) {
        scanf("%d\n", &num_can);
        
        memset(out, false, sizeof(out));
        memset(have, 0, sizeof(have));
        pos = 0;
        
        for (int j = 0; j < num_can; j++) {
            gets(names[j]);
        }

        while (true) {
            if (gets(szBuffer) == NULL) {
                break;
            }
            if (strlen(szBuffer) == 0) {
                break;
            }
            process(szBuffer, pos++);
        }
        if (pos == 0) {
            for (int j = 0; j < num_can; j++) {
                puts(names[j]);
            }
            if (i != num_test_cases - 1) {
                printf("\n");
            }
            continue;
        }
        for (int j = 0; j < pos; j++) {
            have[a[j][0]]++;
        }
        for (int j = 0; j < num_can; j++) {
            if (have[j] == 0) {
                out[j] = true;
            }
        }
        while (judge()) {
            recalculate();
        }
        if (i != num_test_cases - 1) {
            printf("\n");
        }
    }
    return 0;
}

chaturvedi
New poster
Posts: 8
Joined: Mon Jul 10, 2006 9:31 am

10142 Runtime Error!! Help Me!!!! :(

Post by chaturvedi » Sun Jul 16, 2006 4:07 pm

I am getting invalid memory reference for my code!! It works for the test cases I got in earlier threads correctly!! Help me I am not able to figure out!! Here is the code:
#include<string.h>
#include<stdio.h>
struct details
{
char name[81];
int novotes;
}elements[21];

void count (int b,int n);
void initial(int n);
void initial1(int n);
int maxmin(int n,int *min);
void eliminate(int min,int n);
void print(int);
int a[1001][21];
char maxname[81];
void main()
{

int t,n,i,j,senti=0,max,min,k;


scanf("%d",&t);
fflush(stdin);
printf("\n");
for(k=1;k<=t;k++)
{
senti=0;
scanf("%d",&n);
fflush(stdin);
for(j=1;j<=n;j++)
{
gets(elements[j].name);
fflush(stdin);
}


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

while(scanf("%d",&a[j])==1)
{
for(j=2;j<=n;j++)
scanf("%d",&a[j]);
i++;
j=1;
}

while(senti==0)
{
count(i-1,n);
max=maxmin(n,&min);

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


if(((float)max)>((float)((i-1)/2)) && senti==0)
{
printf("%s",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[j]].novotes!=-1)
{
elements[a[j]].novotes++;
break;
}
}
}
}

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

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

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

void print(int n)
{
int i;
for(i=1;i<=n;i++)
{
if(elements.novotes!=-1)
{
if(i==1)
printf("%s",elements[i].name);
else
printf("\n%s",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;
}
}
Any help will be greatfully acknowledged...

User avatar
CodeMaker
Experienced poster
Posts: 183
Joined: Thu Nov 11, 2004 12:35 pm
Location: AIUB, Bangladesh

Post by CodeMaker » Mon Jul 17, 2006 6:02 am

hi, whenever you get that type of Run time error ( invalid memory refference) that means you are over running your array limit.

so, your first approach will be increasing the array limits.
if the problem says the names will be 80 character in length , that doesn't mean you have to declare an array of size 80+1 . you can take 100 , is there any problem? :) so, always declare the arrays a bit larger than the problem asks for.

so after increasing all the array limits, your code got wrong answer.... so try to fix it.
Jalal : AIUB SPARKS

User avatar
CodeMaker
Experienced poster
Posts: 183
Joined: Thu Nov 11, 2004 12:35 pm
Location: AIUB, Bangladesh

Post by CodeMaker » Mon Jul 17, 2006 9:49 am

:D i got your code Accepted!!!

you want me to tell how ? :wink:

well you gave me hard time, i was almost praying to get your code AC because i tested your code with a lot of hand made data and found no missmatch. after lot of try i started to read your code and in your process() founction i found a fault.

it is not told in the problem that there will be only one space between the numbers, but you assumed that there will be only one space.

then i put some more spaces in the middle like:

Code: Select all

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
but it still gave the right output of this dataset (amazing!)
but i knew it can be a problem ,i debuged and saw i am correct, fixed it and got AC


:-?

for the people who got accepted in programming challenges i think they should try this, the uva dataset has more spaces in the lines.
Jalal : AIUB SPARKS

chaturvedi
New poster
Posts: 8
Joined: Mon Jul 10, 2006 9:31 am

Why Invalid Memory Reference?? Help me...

Post by chaturvedi » Thu Jul 27, 2006 4:04 pm

I am getting invalid memory reference as the verdict of the code for 10142... It's getting really sick now... I have increased the limits, am using elementary operations to read strings... It works properly for all the test cases given in threads... I am not understanding what the judge means to say by its verdict!! Can anybody tell me whats the problem with my code... Any help will be greatfully acknowledged... Here's me code:

#include<string.h>
#include<stdio.h>
struct details
{
char name[100];
int novotes;
}elements[32];
void count (int b,int n);
void getstring(char *);
void initial(int n);
void initial1(int n);
int maxmin(int n,char *maxname,int *min);
void eliminate(int min,int n);
void print(int);
int a[1024][32];
void main()
{

int t,n,i,j,senti=0,max,min,k;
char *maxname;

scanf("%d",&t);

printf("\n");
for(k=1;k<=t;k++)
{
senti=0;
scanf("%d",&n);

for(j=1;j<=n;j++)
{
getstring(elements[j].name);
}


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

while(scanf("%d",&a[j])==1)
{
for(j=2;j<=n;j++)
scanf("%d",&a[j]);
i++;
j=1;
}

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)
{
printf("%s",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[j]].novotes!=-1)
{
elements[a[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.novotes>max)
{
max=elements.novotes;
j=i;
}

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

void print(int n)
{
int i;
for(i=1;i<=n;i++)
{
if(elements.novotes!=-1)
{
if(i==1)
printf("%s",elements[i].name);
else
printf("\n%s",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 getstring(char *string)
{
int i=0;
char c;
while((c=getchar()) !='\n' || i==0)
{
string[i]=c;
i++;
}
string[i]='\0';
}

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

User avatar
CodeMaker
Experienced poster
Posts: 183
Joined: Thu Nov 11, 2004 12:35 pm
Location: AIUB, Bangladesh

Post by CodeMaker » Wed Aug 09, 2006 7:47 am

Hi, well my exam is not over yet. but as you r really in trouble with 10142, so i decided to give you some hand. well it didn't take long to give you something here.

i tested your code with my I/O file ( i even posted that in the board, you told that u have tested all the I/O in the board, have you tested with mine?)

your code crashes for my I/O file. so now you have the input. and output. i think from here you can find out what is wrong in your code by yourself through debugging.

*** IMPORTANT: Don't edit it, as you can see there are more space in the middles of the numbers. this how the judge input file will be. so just copy past the inputs to test your code.

INPUT

Code: Select all

7

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

OUTPUT

Code: Select all

i am jalal
he is Hasan

L
P

B

jalal
bijon

John Doe

John Doe

jalal
hasan
Jalal : AIUB SPARKS

peace
New poster
Posts: 5
Joined: Wed Aug 09, 2006 1:34 am

10142

Post by peace » Wed Aug 16, 2006 5:20 am

I got WA but I couldn't find the error :(

here is my code. Can anyone help me?

Code: Select all

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

struct bollot{
       int n;
       int order[20];
       };

int next(int *remain,struct bollot b,int n);

int main()
{
    struct bollot array[1000];
    char candidate[20][150];
    char string[150];
    int count[20];
    int remain[20];
    char *ptr,*temp;
    int m,n,b;
    int i,j;
    int outcome,max,min,maxc,minc;
    scanf("%d\n\n",&m);
    while(m--){
         scanf("%d\n",&n);
         for(i=0;i<n;i++)
              gets(candidate[i]);
         for(j=0;;j++){
              if(gets(string)==NULL)
                   break;
              else if(strcmp(string,"")==0)
                   break;
              array[j].n=0;
              ptr=strtok(string," ");
              for(i=0;i<n;i++){
                   temp=strtok(NULL," ");
                   sscanf(ptr,"%d",&array[j].order[i]);
                   ptr=temp;
              }
         }
         for(i=0;i<n;i++)
              remain[i]=1;
         for(b=j,outcome=0;outcome==0;){
              for(i=0;i<n;i++)
                   count[i]=0;
              for(i=0;i<b;i++){
                   if(remain[array[i].order[array[i].n]-1])
                        count[array[i].order[array[i].n]-1]++;
                   else if((array[i].n=next(remain,array[i],n))==n)
                        outcome=1;
                   else
                        count[array[i].order[array[i].n]-1]++;
              }
              for(i=0,max=0,min=10000;i<n;i++){
                   if(!remain[i])
                        continue;
                   if(count[i]>max){
                        maxc=i;
                        max=count[i];
                   }
                   if(count[i]<min){
                        minc=i;
                        min=count[i];
                   }
              }
              if((double)max/b>0.5){
                   outcome=1;
                   printf("%s\n",candidate[maxc]);
              }
              else if(outcome||min==max){
                   for(i=0;i<n;i++){
                        if(count[i]==max)
                             printf("%s\n",candidate[i]);
                   outcome=1;
                   }
              }
              else
                   remain[minc]=0;
         }
         printf("\n");
    }
}

int next(int *remain,struct bollot b,int n)
{
    int i;
    for(i=b.n+1;i<n;i++){
         if(remain[i])
              return i;
    }
    return i;
}


thx for your help

CGR
New poster
Posts: 4
Joined: Sun Oct 09, 2005 8:11 pm

Post by CGR » Tue Sep 19, 2006 8:05 pm

:-?

So.. when input is

Code: Select all

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 
output is

Code: Select all

jalal
bijon
???

Shouldn't we ignore the last ballot, since it's not valid ?
But if we do so, output would be jalal, without bijon..

Post Reply

Return to “Volume 101 (10100-10199)”