## 127 - "Accordian" Patience

Moderator: Board moderators

bugzpodder
Experienced poster
Posts: 147
Joined: Fri Jun 13, 2003 10:46 pm

### [Resolved] 127 - Accordian Patience (TLE)

My input takes about 7.993 seconds (by commenting out the simulation)
I used gets/cout (printf takes about .5 seconds longer)
with simulation i figure it takes about 18s (using STL stacks+lists)
How on earth does the top ppl get 0.504 time!

can anyone give me hints on improving speed - all i need is a factor of 2 :D? seems there are around 25000 test cases.

[cpp]
#include<cstdio>
#include<iostream>
#include<stack>
#include<list>
using namespace std;

char deck[2000];

list<stack<int > >::iterator li,li2;
int match(int p1,int p2){
return (deck[p1*3]==deck[p2*3] || deck[p1*3+1]==deck[p2*3+1]);
}

int match(list<stack<int> >::iterator li, int n,int &i){
li2=li;
for (int j=0;j<n;j++) li2--;
if (match(li->top(),li2->top())) {
i-=n;
return true;
}
return false;
}

int main(){
int i,cnt=0;
list<stack<int> > v_init(52);
for (i=0,li=v_init.begin();i<52;i++,li++) li->push(i);
list<stack<int> > v;

while(1){
cnt++;
// if (cnt>=20000) cnt/=0;
v=v_init;
gets(deck);
if (deck[0]=='#') break;
gets(&deck[78]);
//Simulation
li=v.begin();
for (i=0;i<v.size();)
if ((i>=3 && match(li,3,i))||(i>=1 && match(li,1,i))){

li2->push(li->top());
li->pop();
if (li->empty())
v.erase(li);
li=li2;
}
else{
i++; li++;
}
cout<<v.size()<<" pile";
if (v.size()>1) cout<<"s";
cout<<" remaining:";
for (i=0,li=v.begin();i<v.size();i++,li++) cout<<" "<<li->size();
cout<<endl;
}
return 0;
}

[/cpp]

1 0:00.504 400 Ivan Golubev C 2003/01/16-08:34:58.951 1336689 (H0)
2 0:00.510 408 Ivor L66bas C 2002/12/22-14:32:35.923 1302795 (H0)
3 0:00.770 392 Ivan Vecerina C 2003/06/16-17:08:35.584 1658948 (H0)
4 0:00.842 8192 Jason Lee C++ 2003/08/27-04:10:19.048 1834082 (H0)
Last edited by bugzpodder on Fri Sep 26, 2003 5:52 pm, edited 1 time in total.
xbeanx
Experienced poster
Posts: 114
Joined: Wed Jul 30, 2003 10:30 pm
Why not implement your own stack? I did, and it only took around 10 lines. That way you are sure that you are doing only what you need.

Really, all you need is a push, pop, and top method. Plus, you can statically allocate the memory needed for the stack of cards, whereas if you use the STL stack, everytime you push something it (may) resize the ientire stack which could take more time.

Also, I used cin to grab input. I don't know if that's any faster than gets.

You are using lists, which are not needed. If you think about it, the maximum number of piles you will ever need is 52 (1 card in each pile), so why not do the following:

[cpp]
class Stack {
char cards[52][2];
...
...
}

main() {
Stack piles[52];
...
...
}
[/cpp]

That way, you can move your piles and cards around freely without having to allocate more memory or resize your stack or whatever.

As for the really quick times.. I don't know how that happened. My program ran in around 4 seconds, which I was quite happy with. The java version I wrote, which used the exact same methods, ran 13 times slower.
UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:
Yes, C++ STL won't cut it with this one (too much overhead). I used a doubly linked list, with input/output buffering [fread and fwrite].
bugzpodder
Experienced poster
Posts: 147
Joined: Fri Jun 13, 2003 10:46 pm
cin: Wrong Answer 0:01.072 C++ 127 - ``Accordian'' Patience
gets: Wrong Answer 0:00.291 C++ 127 - ``Accordian'' Patience

