10422 - Knights in FEN

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

Moderator: Board moderators

Whinii F.
Experienced poster
Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea
Contact:

Post by Whinii F. » Wed Aug 06, 2003 11:29 am

Came back with an AC with 0.023 sec :)
Assume you could declare 25!/(12! 12!) array without MLE. But the resulting array only will have VERY few elements, most of them filled with null.

So you can replace them into a hashed set or something. Of course it will cost some time to check if a state has been visited, but it will not matter much since the number of the nodes are so small.

My program uses DFS, but searches not more than 1000 states per input case. :) (checked with an assert())
JongMan @ Yonsei

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Wed Aug 06, 2003 12:22 pm

I know the DFS approach, but I still want to know the BFS implementation...
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

turuthok
Experienced poster
Posts: 193
Joined: Thu Sep 19, 2002 6:39 am
Location: Indonesia
Contact:

Post by turuthok » Wed Aug 06, 2003 8:37 pm

Observer, I lost my code for this one ... but I used BFS approach. As far as I can recall, I started from target state, find possible moves that are one-step away ... I repeated that it until at most 10 steps. I stored each possible move into a hash-list. After this, I just dealt with the inputs, if it's within 10 moves, it must be in my hash list.

-turuthok-
The fear of the LORD is the beginning of knowledge (Proverbs 1:7).

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Wed Aug 06, 2003 9:43 pm

Ya, me too, though I guess it wasn't clear by my last post..

helpless
New poster
Posts: 3
Joined: Mon Oct 20, 2003 5:05 am
Location: bangladesh

Post by helpless » Tue Oct 21, 2003 11:31 am

generate all node from final state to deph 10 ensuring that the last state will not generate again use long(32 bit) data type to store 25 position

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Tue Jan 27, 2004 9:19 am

Thanks all. I finally rewrote my code and got Accepted in 0.008 sec. Not as good as 0.000 sec. of course :wink:
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

jackie
New poster
Posts: 47
Joined: Tue May 04, 2004 4:24 am

10422 WA Confused !

Post by jackie » Tue May 04, 2004 4:32 am

I search the forum but the topic is the time limit. I really don't know why WA?
Can anyone help PLZ? Some test data will work . THKS!

A binary number and the blank position ------- one state

[cpp]#pragma warning(disable:4786)
#include <cstdio>
#include <memory>
#include <cassert>
#include <set>
using namespace std;
set< pair<int,int> >used;
bool finish;
pair<int,int> final;
int best;
const int digit[25] = {16777216,8388608,4194304,2097152,1048576,524288,262144,131072,65536,32768,16384,8192,4096,2048,1024,512,256,128,64,32,16,8,4,2,1};
const int xtran[8] = {-2,-2,-1,-1,1,1,2,2};
const int ytran[8] = {-1,1,-2,2,-2,2,-1,1};

inline bool suit(int a)
{
return a >= 0 && a < 5;
}
void traceBack(int depth,pair<int,int>c)//depth--setps searched
{
assert(c.first > 33554432);
used.insert(c);
if (depth > 9)
return;
int x = c.second / 5, y = c.second % 5, pattern = c.first;
pair<int,int> next;
for (int i = 0; i < 8; ++i)
{
if (suit(x + xtran) && suit(y + ytran))
{
next.second = (x + xtran) * 5 + y + ytran;
if (digit[next.second] & pattern)
next.first = pattern ^ digit[next.second] ^ digit[x * 5 + y];
else
next.first = pattern;
if (next == final)
{
finish = true;
best = best > depth+1 ? depth + 1 : best;
return;
}
if (used.find(next) == used.end())
traceBack(depth+1,next);
}
}
}

int main()
{
// freopen("10422.in","r",stdin);
int cnt,i,j;
pair<int,int> current;
final.first = 66554912;//11111; 01111; 00011 00001 00000
final.second = 12;
char input[6];
scanf("%d",&cnt);
getchar();
for (NULL; cnt--; NULL)
{
best = 12;
used.clear();
finish = false;
current.first = 1;
for (i = 0; i < 5; ++i)
{
gets(input);
assert(strlen(input) == 5);
for (j = 0; j < 5; ++j)
{
if (input[j] == ' ')
current.second = 5 * i + j;
if (input[j] == '1')
current.first = (current.first << 1) | 1;
else
current.first <<= 1;
}
}
traceBack(0,current);
assert(used.size() < 100000);
if (!finish)
printf("Unsolvable in less than 11 move(s).\n");
else
printf("Solvable in %d move(s).\n",best);
}
return 0;
}[/cpp]

