127 - "Accordian" Patience

[obayashi]

i don't think my code will gimme TLE...
any one help pls
thx in advance

[cpp]
#include <iostream>
#include <string.h>
#include <list>
using namespace std;
typedef struct {
char c[2];
} card_t;
typedef struct {
list<card_t> card;
} stack_t;
list<stack_t> li;
char str[1000],tmp[1000],*p;
bool input () {
card_t cd;
stack_t *st;
cin.getline(str,999);
if (strchr(str,'#'))
return false;
cin.getline(tmp,999);
strcat(str," ");
strcat(str,tmp);
li.clear();
for (int i=0;i<3;i++) {
st = new stack_t;
st->card.clear();
li.push_back(*st);
delete st;
}
p = strtok(str," \t\b\r\n");
while (p) {
cd.c[0] = p[0];
cd.c[1] = p[1];
st = new stack_t;
st->card.push_back(cd);
li.push_back(*st);
p = strtok(NULL," \t\b\r\n");
delete st;
}
return true;
}
inline void getPre3(list<stack_t>::iterator &cur) {
cur--;cur--;cur--;
}
inline void getPre(list<stack_t>::iterator &cur) {
cur--;
}
void solve () {
bool flag;
list<stack_t>::iterator cur,pre;
card_t tmp;
do {
flag = false;
cur = li.begin();
cur++;cur++;cur++;
for (;cur!=li.end();cur++) {
pre = cur;
getPre3(pre);
if (pre->card.size() &&
(cur->card.back().c[0]==pre->card.back().c[0] ||
cur->card.back().c[1]==pre->card.back().c[1])) {
flag = true;
tmp = cur->card.back();
cur->card.pop_back();
pre->card.push_back(tmp);
if (cur->card.size()==0) li.erase(cur);
break;
} else {
pre = cur;
getPre(pre);
if (pre->card.size() &&
(cur->card.back().c[0]==pre->card.back().c[0] ||
cur->card.back().c[1]==pre->card.back().c[1])) {
flag = true;
tmp = cur->card.back();
cur->card.pop_back();
pre->card.push_back(tmp);
if (cur->card.size()==0) li.erase(cur);
break;
}
}
}
} while (flag);

cout<<(li.size()-3)<<" pile";
if (li.size()>4) cout<<"s";
cout<<" remaining:";
cur = li.begin(); cur++;cur++;cur++;
for (;cur!=li.end();cur++)
cout<<" "<<cur->card.size();
cout<<endl;
}
int main () {
while (input()) {
solve ();
}
return 0;
}
[/cpp]

[Ivan Golubev]

The judge input is large, about 20000 test cases, so you're need to optimize your solution to get AC (your code looks OK from algorithm side). It's better to avoid C++ specifics like 'list' and write your own (simple) implemention of stack/list.

[obayashi]

thanx, problem solved.
i used pure c...

[Ryan Pai]

Ok, so I'm getting a WA for number 127. If anyone knows a reason why, I'd appreciate the help.

[cpp]/* @JUDGE_ID: <My ID> 127 C++ "Simulation" */
#include <iostream>
#include <string>
#include <vector>
#include <queue>

using namespace std;

queue<string> deck; // the cards in order
bool input(); // input the deck
vector<int> play(); // deal a card, then reduce piles
bool play(vector<vector<string> >& v); // looks for reductions
void move(vector<vector<string> >& v,int a,int b); // completes one reduction
void print(vector<int>); // output the pile sizes

int main(){
while(input()){
vector<int> result=play();
print(result);
}
}

bool input(){
for(int i=0;i<52;i++){
string s;
cin>>s;
if(s[0]=='#') return false;
deck.push(s);
}
}

void print(vector<int> v){
cout<<v.size()<<" pile"<<(v.size()>1?"s":"")<<" remaining:";
for(int i=0;i<v.size();i++)
cout<<' '<<v;
cout<<'\n';
}

vector<int> play(){
vector<vector<string> > piles;
while(!deck.empty()){
piles.push_back(vector<string>(1,deck.front()));
deck.pop();
while(play(piles));
}
vector<int> ret;
for(int i=0;i<piles.size();i++)
ret.push_back(piles.size());
return ret;
}

bool match(string a,string b){
return a[0]==b[0] || a[1]==b[1];
}

bool play(vector<vector<string> >& v){
int leftmost=-1;
for(int i=1;i<v.size();i++){
if(i-1>=0 && match(v.back(),v[i-1].back())){
leftmost=i;
break;
}
if(i-3>=0 && match(v.back(),v[i-3].back())){
leftmost=i;
break;
}
}
if(leftmost==-1) return false;
if(leftmost-3>=0 && match(v[leftmost].back(),v[leftmost-3].back()))
move(v,leftmost-3,leftmost);
else
move(v,leftmost-1,leftmost);
return true;
}

