101 - The Blocks Problem

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

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

101-Block Problem--- Time Limit Exceeding

Post by mudda_steven »

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:

Post by yoshiro aoki »

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:

Post by yoshiro aoki »

yoshiro (mark) aoki

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

Help me with 101 (TLE)

Post by blodstone »

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

Post by jeffrey »

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

Post by jeffrey »

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

Post by jeffrey »

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"

Post by scan33scan33 »

I got a lot of WAs for this problem.
And test for a lot of cases and got them right.
So......help me please!

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"

Post by scan33scan33 »

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

or give me some samples, thx.


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

sorry for asking....

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

Re: ACM101 WA "C"

Post by helloneo »

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

sorry for asking....
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

Post by dddolphin »

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

Post by helloneo »

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

Post by dddolphin »

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

Post by ilms »

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){
	int ax,ay,ac,ad,ae;
	for(ax=0;ax<use_box;ax++)
		for(ay=0;ay<box_in[ax];ay++)
			if(box[ax][ay]==index){
				ad=box_in[ax];
				for(ac=ay+1;ac<ad;ac++){
					box_in[ax]--;
					ae=box[ax][ac];
					box[ae][box_in[ae]]=ae;
					box_in[ae]++;
				}
				return;
			}
}
void bb::put(int fb,int tb){
	int ax,ay,ac,ad;
	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++){
					ad=box_in[ax];
					for(ay=0;ay<ad;ay++)
						if(box[ax][ay]==tb){
							box[ax][box_in[ax]]=fb;
							box_in[ax]++;
						}
				}
				return;
			}
}
void bb::put_all(int fb,int tb){
	int ax,ay,ac,ad,ae;
	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++)
					for(ad=0;ad<box_in[ac];ad++)
						if(box[ac][ad]==tb){
							ae=box_in[ax];
							for(ad=ay;ad<ae;ad++){
								box[ac][box_in[ac]]=box[ax][ad];
								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??

SHAHADAT
New poster
Posts: 23
Joined: Thu Jun 22, 2006 8:55 am
Location: sust,bangladesh

101 why pe

Post by SHAHADAT »

cut
Last edited by SHAHADAT on Fri Dec 22, 2006 10:25 am, edited 1 time in total.

Post Reply

Return to “Volume 1 (100-199)”