127 - "Accordian" Patience

[bugzpodder]

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)

[xbeanx]

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]

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]

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]

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]

yes, building your own stack and statically allocate the stacks is definately a good idea. it got me AC after ~3.2s

[Ivan Golubev]

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.

[Farid Ahmadov]

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?

thank you for your help in advance.

[UFP2161]

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 AD in second pile.
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.

[Farid Ahmadov]

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.

My program gives answer:
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.

[Farid Ahmadov]

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.

[Farid Ahmadov]

That is incredible, but I could improve my code and got AC at 0:02.533.

[chunyi81]

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]

Search the board. I'm sure there were some threads about this problem with sample input.

[chunyi81]

Yes. And it seems you are the best person to approach. However, the link to the input file on your website is broken.