Page 6 of 6

Posted: Thu Mar 01, 2007 9:30 am
by stcheung
I wanna share some thoughts after struggling with this problem for 2 chilly nights. Gosh this problem isn't called "Accordian" Patience for nothing. I don't know what Accordian means but I definitely see where the word Patience comes from. I originally got a PE and was satisfied. Then I lost the code and tried doing it again for AC.

Here is what happened. I started off with the STL <stack> and <vector> approach (stack to simulate each pile and vector to keep track of the list of piles) and got TLE. Then I read the posts and realized 2 things. First is that STL is just too slow and so you want to implement your own Stack class. Second is that the input is enormous. I was using cin and just reading the OJ input would take like 3-4 seconds already.

With that said, I improved the IO by using scanf("%s") and that can read the OJ input in about 1 second. I also tried implementing my Stack class and that was easy. Then my nightmare began. I started having trouble dealing with array of class pointers. I also started getting memory leaks! So after some very painful debugging I gave up, and also realized the Stroustrup book just isn't useful when you need to look up the quick answer sometimes.

Now here's what I really want to say. Solving this problem within 10 seconds is definitely achievable even without all these fancy data structures and classes. My final AC took 4sec (1sec went to IO). I didn't use any fancy thing like list or stack. I only have a 2-dimensional [52][52]array to simulate the 52 piles, each holding up to 52 cards. So now you must be asking what I do when a pile is empty. Well basically I would just skip over it when I am looking up the card 3 or 1 piles to the left. This is probably the only part in my code that isn't straightforward, since the straightforward way would be to copy the cards over the empty pile.

