OJ Board

what is the prob with my code of 10226 . it gets me TLE . pliz help me
Bye
Riyad

i went through all the topics about 10226 in the board . but no one seems to ans the reason behind getting TLE properly . how can we over come it . plizzzzzzzzzzzzzzz help me in this
Riyad

In your code, searching a tree costs O(n) and inserting costs O(1).

But, you can do binary searching to reach O(logn) in searching and doing inserting with O(n).

It is likely the latter will be faster, since you'll have only 10,000 insertings and 1,000,000 searchings.

Hope this helps!

ram wrote:I also used STL for solving this problem. But getting a TLE. Is anything wrong with the input or our algo?

I also got TLE when using <string>. After changing strings to char* I got Acc in 6 sec. And I had my own hash table.

hey i tried to use the binary search tree to solve the prob as u said me to do . but it is fetching me wa . what did i do wrong , icant find it out . so can u plizzzzzzzzzzzzzz help me in this .
here is my code for 10226 . pliz help me in this .

[c]#include<stdio.h>
#include<string.h>
#include<ctype.h>
#include<stdlib.h>

#define MAXWORD 50

long int Total;

struct tnode {
char *word;
int count ;
struct tnode *left;
struct tnode *right;


};

struct tnode * talloc(void);
char * strdup(char *);
struct tnode * addtree(struct tnode*,char *);
void treeprint(struct tnode*);
void FreeTree(struct tnode *);



int main(){
struct tnode * root;

char word[MAXWORD];

long int mcount ;

scanf("%ld",&mcount);
getchar();
while(mcount>0L){
root=NULL;
Total=0L;
while(gets(word)){
Total++;
root=addtree(root,word);

}
treeprint(root);
printf("\n");
FreeTree(root);

mcount --;
}

return 0;
}


struct tnode* addtree(struct tnode* p , char * w){
int cond;
if(p==NULL){

p=talloc();
p->word=strdup(w);
p->count=1;
p->left=p->right=NULL;

}
else if((cond=strcmp(w,p->word))==0)
p->count++;
else if(cond<0)
p->left=addtree(p->left,w);
else
p->right=addtree(p->right,w);

return p;


}

void treeprint(struct tnode *p){

if(p!=NULL){
treeprint(p->left);
printf(p->word);
printf(" %.4lf\n",(double)((double)(p->count)/(double)(Total))*100.00);
treeprint(p->right);


}


}

struct tnode *talloc(void){
return (struct tnode *) malloc(sizeof(struct tnode));
}

char * strdup(char *s){
char *p;
p=(char *) malloc(strlen(s)+1);

if(p!=NULL)
strcpy(p,s);
return p;

}

void FreeTree(struct tnode *t)
{
if(t==NULL)return;
if(t->left!=NULL)FreeTree(t->left);
if(t->right!=NULL)FreeTree(t->right);

free(t);
}[/c]

regards
riyad

My code causes TLE. I cannot find out the reason. I used Quick sort algorithm to sort the tree names and then start scan though the list and keep counting. It doesn't require any searching algorithm. But it causes mysterious TLE. Can somebody find out the problem?
My code is given below
[c]
#include<stdio.h>
#include<string.h>
void Qsort(long p, long r);
long Partition(long p, long r);


struct list{
char tree[32];
};
struct list forest[1000000];
/*FILE *fp;*/

main()
{
long i,n,len,count,N,c,j;
char str[32],ch;
/*fp = fopen("10226.txt","r");*/

fscanf(stdin,"%ld",&N);

while(N>0)
{
i=0;
count = 0;
while(1)
{
fgets(forest.tree,32,stdin);
if(strcmp(forest.tree,"\n")==0 && i==0)
continue;
else if(strcmp(forest.tree,"\n")==0)
break;
else
{
forest.tree[strlen(forest.tree)-1]='\0';
count = 0;
}
++i;
}

n=i;
Qsort(0,n-1);
count = 1;
strcpy(str,forest[0].tree);
for(i=1;i<=n;++i)
{
if(strcmp(str,forest.tree)==0)
{
++count;
continue;
}
else
{
printf("%s %0.4f\n",str,(count*100.0)/n);
strcpy(str,forest.tree);
count = 1;
}
}
printf("\n");
--N;
}
}

void Qsort(long p, long r)
{
long q;
if(p<r)
{
q = Partition(p,r);
Qsort(p,q);
Qsort(q+1,r);
}
}
long Partition(long p, long r)
{
struct list x,temp;
long i,j;

strcpy(x.tree,forest[p].tree);

i = p-1;
j = r+1;
while(i<=j)
{
do {
--j;
}while(strcmp(forest[j].tree,x.tree)>0);
do {
++i;
}while(strcmp(forest.tree,x.tree)<0);

if(i<j)
{
temp = forest;
forest=forest[j];
forest[j]=temp;
}

else
return j;
}

}

[/c]

Might want to reconsider this..

Well Larry.......you adviced me to check the input portion....well, but it works fine with my sample input file and generates correct output. If you see carefully, you can realize it can handle more than one blang line between two dataset. Well.......thanks for your reply......i am trying to take input character by character.
Hope for the best

I use the following code so that float are output as specified in problem 10226, e.g. 3.1416 for pi.

[cpp]
cout.flags(ios_base::fixed | ios_base::showpoint);
cout.precision(4);
[/cpp]

I have included iostream and iomanip, and am using namespace std. This compiles fine with g++ (GCC) 3.2.2 (Mandrake Linux 9.1 3.2.2-3mdk).

Any idea what is going on? And how can I fix that using C++ library routines?

Thanks,

David.

I've already answered to similar questions several times. Just search the board. It's much faster than waiting for someone to reply.

For each tree name, you scan the whole list of species. So assuming that you have S species, and are reading N names, of length L, then your complexity is roughly N*M*L. Now, if S = 10,000, N = 1,000,000, and L=30, there is no wonder that you get time limit exceeded.

Note that even if you maintain the list of species ordered, then your complexity will be roughly log S * N * L; which is still too much, I think for the judge test cases.

I have only managed to get an accepted when I made my solution linear in the size of the input, that is N * L.

Best luck,

David.
--

For each tree name, you scan the whole list of species. So assuming that you have S species, and are reading N names, of length L, then your complexity is roughly N*M*L. Now, if S = 10,000, N = 1,000,000, and L=30, there is no wonder that you get time limit exceeded.

Note that even if you maintain the list of species ordered, then your complexity will be roughly log S * N * L; which is still too much, I think for the judge test cases.

I have only managed to get an accepted when I made my solution linear in the size of the input, that is N * L.

Best luck,

David.

The search in a map container is too expensive (linear). As you may have as much as 1,000,000 searches in a map of up to 10,000 you exceed the time limits. I am not sure that the compiler accepts hash_map, but it should significantly decrease the execution time.

Best luck,

David.

Thanks for pointing this to me. I enlarged the scope of my search and finally find some pieces of answers. I wonder if there is a web page where the "features" of the current C++ compiler are exhaustively documented.

Cheers,

David.
--

OK, I got that. But the question remains: Why? It's more obscure and, although valid, Stroustrup himself uses the short form. Additionally
[cpp]
std::cout << std::setw(3) << std::ios::right << 3 << std::endl;
[/cpp]
produces some very nasty things: which is not quite what I would expect. So Why is the short form not accepted?

Thx for replies, Hagen.