## 10142 - Australian Voting

Moderator: Board moderators

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

### 10142 - Australian Voting WA

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.

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;
bool skipped;
int cursors;
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;
strcpy(s,"");
while (gets(s))
{
if (strlen(s) == 0) break;
vote_count++;
char s1;
for (int i = 0; i < count; i++)
{
strcpy(s, s1);
}
}
vote_count++;
int skip_count = 0;
while (skip_count < count)
{
memset (votes_for_name, (int)0, sizeof(int) * 20);
for (int i = 0; i < vote_count; i++)
int min = vote_count, min_count = 0, max = 0;

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

//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++)
skip_count += min_count;
}
if (t > 1) printf("\n");
}
}``````

sectroyer
New poster
Posts: 8
Joined: Mon Nov 28, 2005 4:55 pm
I have a problem my code has WA at PC and RE here.
But I am not able to find a bug #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;
char dupa;
char kan;
char gls;
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];
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]-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]==(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;
}

Roby
Experienced poster
Posts: 101
Joined: Wed May 04, 2005 4:33 pm
Location: Tangerang, Banten, Indonesia
Contact:
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.

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

### 10142 : AC at PC site but RE here

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
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
oh sorry but i did the copy-paste wrong. there was a comment before the the line:

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

any other case might be helpful.

thanx

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

### I didn't understand this names!

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
New poster
Posts: 1
Joined: Wed Mar 01, 2006 9:31 pm

### 10142 - passed PC but got WA here

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]]++;
}
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!!!! :(

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

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;
char maxname;
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;

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++)
{
{
break;
}
}
}
}

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

for(i=1;i<=n;i++)
{
{
j=i;
}

}
strcpy(maxname,elements[j].name);
return max;
}

void print(int n)
{
int i;
for(i=1;i<=n;i++)
{
{
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++)
{
}
}
void initial1(int n)
{
int i;
for(i=1;i<=n;i++)
{
}
}

void eliminate(int min,int n)
{
int i;
for(i=1;i<=n;i++)
{
}
}
Any help will be greatfully acknowledged...

CodeMaker
Experienced poster
Posts: 183
Joined: Thu Nov 11, 2004 12:35 pm
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

CodeMaker
Experienced poster
Posts: 183
Joined: Thu Nov 11, 2004 12:35 pm 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.
Jalal : AIUB SPARKS

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

### Why Invalid Memory Reference?? Help me...

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

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++)
{
{
break;
}
}
}
}

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

for(i=1;i<=n;i++)
{
{
j=i;
}

}
strcpy(maxname,elements[j].name);
return max;
}

void print(int n)
{
int i;
for(i=1;i<=n;i++)
{
{
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++)
{
}
}
void initial1(int n)
{
int i;
for(i=1;i<=n;i++)
{
}
}

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++)
{
}
}

CodeMaker
Experienced poster
Posts: 183
Joined: Thu Nov 11, 2004 12:35 pm
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

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

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

int main()
{
struct bollot array;
char candidate;
char string;
int count;
int remain;
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;
}

``````

CGR
New poster
Posts: 4
Joined: Sun Oct 09, 2005 8:11 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..