void move(vector<vector<string> >& v,int a,int b){
v[a].push_back(v.back());
v.pop_back();
if(v.size()==0){
for(int i=b;i+1<v.size();i++)
v=v[i+1];
v.pop_back();
}
}[/cpp]

[Krzysztof Duleba]

Your bool input() should return true.

Now I'm trying to do the same task and it seems to be very difficult. I posted a program that looked like this:


[cpp]int main()
{
while(cin.peek()!='#')cin.get();
}[/cpp]

It was running for 0.8s! See how many card sets must be in such a big input file!

BTW: how to turn on the code highlighter? Whatever I try, it doesn't work.

[Krzysztof Duleba]

Never mind, I did it, don't know how.

Testing:

[cpp]int main()
{
while(cin.peek()!='#')cin.get();
}[/cpp]

[Krzysztof Duleba]

As for your algorithm, it is correct. I've just got AC and our programs return exactly the same output for a big (> 1.5 MB) random input file. I can place the input and output somewhere if anybody wants.

There is a funny thing about time limit for this task. Anytime my program was running more than 10s I got TLE. On the other hand there are some guys with 30s in the problem statistics. I find it annoying as I spent 30min. trying to improve my code to work 0.2-0.3 s. faster (according to my calculations it was enough). Finally I found a place where decrementation could be replaced by setting value to 0 which gave me AC with 9.7s.

[oriol78]

can anybody help me, plz? and say me why my code produce TLE?
(sorry about my english)
[cpp]
/* @BEGIN_OF_SOURCE_CODE */
/*TLE*/
#include <iostream>
#include <utility>
#include <vector>
using namespace std;

int tractar2(vector<vector<pair<char,char> > > &e)
{
for(int i = 1; i< e.size(); i++)
{
char a = e.back().first, b = e.back().second;
if(i-3 > -1 && (a == e[i-3].back().first || b == e[i-3].back().second))
{
e[i-3].push_back(e.back());
e.pop_back();
if(e.size() == 0)
e.erase(&e);
return tractar2(e);
}
else if(a == e[i-1].back().first || b == e[i-1].back().second)
{
e[i-1].push_back(e.back());
e.pop_back();
if(i-1 == 0)
{
while(!e[1].empty())
{
e[0].push_back(e[1].back());
e[1].pop_back();
}
}
if(e.size() == 0)
e.erase(&e);
return tractar2(e);
}
}
return 0;
}

void tractar(vector<vector<pair<char,char> > > e)
{
int tam;
tractar2(e);
tam = e.size();
cout << tam;
if(tam == 1)
cout << " pile remaining: 52";
else
{
cout << " piles remaining:";
for(int i = 0; i < tam; i++)
cout << " " << e[i].size();
}
cout << endl;

}

int main()
{
vector<vector<pair<char,char> > > e(52, vector<pair<char,char> > (1));
cin >> e[0][0].first;
while(e[0][0].first != '#')
{
cin >> e[0][0].second;
for(int i = 1; i < 52; i++)
cin >> e[i][0].first >> e[i][0].second;
tractar(e);
cin >> e[0][0].first;
}
return 0;
}
/* @END_OF_SOURCE_CODE */
[/cpp]

[Krzysztof Duleba]

Speed up your code by 25% and you'll get AC.

I think that your problem is caused by wrong data structure. Look what happens when e[1] is empty: all the vectors begining with e[2] up to e[e.size()] will be copied one place down. It is too slow to be acceptable.

[oriol78]

i try to solve this problem, but ... TLE again...
[cpp]
/* @BEGIN_OF_SOURCE_CODE */
/* TLE */
#include <iostream>
#include <utility>
#include <vector>
using namespace std;

int tractar2(vector<vector<pair<char,char> > > &e)
{
int iMenys1;
int iMenys3;
int aux;
for(int i = 1; i< e.size(); i++)
{
if(e.size())
{
iMenys1 = i-1;
while(iMenys1 != -1 && !e[iMenys1].size())
iMenys1--;
iMenys3 = i;
for(int i2 = 0; i2<3; i2++)
{
iMenys3--;
if(iMenys3 == -1)
break;
while(iMenys3 != -1 && !e[iMenys3].size())
iMenys3--;
}
char a = e.back().first, b = e.back().second;
if(iMenys3 != -1 && (a == e[iMenys3].back().first || b == e[iMenys3].back().second))
{
e[iMenys3].push_back(e.back());
e.pop_back();
return tractar2(e);
}
else if(a == e[iMenys1].back().first || b == e[iMenys1].back().second)
{
e[iMenys1].push_back(e.back());
e.pop_back();
return tractar2(e);
}
}
}
return 0;
}

