127  "Accordian" Patience
Moderator: Board moderators
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 34 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 2dimensional [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 reimplementing your solution differently might be faster than trying to troubleshoot and (2) sometimes a really dumb solution works better than you think.
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 34 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 2dimensional [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 reimplementing your solution differently might be faster than trying to troubleshoot and (2) sometimes a really dumb solution works better than you think.

 Learning poster
 Posts: 83
 Joined: Wed Feb 01, 2006 12:59 pm
 Location: (Fcicu) Egypt
 Contact:
Re: #127, if you get AC, please try this input
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.
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
Mostafa Saad

 New poster
 Posts: 1
 Joined: Fri Jul 30, 2010 2:51 am
Re: #127, if you get AC, please try this input
Why he told me "Time limit exceeded"?Please save me 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=i1;j>=0&&!swap;j)
if (PKCard[j].card_num>0)
{
count++;
if (count==3&&CardCompare(PKCard[i].card[PKCard[i].card_num1],PKCard[j].card[PKCard[j].card_num1]))
{
strcpy(PKCard[j].card[PKCard[j].card_num],PKCard[i].card[PKCard[i].card_num1]);
PKCard[j].card_num++;
PKCard[i].card_num;
swap=1;
break;
}
if (count==3) break;
}
count=0;
for (j=i1;j>=0&&!swap;j)
if (PKCard[j].card_num>0)
{
count++;
if (count==1&&CardCompare(PKCard[i].card[PKCard[i].card_num1],PKCard[j].card[PKCard[j].card_num1]))
{
strcpy(PKCard[j].card[PKCard[j].card_num],PKCard[i].card[PKCard[i].card_num1]);
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);
}
}
}

 New poster
 Posts: 1
 Joined: Wed Oct 13, 2010 7:28 pm
Re: #127, if you get AC, please try this input
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=i1;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=i1;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;
}
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=i1;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=i1;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 ...
I also had started with STL stack & vector like stcheung and got TLE.
Then I used a data structure like:
I just skipped the empty piles while traversing.
though it took 1.552 sec , but I got Accepted.
Now I am trying to improve the efficiency of the code.....
Then I used a data structure like:
Code: Select all
struct pile{
char card[52][2];
int top;
} piles[52];
though it took 1.552 sec , but I got Accepted.
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.
eMail Address:
tariqmnasim@gmail.com
TARIQ M NASIM
CSE 03/04 Batch, SUST, Sylhet 3114.
==>Software Engineer, Structured Data Systems Limited,Dhaka.
Bangladesh.
eMail Address:
tariqmnasim@gmail.com
Re: 127 ...
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.
"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.
eMail Address:
tariqmnasim@gmail.com
TARIQ M NASIM
CSE 03/04 Batch, SUST, Sylhet 3114.
==>Software Engineer, Structured Data Systems Limited,Dhaka.
Bangladesh.
eMail Address:
tariqmnasim@gmail.com
127 WA
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(i3>=0)
if(dui[i][z[i]1][0]==dui[i3][z[i3]1][0]  dui[i][z[i]1][1]==dui[i3][z[i3]1][1])
{
strcpy( dui[i3][z[i3]],dui[i][z[i]1]);
z[i];
z[i3]++;
if(z[i]==0)
{
memcpy(dui[i],dui[i+1],(51i)*sizeof(dui[i]));
memcpy(&z[i],&z[i+1],(51i)*sizeof(z[i]));
k;
}
dfs(i3);
return;
}
if(i1>=0)
if(dui[i][z[i]1][0]==dui[i1][z[i1]1][0]  dui[i][z[i]1][1]==dui[i1][z[i1]1][1])
{
strcpy(dui[i1][z[i1]],dui[i][z[i]1]);
z[i];
z[i1]++;
if(z[i]==0)
{
memcpy(dui[i],dui[i+1],(51i)*sizeof(dui[i]));
memcpy(&z[i],&z[i+1],(51i)*sizeof(z[i]));
k;
}
dfs(i1);
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;
}

 Guru
 Posts: 5947
 Joined: Thu Sep 01, 2011 9:09 am
 Location: San Jose, CA, USA
Re: 127 WA
I believe the bug is in your memcpy lines.
Check input and AC output for thousands of problems on uDebug!
Re: 127  "Accordian" Patience
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).