704  Colour Hash
Moderator: Board moderators
704  Colour Hash
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)
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)

 Experienced poster
 Posts: 167
 Joined: Fri Oct 19, 2001 2:00 am
 Location: Saint Petersburg, Russia
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
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
What do I do?
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.
I've tryied IDA*, dfs and bfs, but couldn't find the solution in time...
Any help is appreciated
JP.
704  Colour Hash
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.
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.
Re: 704 ... Color Hash !!
This is a FAQ in this board.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.
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.

 Learning poster
 Posts: 57
 Joined: Fri Oct 10, 2003 11:01 pm
 Location: in front of PC
 Contact:
Hello
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
so if any one posts here some problem numbers of (nearly) this type yet relatively
easier, would be greatly appriciated.
regards
Rss
704
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:
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[i2+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 CounterClockwise rotation */
else if(rotacion == 3) {
for(i=2;i<12;i++) {
v[i2] = vtmp[i];
}
v[21] = v[9] = vtmp[11];
v[22] = v[10] = vtmp[0];
v[23] = v[11] = vtmp[1];
}
/* 4 Right Wheel CounterClockwise 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[nivel1] == 1) && (s[nivel] == 3)) s[nivel]++;
else if((s[nivel1] == 2) && (s[nivel] == 4)) s[nivel]++;
else if((s[nivel1] == 3) && (s[nivel] == 1)) s[nivel]++;
else if((s[nivel1] == 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;
}
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.
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
HomePage
 little joey
 Guru
 Posts: 1080
 Joined: Thu Dec 19, 2002 7:37 pm