10420 - List of Conquests

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

Moderator: Board moderators

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post by Per » Thu Sep 09, 2004 5:48 pm

There is no guarantee that there is at most 80 countries.

User avatar
Ghust_omega
Experienced poster
Posts: 115
Joined: Tue Apr 06, 2004 7:04 pm
Location: Venezuela

Post by Ghust_omega » Fri Sep 10, 2004 12:42 pm

Hi!! Per thanks for you answer, i change the value to 800 and still WA , i change the compare about strcmp to < 0, ichange the size of country to 800 and the array to the frecuencies to 800 and nothing still WA please Help :(

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post by Per » Fri Sep 10, 2004 12:58 pm

There is no guarantee that there is at most 800 countries, either.

User avatar
Ghust_omega
Experienced poster
Posts: 115
Joined: Tue Apr 06, 2004 7:04 pm
Location: Venezuela

Post by Ghust_omega » Fri Sep 10, 2004 9:05 pm

Thanks Per for your answer, and that case what size can be the array :-? please Help me, or better how many countries are??

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Fri Sep 10, 2004 11:16 pm

Ghust_omega, just try to create any dynamic data structure. Not always static tables are enough :-)

Best regards
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post by Per » Sat Sep 11, 2004 2:18 pm

Though in this case, they are.
The input consists of at most 2000 lines.

User avatar
Ghust_omega
Experienced poster
Posts: 115
Joined: Tue Apr 06, 2004 7:04 pm
Location: Venezuela

Post by Ghust_omega » Sat Sep 11, 2004 3:37 pm

HI Per and Dominik thanks for yours answers I will rewrite my code with linked list with order plus frecuency of country but now i wonder how long is the name of a country
?? :-?
to Per and Dominik Keep posting!!
Thanks in advance

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

Post by CodeMaker » Mon Nov 15, 2004 5:32 am

Hi, anyone who needs helps in this problem can check this out....nothing much but may help u.

I was getting WA for whole night(u know how it feels :evil: ) and in the morning i just got AC :D ....

Here is some I/O...u can test it...[c]15
Bangladesh Jalal Uddin
Bangladesh Jalal Uddin
Bangladesh Jalal Uddin
Bangladesh Hasan
Bangladesh Bijon Khaled Jaman
Bangladesh Jalal Uddin
Bangladesh Jalal Uddin
India Saiket podder
India Partha Sarker
Bangladesh Hasan Ahmed
Bangladesh Bijon Khaled Jaman
Australia Anil
Bangladesh Shoikot
Barma Asma
Bangladesh Saiket[/c]

Output:
Australia 1
Bangladesh 6
Barma 1
India 2
Jalal : AIUB SPARKS

User avatar
Ali Arman Tamal
Learning poster
Posts: 76
Joined: Sat Jan 15, 2005 5:04 pm
Location: Dhaka
Contact:

Post by Ali Arman Tamal » Fri Jan 21, 2005 11:51 am

Hello Everyone ! :)

I think codemaker is wrong. I solved the code without considering any duplicate women name and still got AC. :wink:

My output for the codemaker's input is

Australia 1
Bangladesh 11
Barma 1
India 2

Since the judge doesn't seem to give any duplicate name, so considering duplicate or not considering will lead to the same answer !! :wink:

And Ghust Omega, if you still haven't got AC, watch this:

1. There will not be more than 201 different countries. My AC code couldn't handle more than 201 different countries.

2. You can use array of structure like this:


struct data
{
char name[80];
int freq;
};

struct data country[201];

and later use it for other operation :)

Hope it helps!!

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by Sedefcho » Tue Feb 22, 2005 12:10 am

Hello, Ali Arman Tamal !

Yes, you are right. I got ACC having same output as yours
for CodeMaker's input.

Seems like the tests the Judge has really don't contain
duplicate women names.

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by Sedefcho » Tue Feb 22, 2005 12:17 am

By the way, if they put decent tests for this problem we will
get WA. I think the better approach is to take into consideration
duplicate women names.

User avatar
smilitude
Experienced poster
Posts: 137
Joined: Fri Jul 01, 2005 12:21 am

10420 Runtime error

Post by smilitude » Tue Apr 11, 2006 5:18 am

Sir John Leparro (104-20) has died on the march 20th of the year 2006 with signal 11 (SIGSEGV). Meaning:

Invalid memory reference :o

Before being crashed by an ongoing heavy truck, he ran for 0.014 seconds on the streets of downtown of UVa. His last wish was someone will tell his innocent relatives about why he had an invalid memory reference problem! :cry:

We mourn for Sir John Leparro, but right now, invalid memory reference is bugging us very much! Instead of a proper hashing, all the program did is a proper crashing~! :P

Code: Select all

/*
 * 10420 List of Conquests
 * submission 1 RE
 * coded at 1004pm march 20, 2006
 *
 */ 


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

#define PRIME 3001
#define MULTIPLIER 37
#define NHASH PRIME

typedef struct Country Country;
struct Country {
    char name[76];
    int count;
    int next;
};

Country country[3001];
int extra=2003;

void init() {
    for(int i=0;i<=PRIME;i++) {
        strcpy(country[i].name,"");
        country[i].count=0;
        country[i].next=-1;
    }
}        

void print() {
    for(int i=0;i<=PRIME;i++) {
        if(strcmp(country[i].name,"")!=0) {
            printf("%s %d\n",country[i].name,country[i].count);
        }
    }
}

int compare(const void *va, const void *vb) {
    Country *a,*b;
    a=(Country *)va;
    b=(Country *)vb;
    
    return strcmp(a->name,b->name);
}                

unsigned int hash(char *str) {
    unsigned int h=0;
    int len=strlen(str);
   
    for(int i=0;i<len;i++) 
        h=MULTIPLIER*h + str[i];
    return h % NHASH;
}

void add(char *str) {
    int h=hash(str);
    if(!strcmp(country[h].name,"")) {
        strcpy(country[h].name,str);
        country[h].count++;
    }else if(!strcmp(country[h].name,str)) {
        country[h].count++;
    }else {
        while(country[h].next!=-1) {
            h=country[h].next;
            if(!strcmp(country[h].name,str)) {
                country[h].count++;
                h=-1;
                break;
            }
        }
        if(h!=-1) {
            country[h].next=++extra;
            strcpy(country[extra].name,str);
            country[extra].count++;
        }
    }
}            
         
int main() {
    char line[100];
    char word[76];
    int n;
    int i,j;
    
    while(scanf("%d",&n)==1) {
        init();
        gets(line);
        for(i=0;i<n;i++) {
            gets(line);
            j=0;
            while(line[j]!=' ') {
                word[j]=line[j];
                j++;
            }
            word[j]='\0';
            add(word);
        }
    qsort(country,PRIME,sizeof(country[0]),compare);
    print();
    }
    
    
}                
            
            
    
fahim
#include <smile.h>

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

Post by Roby » Tue Apr 11, 2006 7:01 am

Hmmm.. may be the array size is to small for the judge input... I've solved it with Binary Search Tree method, may be this method can help you out of this problem... :)

stubbscroll
Experienced poster
Posts: 151
Joined: Tue Nov 16, 2004 7:23 pm
Location: Norway
Contact:

Post by stubbscroll » Wed Apr 12, 2006 10:16 am

Volume CIV (104) is the correct thread for this problem.

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Wed Apr 12, 2006 11:04 am

I moved this thread to the correct forum. Please Mr. Smilitude, problems 104xx belong in volume 104, which is CIV in Roman numerals :)
I moved your other thread too.

Post Reply

Return to “Volume 104 (10400-10499)”