## 101 - The Blocks Problem

Moderator: Board moderators

mudda_steven
New poster
Posts: 1
Joined: Wed Sep 13, 2006 7:09 pm

### 101-Block Problem--- Time Limit Exceeding

Iam a newbie and
Iam unable to minimize this code........this is as far as i can go to reduce the complexity of the problem....could u guys please tell me a way in which i can reduce the Time limit.....

Code: Select all

``````#include<iostream>
#include<string.h>
using namespace std;
class Block
{
public:
int value;
int next;
int prev;
Block()
{
value = 0;
next = -1;
prev = -1;
}
Block(int val)
{
value = val;
next = -1;
prev = -1;
}
};
class Operation
{
public:
static Block block[25];
int temp,t,temp1;
Operation()
{

}
static void MakeBlocks()
{
for(int i=0;i<25;i++)
{
block[i].value = i;
}
}

int check(int a,int b)
{
for(t=block[a].value;t != -1;t=block[t].next)
{
if(t==b)
return 0;
}
for(t=block[a].value;t != -1;t=block[t].prev)
{
if(t==b)
return 0;
}
return 1;
}

void Moveofx(int a)
{
temp = block[a].next;
while(temp !=  -1)
{
temp1 = block[temp].next;
block[temp].next = -1;
block[temp].prev = -1;
temp = temp1;
}
}

void MoveToEnd(int a)
{
temp = block[a].value;
while(block[temp].next !=  -1)
{
temp = block[temp].next;
}
}
void MoveOnto(int a,int b)
{
int temp3,temp4;
Moveofx(a);
Moveofx(b);
temp = block[a].prev;
if(temp != -1)
block[temp].next = -1;
block[a].next = -1;
block[a].prev = b;
block[b].next = a;
}

void MoveOver(int a,int b)
{

Moveofx(a);
temp = block[a].prev;
if(temp != -1)
block[temp].next = -1;
block[a].next = -1;
MoveToEnd(b);
block[a].prev = block[temp].value;
block[temp].next = block[a].value;

}

void PileOnto(int a,int b)
{

Moveofx(b);
temp = block[a].prev;
if(temp != -1)
block[temp].next = -1;
block[a].prev = b;
block[b].next = a;

}

void PileOver(int a,int b)
{

MoveToEnd(b);
temp1 = block[a].prev;
if(temp1 != -1)
block[temp1].next = -1;
block[a].prev = b;
block[temp].next = a;

}

void Display(int n)
{
for(int i=0;i<n;i++)
{
temp = i;
if(block[temp].prev != -1)
{
cout<<temp<<": "<<endl;
}
else
if((block[temp].next == -1 ))
{
cout<<temp<<": "<<block[temp].value<<endl;
}
else
{
cout<<temp<<":";
for(;temp !=-1;temp = block[temp].next)
{
cout<<" "<<block[temp].value;
}
cout<<endl;
}
}
}

};
Block Operation::block[25];
int main()
{
int n;
char command[10],oper[10];
int a,b,i;
Operation op = Operation();
Operation::MakeBlocks();
while(cin>>n)
{

for(;;)
{

cin>>command;
if(strcmp(command,"quit")==0)
{
op.Display(n);
break;
}
cin>>a;
cin>>oper;
cin>>b;

if(op.check(a,b) == 0)
continue;
if(strcmp(command,"move")==0)
{
if(strcmp(oper,"onto") ==0)
{
op.MoveOnto(a,b);
}
else
{
op.MoveOver(a,b);
}
}

if(strcmp(command,"pile")==0)
{
if(strcmp(oper,"onto") ==0)
{

op.PileOnto(a,b);
}
else
{

op.PileOver(a,b);
}
}

}

}
}``````
Thanks

yoshiro aoki
New poster
Posts: 21
Joined: Sat Oct 21, 2006 11:50 pm
Contact:
I only looked quickly at your code, so maybe my advice is not the best possible. Of course you can profile the code to find more about where time is spent.
Maybe a hash table would allow quicker determination of where blocks are? I can have an array, 0 - 24, representing blocks. The value of the array elements could be the stack a particular block is in. So, such lookups are in constant time complexity. Will that help you?

I think I will try this problem. It looks very interesting! I hope you can speed up your code and get an accept if you have not already.

Have a nice weekend,
-yoshiro (mark) aoki
yoshiro (mark) aoki

yoshiro aoki
New poster
Posts: 21
Joined: Sat Oct 21, 2006 11:50 pm
Contact:
yoshiro (mark) aoki

blodstone
New poster
Posts: 6
Joined: Sun Nov 19, 2006 5:47 am

### Help me with 101 (TLE)

Can someone help me with my program? The judge keep sending me a TLE but I still don't know where is the problem.

Code: Select all

``````#include <iostream>
#include <list>
#include <sstream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;

