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

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

[Resolved] 127 - Accordian Patience (TLE)

Post by bugzpodder » Fri Sep 26, 2003 3:00 am

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
Location: Newfoundland, Canada (St. John's)

Post by xbeanx » Fri Sep 26, 2003 1:29 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. :(

User avatar
UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:

Post by UFP2161 » Fri Sep 26, 2003 2:35 pm

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

Post by bugzpodder » Fri Sep 26, 2003 3:01 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

Post by bugzpodder » Fri Sep 26, 2003 3:05 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

Post by bugzpodder » Fri Sep 26, 2003 5:51 pm

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

Ivan Golubev
Experienced poster
Posts: 167
Joined: Fri Oct 19, 2001 2:00 am
Location: Saint Petersburg, Russia

Post by Ivan Golubev » Fri Sep 26, 2003 6:31 pm

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
Experienced poster
Posts: 131
Joined: Thu Apr 17, 2003 8:39 am
Location: Baku, Azerbaijan

127 Accordian Patience - help

Post by Farid Ahmadov » Tue Oct 14, 2003 2:08 pm

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.
_____________
NO sigNature

User avatar
UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:

Post by UFP2161 » Tue Oct 14, 2003 2:53 pm

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
Experienced poster
Posts: 131
Joined: Thu Apr 17, 2003 8:39 am
Location: Baku, Azerbaijan

Post by Farid Ahmadov » Tue Oct 14, 2003 3:19 pm

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.
_____________
NO sigNature

Farid Ahmadov
Experienced poster
Posts: 131
Joined: Thu Apr 17, 2003 8:39 am
Location: Baku, Azerbaijan

Post by Farid Ahmadov » Tue Oct 14, 2003 3:48 pm

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

Farid Ahmadov
Experienced poster
Posts: 131
Joined: Thu Apr 17, 2003 8:39 am
Location: Baku, Azerbaijan

Post by Farid Ahmadov » Tue Oct 14, 2003 4:05 pm

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

Post by chunyi81 » Tue Aug 03, 2004 7:06 am

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.

User avatar
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba » Tue Aug 03, 2004 2:23 pm

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

chunyi81
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore

Post by chunyi81 » Tue Aug 03, 2004 4:45 pm

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

Post Reply

Return to “Volume 1 (100-199)”