704 - Colour Hash

All about problems in Volume 7. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

wyvmak
Experienced poster
Posts: 110
Joined: Thu Dec 13, 2001 2:00 am

704 - Colour Hash

Post by wyvmak » Tue Apr 16, 2002 6:36 am

my program used brute force approach, and got Time Limit Exceeded at 30 secs, yet, in the ranklist, there're submissions which allowed running time to be over a minute, it's weird. is it a trick? if yes, how?

nevertheless, on the positive side, i'm thinking how to improve my program to get its running time less than 30 seconds. but, i'm wondering what tricks to play with to achieve 0.08s and 64K memory, that doesn't seem very possible? (at least you seem need some memory for storing)

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

Post by Ivan Golubev » Tue Apr 16, 2002 11:45 am

Don't forget about judge system upgrate. Before January 2001 (AFAIR) time limit was 90 seconds, so it's just an outdated statistics.

And when solution runs faster than 0.090 sec 'memory used' usually measured as 64K. It's just a bug, don't trust this information.

mmammel
New poster
Posts: 11
Joined: Fri Aug 23, 2002 9:42 pm
Location: MD, USA
Contact:

Post by mmammel » Fri Aug 23, 2002 9:46 pm

To reduce the number of positions you need to look at, try searching from the start position and the end position at the same time, and finding a common position in the middle. Make sure to keep track of already visited positions so you don't go in circles -- using a hash value or something.
-Mark

wyvmak
Experienced poster
Posts: 110
Joined: Thu Dec 13, 2001 2:00 am

Post by wyvmak » Sat Aug 24, 2002 2:42 am

one thing about hash value, does it have to be unique for each configuration? if not, what's the way to resolve same hash value?

mmammel
New poster
Posts: 11
Joined: Fri Aug 23, 2002 9:42 pm
Location: MD, USA
Contact:

Post by mmammel » Tue Aug 27, 2002 5:20 am

I use a hash table that can hold 1000000 positions (using lots of memory :) I think you should actually use a prime number as the size...
I generate TWO different hash values for each position (mod 1000000) one is the index to the table and the second is stored in the table as the check value. When you check a position, look in the table at the generated index position and see if its second hash value matches the stored second value. If it is the same, it is very likely to be the same position. If not, you should consider the position new and store the new value in the table -- forgetting the old value. Unfortunately, forgetting values will allow the program to repeat some positions. To use more memory, you could store multiple check values for each indexed position (buckets) and that way not forget any.
-Mark

jpfarias
Learning poster
Posts: 98
Joined: Thu Nov 01, 2001 2:00 am
Location: Brazil
Contact:

What do I do?

Post by jpfarias » Thu Sep 25, 2003 7:59 pm

What is a good approach to solve this one?

I've tryied IDA*, dfs and bfs, but couldn't find the solution in time...

Any help is appreciated :)

JP.

muvee
New poster
Posts: 25
Joined: Sun Sep 05, 2004 12:41 am

704 - Colour Hash

Post by muvee » Tue Dec 21, 2004 3:07 am

Hello guys,

Ive been stumped on this problem for a few days now.

At first I thought I could do this with a bfs or dfs with the only pruning being that I don't do opposite operations in consecutive moves. Hence a 1 can only be followed by a 1,2 or 4 . Hence apart from the first move where there are 4 possibilities, each move would have a a maximum of 3 possibilities.
This leads to a HUGE search space. The only other pruning I can think off is to eliminate 6 consecutive moves of the same type. However I doubt that will improve it much.

I couldn't think of a better algorithm so I just implemented the above and hoped that the sample input would be such that my program would pass it but unfortunately it didn't :x

The ranklist of this problem is interesting. There are some Accepted solutions that have taken 20 seconds. I don't understand. I thought 10 seconds was the absolute maximum across all problems.

Anyway, I also saw Accepted solutions that took under 1 second. If somebody could point me in the right direction, it would be appreciated :)


Thanks.

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Re: 704 ... Color Hash !!

Post by .. » Sun Dec 26, 2004 3:21 pm

muvee wrote:Hello guys,
The ranklist of this problem is interesting. There are some Accepted solutions that have taken 20 seconds. I don't understand. I thought 10 seconds was the absolute maximum across all problems.
This is a FAQ in this board.
All the submissions over 10s were submitted before the upgrade of judge server, at that time the judge is slower so the time limit is longer.

About the problem, in each test case you are also asked to turn it to "final position". The rough idea is, before start processing test cases, your program should cache the configurations that can be reached from final position in certain steps. So when you process each test case, you have to find a shortest path to any cached configuration.
My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    We can learn much more in discussion than reading source code.
  • I HATE testing account.
  • Don't send me source code for debug.

I LIKE GN
Learning poster
Posts: 57
Joined: Fri Oct 10, 2003 11:01 pm
Location: in front of PC
Contact:

Hello

Post by I LIKE GN » Fri Apr 29, 2005 5:13 pm

i know this is really a very hard (at least to me) problem :roll:
so if any one posts here some problem numbers of (nearly) this type yet relatively
easier, would be greatly appriciated.

regards
Rss

Sotek
New poster
Posts: 8
Joined: Mon Jun 05, 2006 12:06 am
Location: Murcia, Spain

704

Post by Sotek » Sun Jun 11, 2006 5:26 pm

I'm trying to solve 704 but I'm gettin time limit.
I'm using an iterative backtracking but I think I cannot optimize it more.

Do you have any idea about solving this problem ?
any other way ?

Thank you in advance :)

This is my code:

Code: Select all