int search(list<int> arr[],int n, int target){
list<int>::iterator pos;
for (int i=0;i<n;i++){
pos = find(arr[i].begin(), arr[i].end(), target);
if(pos!=arr[i].end())
return i;
}
return 0;
}
int main(){
freopen("input.in","r",stdin);
freopen("output.out","w",stdout);
int n;
bool first = true;
string word1,word2;
int x,y;
list<int> arr[25];
while(cin >> n){
if (!first) cout << endl;
first = false;
for(int i=0;i<n;i++){
arr[i].push_back(i);
}
while(true){
cin >> word1; if (word1=="quit") break;
cin >> x >> word2 >> y;
if(word1=="move"){
if(word2=="onto"){
int tx = search(arr,n,x);
int tmp,tmp2;
while (arr[tx].back()!=x){
tmp = arr[tx].back();
arr[tmp].push_back(tmp);
arr[tx].pop_back();
}
tmp2 = arr[tx].back();
arr[tx].pop_back();
tx = search(arr,n,y);
while (arr[tx].back()!=y){
tmp = arr[tx].back();
arr[tmp].push_back(tmp);
arr[tx].pop_back();
}
arr[tx].push_back(tmp2);
}
else{
int tx = search(arr,n,x);
int tmp;
while (arr[tx].back()!=x){
tmp = arr[tx].back();
arr[tmp].push_back(tmp);
arr[tx].pop_back();
}
tmp = arr[tx].back();
arr[tx].pop_back();
tx = search(arr,n,y);
arr[tx].push_back(tmp);
}
}            else if(word1=="pile"){
if(word2=="onto"){
int tx = search(arr,n,x);
int tmp;
list<int> smtr;
while (arr[tx].back()!=x){
tmp = arr[tx].back();
smtr.push_back(tmp);
arr[tx].pop_back();
}
tmp = arr[tx].back();
smtr.push_back(tmp);
arr[tx].pop_back();
tx = search(arr,n,y);
while (arr[tx].back()!=y){
tmp = arr[tx].back();
arr[tmp].push_back(tmp);
arr[tx].pop_back();
}
while(!smtr.empty()){
int temp = smtr.back();
arr[tx].push_back(temp);
smtr.pop_back();
}
}
else{
int tx = search(arr,n,x);
int tmp;
list<int> smtr;
while (arr[tx].back()!=x){
tmp = arr[tx].back();
smtr.push_back(tmp);
arr[tx].pop_back();
}
tmp = arr[tx].back();
smtr.push_back(tmp);
arr[tx].pop_back();
tx = search(arr,n,y);
while(!smtr.empty()){
int temp = smtr.back();
arr[tx].push_back(temp);
smtr.pop_back();
}
}
}
}
for(int i=0;i<n;i++){
cout << i << ":";
while (!arr[i].empty()){
cout << " " << arr[i].front() ;
arr[i].pop_front();
}
cout << endl;
}
}
return 0;
}
``````
I used this test case, and it ran fine. Can someone provide me another test case? so I can test my program. Thx in advance

Code: Select all

``````10
move 9 onto 1
quit

11
move 9 onto 1
move 8 over 1
move 7 over 1
move 6 over 1
pile 8 over 6
pile 8 over 5
move 2 over 1
move 4 over 9
quit

24
move 23 onto 1
move 9 over 1
move 22 onto 2
pile 20 over 15
move 16 onto 15
move 22 onto 2
move 11 over 2
move 22 onto 23
move 17 over 15
pile 16 over 23
move 2 over 15
move 3 over 15
move 4 over 15
move 5 over 15
move 6 over 15
move 7 over 15
move 8 over 15
pile 3 onto 22
move 21 onto 9
move 22 over 9
quit``````

jeffrey
New poster
Posts: 6
Joined: Wed Nov 22, 2006 3:54 am
for the 24-block example input you gave, I got

Code: Select all

``````0: 0
1: 1 23
2:
3: 3
4: 4
5: 5
6: 6
7: 7
8: 8
9: 9 21 22
10: 10
11: 11
12: 12
13: 13
14: 14
15: 15 2
16: 16
17: 17
18: 18
19: 19
20: 20
21:
22: 22
23:``````
The submission server is down so I don't know if my program is correct, but does that output match yours?

Things to watch out for is that there are no spaces on the end of a line, and that your output doesn't end with \r or \n.

jeffrey
New poster
Posts: 6
Joined: Wed Nov 22, 2006 3:54 am

### 101... runtime error on the server but not locally using gcc

I'm running gcc 4.0.1. I've also tried gcc 3.4.2. Running in a cygwin or mac os x environment, I do

c++ -o 101 101.cpp

cat input | ./101

This gives me the desired result. However, upon submitting the source to the judge I always get a runtime error. I've tried copying the text to the submission page and also uploading the file. Any ideas about how I can fix this? It seems to me that since the judge is running linux, they're running gcc and the results should be the same. I would search the forum but the forum search is broken. At least "runtime error" gives no results.

jeffrey
New poster
Posts: 6
Joined: Wed Nov 22, 2006 3:54 am
the howto says
Crash - Runtime Error (RE): Your program failed during the execution (segmentation fault, floating point exception...). The exact cause is reported to the user.
But where is it reported? I got no email and my status page doesn't say anything that I can see.

scan33scan33
New poster
Posts: 4
Joined: Mon Dec 04, 2006 5:39 am
Contact:

### ACM101 WA "C"

I got a lot of WAs for this problem.
And test for a lot of cases and got them right.

