704 - Colour Hash

[wyvmak]

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]

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]

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]

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]

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]

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]

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

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.

[..]

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.

[I LIKE GN]

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

regards
Rss

[Sotek]

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]

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.

[..]

Cache up to 8 steps only can make you use less memory.

[little joey]

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]

Thanks little joey and Lawrence. Got it accepted.

[adelar]

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