11035 - Card Hands

[naguib]

I get runtime error

Code: Select all

		for(i=0;i<n;i++)
		{
			fscanf(in,"%d",hands+i);
				for(j=0;j<hands[i];j++)
				{
					fscanf(in,"%s",cstr);
					cards[t++]=tonum(cstr);
				}
		}
		

is this a right way to read input
I checked "cstr" is some times more than 2 chars
is there problem with judge or with my code???

[mf]

The problem statement says that one of the values a card may have is '10', which is two chars.
So yes, some card names may be longer than 2 characters.

[naguib]

stupid me anyway it still gives runtime error

Code: Select all

#include<algorithm>
#include<cstdio>
#include<list>
using namespace std;
FILE *in=stdin;//fopen("hands.in","r");
class node{public:
int i,c;
};
node arr[100009];
char cards[100009];
int hands[100009];
int cum[100009];
bool vis[55];
int n;
void err()
{
	while(1)printf("%s\n",cards);
}  
int tonum(char* c)
{
	int a,b;
	
	if(*c=='J')		b=10;
	else if(*c=='Q')b=11;
	else if(*c=='K')b=12;
	else if(*c=='A')b=0;
	else if(*c=='1')b=9,c[1]=c[2];
	else b=*c-'1';

	if(c[1]=='C')	  a=0;
	else if(c[1]=='D')a=1;
	else if(c[1]=='H')a=2;
	else			  a=3;

	return a*13+b;
}
bool operator < (node a,node b)
{
	return a.c<b.c;
}
bool cmp(char a,char b)
{
	return b<a;
}
int main()
{
	int i,j,k,t=0,ans=0,s,l;
	char cstr[10];
	cards[100008]=0;
	while(1)
	{
		fscanf(in,"%d",&n);
		ans=0;
		if(n==0)return 0;
		t=0;
		l=0;
		for(i=0;i<n;i++)							//reading hands
		{
			fscanf(in,"%d",hands+i);
				for(j=0;j<hands[i];j++)
				{
					fscanf(in,"%s",cstr);
					cards[t++]=tonum(cstr);
				}
		}
		for(i=0;i<n;i++)
			arr[i].i=i,arr[i].c=hands[i],l=max(l,hands[i]);   //storing in a array of class "node"

		cum[0]=0;
		for(i=1;i<n;i++)										//bulding cummulative sum table
			cum[i]=cum[i-1]+hands[i-1];

		sort(arr,arr+n);									//sorting hands  accsendingly on number of cards


		for(i=0;i<n;i++)								//sorting each hand
			sort(cards+cum[i],cards+cum[i]+hands[i],cmp);
		s=0;
		for(i=0;i<l;i++)								//greedy algorithm to count nodes
		{
			memset(vis,0,sizeof(vis));					
			for(j=s;j<n;j++)							//count how many different card in position i of each hand
			{
				if(!vis[cards[cum[arr[j].i]+i]])ans++,vis[cards[cum[arr[j].i]+i]]=1;
				if(arr[j].c-1==i)
					s++;
			}
		}
		printf("%d\n",ans);
	}
}

I know that u probably hates reading others code ,but would u plz help me to find what could cause runtime error

[Jan]

What is the output for the following input set?

Input:

Code: Select all

3
3 7D AH 5S
4 9C 3D 4D 5S
2 AH 5S
3
3 7D AH 5S
4 9C 3D 4D 5S
2 AH 5S
3
4 2D 4D AH 5S
3 3D AH 5S
4 2D 3D AH 5S
2
2 2D 3D
1 2D
3
4 9C 3D 4D 6S
4 9C 3D 4D 5S
3 10C 4D 7S
3
2 10C 10H
2 10C 10S
1 10H
3
3 7D AH 5S
4 9C 3D 4D 5S
3 3D AH 5S
0

Thanks in advance.

[ayon]

anyone please describe your algo, i cant find a good solution

[mf]

I reverse each hand and insert them into a trie.
And then just print the number of nodes in the trie.

To Jan:
I get this output

Code: Select all

6
6
6
3
11
4
7

[ayon]

oh, thats it. i just misunderstood the problem
ok now, i solved the problem,
to mf:
my program takes memory 12MB, while yours less than 2 MB, dont your trie node has 52 pointers? i used
typedef struct rec
{
struct rec *next[52];
} node;
and of course i free the trie everytime.

[mf]

You can implement a trie with just two pointers per node: pointer to node's first child and node's sibling (the node following it in its parent's childs list).

[naguib]

I think I missunderstood the problem would some body reword it with examples

[ayon]

to mf, thank you very much, i didnt know the great idea before.

to naguib:

Code: Select all

for the test case:
3 
3 7D AH 5S 
4 9C 3D 4D 5S 
2 AH 5S

9C-3D-4D
        \
         5S   (only 6 nodes)
        /
   7D-AH

3 
3 7D AH 5S 
4 9C 3D 4D 5S 
3 3D AH 5S

    7D
     \
   3D-AH-5S   (only 7 nodes)
        /
9C-3D-4D

[sohel]

My method was similar to that of mf...
.. but I didn't use any tries.

1] Reverse all the hands.
2] Sort each hand in increasing order of first value, if there is a tie then in order of increasing second value and so on..
3] Set ans = total number of cards
3] Then simply apply plain, old dfs() to reduce the number of common starting cards.

It took 3MB of memory.

[JohnTortugo]

Hi, I know its too late, but I'll apreciate if somebody can give me the correct output for the input case below :

Code: Select all

3
5 6D 7D 8D 9D AH
5 6D 7D 8D 9D AH
5 6D 7D 8D 9D AH
5
5 6D 7D 8D 9D AH
5 6D 7D 8D 9D AH
5 6D 7D 8D 9D AH
4 6D 7D 8D AH
4 6D 7D 8D AH
0

Thank you very much.
John.

[Jan]

My code returns.

Output:

Code: Select all

5
8

Hope it helps.