or give me some samples, thx.

code removed
Last edited by scan33scan33 on Tue Jan 02, 2007 10:48 am, edited 1 time in total.

scan33scan33
New poster
Posts: 4
Joined: Mon Dec 04, 2006 5:39 am
Contact:

### Re: ACM101 WA "C"

[quote="scan33scan33"]I got a lot of WAs for this problem.
And test for a lot of cases and got them right.

or give me some samples, thx.

I got an AC use C compiler...................
I previously chose C++........

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

### Re: ACM101 WA "C"

scan33scan33 wrote:
I got an AC use C compiler...................
I previously chose C++........

Congratulation..~!

If you got AC, then remove your code..

dddolphin
New poster
Posts: 3
Joined: Fri Dec 15, 2006 10:16 am

### 101: understand the problem

HI, I have problem understanding the process. Let me put my understanding to the following example:

the sample output from the webpage is:
0: 0//an space before first zero and also second 0??
1: 1 9 2 4
2:
3: 3
4:
5: 5 8 7 6
6:
7:
8:
9://if there is a '\n' here, does it matter?

if I continue to
move 7 onto 9, result would be:
0: 0
1: 1 9 7
2: 2
3: 3
4: 4
5: 5 8
6: 6
7:
8:
9:

Or, if I
move 7 over 9, result would be:
0: 0
1: 1 9 2 4 7
2:
3: 3
4:
5: 5 8
6: 6
7:
8:
9:

Or, if I
pile 7 onto 9, result would be:
0: 0
1: 1 9 7 6
2: 2
3: 3
4: 4
5: 5 8
6:
7:
8:
9:

Or, if
pile 7 over 9, result would be:
0: 0
1: 1 9 2 4 7 6
2:
3: 3
4:
5: 5 8
6:
7:
8:
9:

Anyone can help?

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea
There are a lot of threads on this problem..
You have to search first..
If you need to post, use one of the old one to post instead of creating new one..

Check this out..
http://online-judge.uva.es/board/viewtopic.php?t=4019

dddolphin
New poster
Posts: 3
Joined: Fri Dec 15, 2006 10:16 am

### Solved--Thanks

the above processing is correct.

but still encounter presentation error

ilms
New poster
Posts: 2
Joined: Fri Dec 15, 2006 6:20 pm

### q101 where is my wrong

this is my code

Code: Select all

``````#include <iostream>
#include <string>
#include <cstdlib>
using namespace std;
class bb{
private:
int box[25][25];
int box_in[25];
public:
int use_box;
void re_set();
void re_put(int index);
void put(int fb,int tb);
void put_all(int fb,int tb);
void show();
};
bb sbox;
int main(){
string da,db;
int ia,ib;
re_start:
cin>>ia;
sbox.use_box=ia;
sbox.re_set();
re_run:
cin>>da;
if(da=="quit"){
err_go:
sbox.show();
goto re_start;
}else if(cin>>ia>>db>>ib){
if(ia!=ib){
if(da=="move"){
if(db=="onto"){
sbox.re_put(ia);
sbox.re_put(ib);
sbox.put(ia,ib);
}
if(db=="over"){
sbox.re_put(ia);
sbox.put(ia,ib);
}
}else if(da=="pile"){
if(db=="onto"){
sbox.re_put(ib);
sbox.put_all(ia,ib);
}
if(db=="over"){
sbox.put_all(ia,ib);
}
}
}
goto re_run;
}
return 0;
}
void bb::re_set(){
int ax,ay;
for(ax=0;ax<25;ax++)
for(ay=0;ay<25;ay++){
box[ax][ay]=ax;
box_in[ax]=1;
}
}
void bb::re_put(int index){
for(ax=0;ax<use_box;ax++)
for(ay=0;ay<box_in[ax];ay++)
if(box[ax][ay]==index){
box_in[ax]--;
ae=box[ax][ac];
box[ae][box_in[ae]]=ae;
box_in[ae]++;
}
return;
}
}
void bb::put(int fb,int tb){
for(ax=0;ax<use_box;ax++)
for(ay=0;ay<box_in[ax];ay++)
if(box[ax][ay]==fb){
box_in[ax]--;
for(ac=ay;ac<use_box;ac++){
box[ax][ac]=box[ax][ac+1];
}
for(ax=0;ax<use_box;ax++){
if(box[ax][ay]==tb){
box[ax][box_in[ax]]=fb;
box_in[ax]++;
}
}
return;
}
}
void bb::put_all(int fb,int tb){
for(ax=0;ax<use_box;ax++)
for(ay=0;ay<box_in[ax];ay++)
if(box[ax][ay]==fb)
for(ac=0;ac<use_box;ac++)
ae=box_in[ax];
box_in[ax]--;
box_in[ac]++;
}
return;
}
}
void bb::show(){
int ax,ay;
for(ax=0;ax<use_box;ax++){
cout<<ax<<":";
for(ay=0;ay<box_in[ax];ay++){
cout<<" "<<box[ax][ay];
}
cout<<endl;
}
}

``````
i send my code to server.
the server show message "Output Limit Exceeded".
where is my worng??