10142 - Australian Voting

[AndyGee]

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]

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

[Roby]

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]

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.

[chunyi81]

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]

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

[willima]

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.

[petrov]

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]

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...

[CodeMaker]

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.

[CodeMaker]

i got your code Accepted!!!

you want me to tell how ?

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.

[chaturvedi]

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;
}
}

[CodeMaker]

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

[peace]

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]

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..