So my 2 takeaways are (1) if you really get stuck (whether it's TLE or WA), sometimes re-implementing your solution differently might be faster than trying to troubleshoot and (2) sometimes a really dumb solution works better than you think.

Re: #127, if you get AC, please try this input

Posted: Thu Sep 18, 2008 5:16 pm
by 898989
Hi all, I need some help in this problem, I am suffering from TLE.

My code use only arrays, and i implement double linked list ( using 2 arrays L, R). I also use scanf, printf.
What else I can do?!!!! Please if any one has Hints, I will be happy.


Edit: Passed 1.3s, I called function f(str a, str b) to check if they were same, try to avoid such things.

Re: #127, if you get AC, please try this input

Posted: Fri Jul 30, 2010 2:56 am
by gy_jsj08_sdkd
Why he told me "Time limit exceeded"?Please save me :x Thanks

Code: Select all

#include <stdio.h>
#include <string.h>
struct Card
{
	char card[52][3];
	int card_num;
};
Card PKCard[52];
void DealPK();
int CardCompare(char c1[3],char c2[3]);
int main()
{
    //freopen("127in.txt", "r", stdin);
    //freopen("127out.txt", "w", stdout);
	int i;
	while (1==1)
	{
		for (i=0;i<52;i++)
		{
			scanf("%s",PKCard[i].card[0]);
			if (PKCard[i].card[0][0]=='#') return 0;
			PKCard[i].card_num=1;
		}
		DealPK();
	}
	return 0;
}
int CardCompare(char c1[3],char c2[3])
{
	if (c1[0]==c2[0]||c1[1]==c2[1]) return 1;
	else return 0;
}
void DealPK()
{
	int i,j,swap,k,count;
	swap=1;
	while (swap)
	{
		swap=0;
		for (i=0;i<52;i++)
		{
			count=0;
			for (j=i-1;j>=0&&!swap;j--)
				if (PKCard[j].card_num>0)
				{
					count++;
					if (count==3&&CardCompare(PKCard[i].card[PKCard[i].card_num-1],PKCard[j].card[PKCard[j].card_num-1]))
					{
						strcpy(PKCard[j].card[PKCard[j].card_num],PKCard[i].card[PKCard[i].card_num-1]);
						PKCard[j].card_num++;
						PKCard[i].card_num--;
						swap=1;
						break;
					}
					if (count==3) break;
				}
			count=0;
			for (j=i-1;j>=0&&!swap;j--)
				if (PKCard[j].card_num>0)
				{
					count++;
					if (count==1&&CardCompare(PKCard[i].card[PKCard[i].card_num-1],PKCard[j].card[PKCard[j].card_num-1]))
					{
						strcpy(PKCard[j].card[PKCard[j].card_num],PKCard[i].card[PKCard[i].card_num-1]);
						PKCard[j].card_num++;
						PKCard[i].card_num--;
						swap=1;
						break;
					}
					if (count==1) break;
				}
			if (swap) break;
		}
	}
	count=0;
	for (i=0;i<52;i++)
		if (PKCard[i].card_num>0)
			count++;
	if (count==1) printf("1 piles remaining: 52\n");
	else
	{
		printf("%d pile remaining: ",count);
		k=0;
		for (i=0;i<52;i++)
			if (PKCard[i].card_num>0)
			{
				k++;
				if (k<count) printf("%d ",PKCard[i].card_num);
				if (k==count) printf("%d\n",PKCard[i].card_num);
			}
	}
}

Re: #127, if you get AC, please try this input

Posted: Wed Oct 13, 2010 7:41 pm
by camelwombat
TLE??????????WHO CAN SAVE ME ????????
save me!!!!!!!!!!!!!!!111


#include<cstdio>
#include<stack>
#include<string>
using namespace std;
int main()
{
int i,j;
char card[2];
while(1)
{
stack<string> pile[53];
scanf("%s",card);
if(card[0]=='#') return 0;
string temp=card;
pile[1].push(temp);

for(i=2;i<=52;i++)
{
scanf("%s",card);
temp=card;
pile.push(temp);
}
for(i=1;i<=52;)
{

string a,b;

if(i==1 || pile.empty()) {i++;continue;}

a=pile.top();
int num=0,k=0,t=0;
if(i>=4)
{

for(j=i-1;j>=1;j--)
{
if(!pile[j].empty())
num++;
if(num==3) {t=j;break;}

}

if(t>=1 && t!=i)
{
b=pile[t].top();
if(a[0]==b[0] || a[1]==b[1])
{
pile[t].push(a);
pile.pop();
i=t;
continue;
}

}
}
for(j=i-1;j>=1;j--)
{
if(!pile[j].empty())

{k=j;break;}

}
if (k>=1 && k!=i)
{
b=pile[k].top();
if(a[0]==b[0] || a[1]==b[1])
{
pile[k].push(a);
pile.pop();
i=k;
continue;

}


}
i++;//


}

int total=0;
for(i=1;i<=52;i++)

if(!pile.empty()) total++;
if(total==1) printf("1 pile remaining: 52");
else
{
printf("%d piles remaining:",total);
for(i=1;i<=52;i++)
if(!pile.empty()){ printf(" %d",pile.size());}
}
printf("\n");
}
return 0;
}

Re: 127 ...

Posted: Sat Nov 13, 2010 12:26 pm
by N@$!M
I also had started with STL stack & vector like stcheung and got TLE.
Then I used a data structure like:

Code: Select all

struct pile{
	char card[52][2];	
	int top;
} piles[52];
I just skipped the empty piles while traversing.
though it took 1.552 sec , but I got Accepted. :wink:
Now I am trying to improve the efficiency of the code.....

Re: 127 ...

Posted: Sat Nov 13, 2010 2:13 pm
by N@$!M
I just added two arrays next[52] and prev[52] for each piles and used those in the previous code. Now its Runtime is 0.256 sec that places me within the Top 20 List for this problem. And I am satisfied with this. :D

127 WA

Posted: Sun Jun 01, 2014 5:27 am
by nopy
I have test many inputs but I still got WA.

Code: Select all


#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<string>
#include<cstring>
#include<algorithm>
#include<queue>
#include<climits>
#include<stack>
#include<map>
using namespace std;

char dui[55][55][3];
int z[55];
int k;
void dfs(int cur)
{
    if(cur>=k)return;
    int i=cur;
    if(i-3>=0)
        if(dui[i][z[i]-1][0]==dui[i-3][z[i-3]-1][0]  ||  dui[i][z[i]-1][1]==dui[i-3][z[i-3]-1][1])
        {
         
            strcpy( dui[i-3][z[i-3]],dui[i][z[i]-1]);


            z[i]--;
            z[i-3]++;
            if(z[i]==0)
            {

                memcpy(dui[i],dui[i+1],(51-i)*sizeof(dui[i]));
                memcpy(&z[i],&z[i+1],(51-i)*sizeof(z[i]));

                k--;
            }

            dfs(i-3);
            return;
        }
    if(i-1>=0)
        if(dui[i][z[i]-1][0]==dui[i-1][z[i-1]-1][0]  ||  dui[i][z[i]-1][1]==dui[i-1][z[i-1]-1][1])
        {
            strcpy(dui[i-1][z[i-1]],dui[i][z[i]-1]);
            z[i]--;
            z[i-1]++;
            if(z[i]==0)
            {
                memcpy(dui[i],dui[i+1],(51-i)*sizeof(dui[i]));
                memcpy(&z[i],&z[i+1],(51-i)*sizeof(z[i]));
                k--;
            }
            dfs(i-1);
            return;
        }
    dfs(i+1);
}
int main()
{
   // freopen("in.txt","r",stdin);
    while(scanf("%s",dui[0][0])!=EOF)
    {
        if(dui[0][0][0]=='#')break;
        z[0]=1;
        k=52;
        for(int i=1;i<52;i++)
        {
            z[i]=1;
            scanf("%s",dui[i][0]);
        }

        dfs(0);
        if(k<=1)
            printf("1 pile remaining:");
        else
            printf("%d piles remaining:",k);
        for(int i=0;i<k;i++)
        {
            printf(" %d",z[i]);
        }
        printf("\n");
    }
    return 0;
}


Re: 127 WA

Posted: Wed Jun 11, 2014 9:32 pm
by brianfry713
I believe the bug is in your memcpy lines.

Re: 127 - "Accordian" Patience

Posted: Mon Jun 26, 2017 6:12 pm
by rafastv
It took me more time than needed, just remember as a tip that you must move only ONE card from the piles in a movement. I don't know why I thought you needed to move the whole pile (but sometimes you do).