jackie
New poster
Posts: 47
Joined: Tue May 04, 2004 4:24 am

Post by jackie » Tue May 04, 2004 4:09 pm

Seems no one is interested !
:-?
Now i find the used <set> is wrong ,but it too slow .

May be two way BFS will work.

It's some task tomorrow.

jackie
New poster
Posts: 47
Joined: Tue May 04, 2004 4:24 am

Post by jackie » Wed May 05, 2004 8:25 am

Now make it one word.

[cpp]Method Time (second) Memory States checked
TraceBack >7 >5M nearly 1000000
BFS(from begin to end) >4 >4M >100000
BFS(from end to begin) >2 >2M >10000
BFS(both way) 0.031 64K <2000[/cpp]

Not very precise but we know the efficiency.

JackDaniels
New poster
Posts: 8
Joined: Mon Aug 11, 2003 4:51 pm
Location: Suceava, Romania

10422

Post by JackDaniels » Tue Apr 12, 2005 11:11 pm

I'm stuck . I don't know what's wrong. I've solved this problem with DFS first, then with BFS. WA for both...

PLEASE give me some inputs & outputs.

These are inputs & outputs obtained with my code:

Code: Select all

input
4
01011
110 1
01110
01010
00100
10110
01 11
10111
01001
00000
11111
01111
00 11
00001
00000
11111
01111
00110
00001
000 0

output:
Unsolvable in less than 11 move(s).
Solvable in 7 move(s).
Solvable in 0 move(s).
Solvable in 3 move(s).
Nothing is lost because everything is transforming.

JackDaniels
New poster
Posts: 8
Joined: Mon Aug 11, 2003 4:51 pm
Location: Suceava, Romania

Post by JackDaniels » Wed Apr 13, 2005 2:36 pm

Should I post my code? Would that help you helping me? Anyway my code is quite huge, say 250 lines!
Nothing is lost because everything is transforming.

Emilio
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain

Post by Emilio » Sat Apr 16, 2005 5:25 am

Hello,

my AC program gives the next output:

Code: Select all

Unsolvable in less than 11 move(s).
Unsolvable in less than 11 move(s).
Unsolvable in less than 11 move(s).
Unsolvable in less than 11 move(s).
I solved with simple DFS.

Good luck!

JackDaniels
New poster
Posts: 8
Joined: Mon Aug 11, 2003 4:51 pm
Location: Suceava, Romania

Post by JackDaniels » Sat Apr 16, 2005 10:52 am

Finally I've got AC.
I've solved the problem using BFS and an optimising function wich counts how many knights aren't on their final place. The runtime was 0.035 seconds... pretty good.
Emilio, are you sure you've got those outputs for my inputs, with your AC program? cause my AC program does not give that answer.
Nothing is lost because everything is transforming.

Emilio
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain

Post by Emilio » Sat Apr 16, 2005 4:56 pm

Emilio, are you sure you've got those outputs for my inputs, with your AC program?
Yes, even I sent my code yesterday another time for confirming that was correct and I obtained AC (You can see my statistics http://acm.uva.es/cgi-bin/OnlineJudge?A ... 45242:Back), I sent it because I tought that was strange the output for my code. My code works fine, I think, it not prune its method is brute force. Maybe your code or mine is incorrect, but are AC :D

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by Sedefcho » Fri Jun 17, 2005 1:35 pm

Solvable in 0 move(s).
Solvable in 3 move(s).

These last two answers from JackDaniels are obviously OK
( I mean OK from logical point of view and not from Judge's
points of view ).

Emilio's answers for these two cases are logically wrong.

It's pretty interesting what the Judge Test Inputs are.

Post Reply

Return to “Volume 104 (10400-10499)”