void tractar(vector<vector<pair<char,char> > > e)
{
int tam = 0;
tractar2(e);
for(int i = 0; i < 52; i++)
{
if(e.size() != 0)
tam++;
}
cout << tam;
if(tam == 1)
cout << " pile remaining: 52";
else
{
cout << " piles remaining:";
for(int i2 = 0; i2 < 52; i2++)
{
int aux = e[i2].size();
if(aux != 0)
cout << " " << aux;
}
}
cout << endl;

}

int main()
{
vector<vector<pair<char,char> > > e(52, vector<pair<char,char> > (1));
cin >> e[0][0].first;
while(e[0][0].first != '#')
{
cin >> e[0][0].second;
for(int i = 1; i < 52; i++)
cin >> e[0].first >> e[0].second;
tractar(e);
cin >> e[0][0].first;
}
return 0;
}
/* @END_OF_SOURCE_CODE */
[/cpp]

[Krzysztof Duleba]

On a big test of mine my accepted code (with 9.7s ) had 2.218s, your old code 2.718 and new one 2.250. Just a little bit more and you'll do it!

[oriol78]

can you check my speed again plz ?
[cpp]
/* @BEGIN_OF_SOURCE_CODE */
/* TLE */
#include <iostream>
#include <utility>
#include <vector>
using namespace std;

void printar(vector<vector<pair<char,char> > > e, vector<int> tams)
{
cout << "data" << endl;
for(int i = 0; i < 52; i++)
{
for(int j = 0; j < tams; j++)
cout << e[j].first << e[j].second << " ";
cout << "el tamany es de " << tams << endl;
}
}

int tractar2(vector<vector<pair<char,char> > > &e, vector<int> &tams)
{
int iMenys1;
int iMenys3;
//printar(e,tams);
for(int i = 1; i< 52; i++)
{
if(tams)
{
iMenys1 = i-1;
while(iMenys1 != -1 && !tams[iMenys1])
iMenys1--;
iMenys3 = i;
for(int i2 = 0; i2<3; i2++)
{
iMenys3--;
if(iMenys3 == -1)
break;
while(iMenys3 != -1 && !tams[iMenys3])
iMenys3--;
}
char a = e[tams-1].first, b = e[tams-1].second;
if(iMenys3 != -1 && (a == e[iMenys3][tams[iMenys3]-1].first || b == e[iMenys3][tams[iMenys3]-1].second))
{
e[iMenys3][tams[iMenys3]] = e[tams[i]-1];
e[i][tams[i]-1] = e[i][tams[i]];
tams[iMenys3]++;
tams[i]--;
return tractar2(e,tams);
}
else if(a == e[iMenys1][tams[iMenys1]-1].first || b == e[iMenys1][tams[iMenys1]-1].second)
{
e[iMenys1][tams[iMenys1]] = e[i][tams[i]-1];
e[i][tams[i]-1] = e[i][tams[i]];
tams[iMenys1]++;
tams[i]--;
return tractar2(e,tams);
}
}
}
return 0;
}

void tractar(vector<vector<pair<char,char> > > e)
{
int tam = 0;
vector<int> tams(52,1);
tractar2(e, tams);
for(int i = 0; i < 52; i++)
{
if(tams[i] != 0)
tam++;
}
cout << tam;
if(tam == 1)
cout << " pile remaining: 52";
else
{
cout << " piles remaining:";
for(int i2 = 0; i2 < 52; i2++)
{
int aux = tams[i2];
if(aux != 0)
cout << " " << aux;
}
}
cout << endl;

}

int main()
{
vector<vector<pair<char,char> > > e(52, vector<pair<char,char> > (52));
cin >> e[0][0].first;
while(e[0][0].first != '#')
{
cin >> e[0][0].second;
for(int i = 1; i < 52; i++)
cin >> e[i][0].first >> e[i][0].second;
tractar(e);
cin >> e[0][0].first;
}
return 0;
}
/* @END_OF_SOURCE_CODE */
[/cpp]

[Krzysztof Duleba]

Now your code is exactly as fast as mine, but only if I compile it with -O2 option. Witout any optimalisation it takes you more than 14s. to finish the task that I do in 4s. So everything depends on how do the judge compiles our programs.

To be honest, I don't understand your program. Maby you should try stacks instead of vectors? Maby using some pointers along with new/delete operators would come in handy?

[oriol78]

well, i have TLE again, can anybody tell me what kind of structure i need?
plzzzzzzzzzzzzzzzzzz

[bugzpodder]

may i ask what does the utility header do?