JOIN
Get Time
forums  Revision History
Search My Post History  |  My Watches  |  User Settings
Forums Algorithm Discussions General Algorithm Discussions Re: Turkish Informatics Olympiad problem Revision History (1 edit)
Re: Turkish Informatics Olympiad problem (response to post by wongiseng)
I coded the problem for N=4 based on misof's hints and after 5 minutes it spit out the same solution as yours. (it can be easily done in roughly 600-800 MB)
Of course there might be potential bugs there.

Code in the edit.
Re: Turkish Informatics Olympiad problem (response to post by wongiseng)
I coded the problem for N=4 based on misof's hints and after 5 minutes it spit out the same solution as yours. (it can be easily done in roughly 600-800 MB)
Of course there might be potential bugs there.

Code in the edit.

// 33 - shortest solution
// 1234 2341 3412 4123 2314 3142 1423 4231 3124 1243 2431 4312 2134 1342 3421 4213 1324 3241 2413 4132 3214 2143 1432 4321
// 1234    1    2    3   14    2    3    1   24    3    1    2  134    2    1    3   24    1    3    2   14    3    2    1
// 1234    5    6    7   89    0    1    2   34    5    6    7  890    1    2    3   45    6    7    8   90    1    2    3
// 123412314231243121342132413214321
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
 
typedef unsigned char uchar;
 
char perm[24][5];
uchar d[24][24];
uchar memo[24][1<<24];
uchar last[24][1<<24];
int rem = 24*(1<<24);
 
uchar go(int node, int was)
{
	if (was == (1<<24)-1) return 0;
	if (memo[node][was] != 0) return memo[node][was]-1;
	uchar s = 120;
	for (int i = 0; i < 24; ++i)
	{
		if (((was>>i)&1)==0)
		{
			uchar ns = d[node][i]+go(i,was|(1<<i));
			if (ns < s)
			{
				s = ns;
				last[node][was] = i;
			}
		}
	}
	memo[node][was] = s+1;
	--rem;
	if ((rem&0xFFFFF) == 0) printf("%d states may remain\n", rem);
	return s;
}
 
int main()
{
	char tmp[5] = "1234";
	for (int i = 0; i < 24; ++i)
	{
		strcpy(perm[i], tmp);
		next_permutation(tmp, tmp+4);
	}
	for (int i = 0; i < 24; ++i)
	{
		for (int j = 0; j < 24; ++j)
		{
			if (i == j) continue;
			if (perm[i][1]==perm[j][0] && perm[i][2]==perm[j][1] && perm[i][3]==perm[j][2]) d[i][j] = 1;
			else if (perm[i][2]==perm[j][0] && perm[i][3]==perm[j][1]) d[i][j] = 2;
			else if (perm[i][3]==perm[j][0]) d[i][j] = 3;
			else d[i][j] = 4;
		}
	}
	memset(last, 127, sizeof last);
	printf("%d\n", go(0,1)+4);
 
	int i = 0, bm = 0;
	while (i != 127)
	{
		printf("%s ", perm[i]);
		bm |= (1<<i);
		i = last[i][bm];
	}
	puts("");
 
	return 0;
}