this time, i commented out the line v=v_init (list assignment) as well as simulation and it boosted the time by almost 8 seconds!! I didnt know STL lists would be THAT slow!
bugzpodder
Experienced poster
Posts: 147
Joined: Fri Jun 13, 2003 10:46 pm
UFP2161 wrote:Yes, C++ STL won't cut it with this one (too much overhead). I used a doubly linked list, with input/output buffering [fread and fwrite].
hmm fread? what is the parameter for the file stream? my compiler wont accept stdio ass the file stream.
bugzpodder
Experienced poster
Posts: 147
Joined: Fri Jun 13, 2003 10:46 pm
yes, building your own stack and statically allocate the stacks is definately a good idea. it got me AC after ~3.2s
Ivan Golubev
Experienced poster
Posts: 167
Joined: Fri Oct 19, 2001 2:00 am
Location: Saint Petersburg, Russia
Of course, gets faster than cin, as well as fread faster than gets. About fread parameters -- you can use stdin (and stdout for fwrite). STL, obviously, very slow for this problem because it contains too much unnecessary code (for this problem especially). Own stack routines + own I/O routines are keys to success . Though I've also rewrote almost everything in ASM, Ivor's time shows that it isn't really necessary.
Experienced poster
Posts: 131
Joined: Thu Apr 17, 2003 8:39 am
Location: Baku, Azerbaijan

### 127 Accordian Patience - help

Hello. I need help to understand moves.

Code: Select all

``````AC 2C 3C 4C 5C 6C 7C 8C 9C TC JC QC KC AD 2D 3D 4D 5D 6D 7D 8D TD 9D JD QD KD
AH 2H 3H 4H 5H 6H 7H 8H 9H KH 6S QH TH AS 2S 3S 4S 5S JH 7S 8S 9S TS JS QS KS
#``````
How we can get from here

Code: Select all

``1 pile remaining: 52``
Can you show me how to play first and what to do then? I read the problem statement and did as I understood, by I can't get right answer.
First take AC then put 2C on it the 3C and so on until AD. Put AD in the second pile, 2D on it and so on. But I can't get right answer. What to do?

_____________
NO sigNature
UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:
Deal AC.
Deal 2C. Notice 2C matches AC. Move 2C on top of AC.
Repeat for clubs. First pile has 13 cards, top card being KC.
Deal 2D in third pile. Notice 2D matches AD in second pile. Move 2D on top of AD.
Repeat for diamonds. First pile has 13 clubs [KC]. Second pile has 13 diamonds [KD].
Notice KD matches KC. Move KD on top of KC. First pile has 14 cards [KD]. second pile has 12 cards [QD]. Move all diamonds onto first pile.
Repeat for last two suits.
Experienced poster
Posts: 131
Joined: Thu Apr 17, 2003 8:39 am
Location: Baku, Azerbaijan
OK. now we have

Code: Select all

``AC 2C 3C 4C 5C 6C 7C 8C 9C TC JC QC KC KD QD JD 9D TD 8D 7D 6D 5D 4D 3D 2D AD``
int the first pile.
Then comes AH. We put it on AD and get

Code: Select all

``AC 2C 3C 4C 5C 6C 7C 8C 9C TC JC QC KC KD QD JD 9D TD 8D 7D 6D 5D 4D 3D 2D AD AH``
Then come after AH - 2H,3H,4H,5H,6H,7H,8H,9H,KH
and now we have in the first pile

Code: Select all

``AC 2C 3C 4C 5C 6C 7C 8C 9C TC JC QC KC KD QD JD 9D TD 8D 7D 6D 5D 4D 3D 2D AD AH 2H 3H 4H 5H 6H 7H 8H 9H KH``
Then we put 6S into the second pile, then QH into the third.
TH we put on the first pile and we do this steps until we cannot anymore move a card from pile.

6 piles remaining: 37 5 1 7 1 1

I am wrong of course. Maybe I missunderstood the problem.
If I move a card, is it nessesary do move only the rightmost (the one we deal). Can we move any other card on the top of a center pile? I think the problem must be that.

thx.
_____________
NO sigNature
Experienced poster
Posts: 131
Joined: Thu Apr 17, 2003 8:39 am
Location: Baku, Azerbaijan
Thank you all who just looked here. I've got AC 0:03.734. I'll try to make this time better. I just had to look at the leftmost card, if I can move it.
_____________
NO sigNature
Experienced poster
Posts: 131
Joined: Thu Apr 17, 2003 8:39 am
Location: Baku, Azerbaijan
That is incredible, but I could improve my code and got AC at 0:02.533.
_____________
NO sigNature
chunyi81
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore

### Problem 127 RE

When I submit my program to the OJ, the OJ keep on replying RE, invalid memory reference. My program ran fine on the sample input, giving the correct output. Can someone give me ome sample I/O to test my program? There may be something I missed. Thanks.
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact: