127 - "Accordian" Patience

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

Moderator: Board moderators

stcheung
Experienced poster
Posts: 114
Joined: Mon Nov 18, 2002 6:48 am
Contact:

Post by stcheung » Thu Mar 01, 2007 9:30 am

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.

898989
Learning poster
Posts: 83
Joined: Wed Feb 01, 2006 12:59 pm
Location: (Fci-cu) Egypt
Contact:

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

Post by 898989 » Thu Sep 18, 2008 5:16 pm

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.
Sleep enough after death, it is the time to work.
Mostafa Saad

gy_jsj08_sdkd
New poster
Posts: 1
Joined: Fri Jul 30, 2010 2:51 am

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

Post by gy_jsj08_sdkd » Fri Jul 30, 2010 2:56 am

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

camelwombat
New poster
Posts: 1
Joined: Wed Oct 13, 2010 7:28 pm

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

Post by camelwombat » Wed Oct 13, 2010 7:41 pm

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

User avatar
N@$!M
New poster
Posts: 10
Joined: Wed Jan 10, 2007 7:26 pm

Re: 127 ...

Post by N@$!M » Sat Nov 13, 2010 12:26 pm

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.....
"I AM NOT SURE WHETHER I SHOULD BE CONFUSED OR NOT..."
TARIQ M NASIM
CSE 03/04 Batch, SUST, Sylhet- 3114.
==>Software Engineer, Structured Data Systems Limited,Dhaka.
Bangladesh.

e-Mail Address:
tariqmnasim@gmail.com

User avatar
N@$!M
New poster
Posts: 10
Joined: Wed Jan 10, 2007 7:26 pm

Re: 127 ...

Post by N@$!M » Sat Nov 13, 2010 2:13 pm

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
"I AM NOT SURE WHETHER I SHOULD BE CONFUSED OR NOT..."
TARIQ M NASIM
CSE 03/04 Batch, SUST, Sylhet- 3114.
==>Software Engineer, Structured Data Systems Limited,Dhaka.
Bangladesh.

e-Mail Address:
tariqmnasim@gmail.com

nopy
New poster
Posts: 1
Joined: Sun Jun 01, 2014 5:15 am

127 WA

Post by nopy » Sun Jun 01, 2014 5:27 am

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


brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 127 WA

Post by brianfry713 » Wed Jun 11, 2014 9:32 pm

I believe the bug is in your memcpy lines.
Check input and AC output for thousands of problems on uDebug!

rafastv
New poster
Posts: 22
Joined: Tue Jun 19, 2007 3:18 am

Re: 127 - "Accordian" Patience

Post by rafastv » Mon Jun 26, 2017 6:12 pm

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).

Post Reply

Return to “Volume 1 (100-199)”