#include <stdio.h>
#include <string.h>

/* Final state of the problema */
int sol[] = {0,3,4,3,0,5,6,5,0,1,2,1,0,7,8,7,0,9,10,9,0,1,2,1};
/* Actual state */
int v[24];

/* Rotates the vector */
void Rotar(int rotacion) {
	int vtmp[24];
	int i;

	/* Get a copy of the actual state */
	memcpy(vtmp, v, sizeof(v));

	/* 1 Left Wheel Clockwise rotation */
	if(rotacion == 1) {
		for(i=0;i<12;i++) {
			v[(i+2)%12] = vtmp[i%12];
		}		
		v[21] = v[9];
		v[22] = v[10];
		v[23] = v[11];		
	}
	/* 2 Right Wheel Clockwise rotation */
	else if(rotacion == 2) {
		for(i=2;i<12;i++) {
			v[i-2+12] = vtmp[i+12];
		}		
		v[22] = vtmp[12];
		v[23] = vtmp[13];
		v[9] = v[21];
		v[10] = v[22];
		v[11] = v[23];
	}
	/* 3 Left Wheel Counter-Clockwise rotation */
	else if(rotacion == 3) {
		for(i=2;i<12;i++) {
			v[i-2] = vtmp[i];
		}		
		v[21] = v[9] = vtmp[11];
		v[22] = v[10] = vtmp[0];
		v[23] = v[11] = vtmp[1];
	}
	/* 4 Right Wheel Counter-Clockwise rotation */
	else if(rotacion == 4) {
		for(i=0;i<12;i++) {
			v[((i+2)%12)+12] = vtmp[(i%12)+12];
		}
		v[12] = vtmp[22];
		v[13] = vtmp[23];
		v[9] = v[21];
		v[10] = v[22];
		v[11] = v[23];
		
	}
}

/* returns 1 if we've found the solution */
int Solucion(int *s) {
	int i;
	for(i=0;i<24;i++) {
		if(s[i] != sol[i]) return 0;
	}
	return 1;
}

/* Generates another level */
void Generar(int nivel, int *s) {		
		/* Undo previous rotation */
		if(s[nivel] == 1) Rotar(3);
		if(s[nivel] == 2) Rotar(4);
		if(s[nivel] == 3) Rotar(1);
		if(s[nivel] == 4) Rotar(2);
		s[nivel]++;
		if(nivel>0) {
			if((s[nivel-1] == 1) && (s[nivel] == 3)) s[nivel]++;
			else if((s[nivel-1] == 2) && (s[nivel] == 4)) s[nivel]++;
			else if((s[nivel-1] == 3) && (s[nivel] == 1)) s[nivel]++;
			else if((s[nivel-1] == 4) && (s[nivel] == 2)) s[nivel]++;
		}
		
		if(s[nivel] <= 4)
		{
			Rotar(s[nivel]);			
		}
}

/* returns 1 if there's no more brothers */

int NoMasHermanos(int nivel, int *s) {
	if(s[nivel] == 4) return 1;
	else return 0;
}

/* Backtracking */
void buscar(int *s) {
	int i, j, nivel = 0, fin = 0;
	/* s = initial solution */
	for(i=0;i<16;i++) s[i] = 0;
	while(nivel>=0) {
		Generar(nivel, s);		
		if(s[nivel] > 4) {
			s[nivel] = 0;	
			nivel--;
			continue;
		}
		if(Solucion(v)) {
			for(j=0;j<=nivel;j++) printf("%d", s[j]);
			printf("\n");
			return;
		}
		else if(nivel<15) {
			nivel++;
		}
		else {
			while(NoMasHermanos(nivel, s) && nivel >= 0 ) {
				Rotar(2);
				s[nivel] = 0;	
				nivel--;				
			}
		
		}
	}
	printf("NO SOLUTION WAS FOUND IN 16 STEPS\n");
}

/* Start */
int main() {
	int s[16];	
	int i, j, casos;
	scanf("%d", &casos);
	for(i=0;i<casos;i++) {
		for(j=0;j<24;j++) {
			scanf("%d", &v[j]);
		}
		if(Solucion(v)) printf("PUZZLE ALREADY SOLVED\n");
		else buscar(s);
	}
	return 0;
}

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Wed Apr 18, 2007 11:37 pm

My idea is similar. I wanted to precalculate the states using hashing, but in my compiler it exceeds memory limit (for 16 moves). So, how to save the states?

Some people solved the problem under .1 second. But my code is way to slow. So, how to speed up?

Thanks in advance.
Ami ekhono shopno dekhi...
HomePage

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. » Thu Apr 19, 2007 4:18 pm

Cache up to 8 steps only can make you use less memory.
My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    We can learn much more in discussion than reading source code.
  • I HATE testing account.
  • Don't send me source code for debug.

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Thu Apr 19, 2007 5:03 pm

Yep. This approach is called 'meet in the middle'. You can precalculate all states reachable from the solution up to such a depth that you can store them in memory. Then, for each case, do a bfs until you hit one of the stored states. It's the same method used for solving Rubick's Cube.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Thu Apr 19, 2007 9:29 pm

Thanks little joey and Lawrence. Got it accepted.
Ami ekhono shopno dekhi...
HomePage

adelar
New poster
Posts: 35
Joined: Wed May 02, 2007 11:48 pm
Location: Brasil

manhatan

Post by adelar » Thu Jun 21, 2007 4:43 pm

Hello,
Manhattan distance work in this problem?
thank in advance.

Post Reply

Return to “Volume 7 (700-799)”