11214 - Guarding the Chessboard

[sunny]

some hints to optimize it.

[LithiumDex]

(Oops... last time I was here there wasn't a post, ah well... might as well delete my old one)

I'm getting WA.. can someone explain why my algorithm won't work?

It is..

minQueens = 0
While boardNotEmpty:
PlaceQueenWhichEliminatesLargestNumberOfX's
EliminateX'sForThatQueen
minQueens ++
Loop.

Judging by the times of the other submissions, and the time of my WA -- I'm guessing my greedy algorithm is wrong, I'd like to know why though...

If it is infact wrong, would branching when there are multiple best-placed-queens help? hmm...

P.S.

Input:

Code: Select all

8 8
XXXXXXXX
XXXXXXXX
XXXXXXXX
XXXXXXXX
XXXXXXXX
XXXXXXXX
XXXXXXXX
XXXXXXXX
8 8
X.......
.X......
..X.....
...X....
....X...
.....X..
......X.
.......X
9 2
XX
XX
XX
XX
XX
XX
XX
XX
XX
2 2
XX
XX
5 3
XXX
XXX
XXX
XXX
...
9 9
.X.......
........X
.........
.........
.........
...X.....
.........
..X......
.....X...
9 9
XXXXXXXXX
XXXXXXXXX
XXXX.XXXX
XXX.X.XXX
XX.X.X.XX
XXX.X.XXX
XXXX.XXXX
XXXXXXXXX
XXXXXXXXX
2 2
..
..
0

My WA Output:

Code: Select all

Case 1: 5
Case 2: 1
Case 3: 2
Case 4: 1
Case 5: 2
Case 6: 2
Case 7: 5
Case 8: 0

Thanks in advance.

[Jan]

Your outputs are correct. Greedy shouldn't work I think. Check the case below.

Input:

Code: Select all

5 5
XX...
XX...
X...X
X..X.
XXXXX
0

Output:

Code: Select all

2

Hope it helps.

[LithiumDex]

My program also outputs 2 for that case.

[Jan]

Try the case.

Input:

Code: Select all

7 7
X......
XX.....
X.X..X.
X......
X..X...
X......
XXXXXXX
0

Output:

Code: Select all

2

Hope it helps.

[LithiumDex]

Again, same.

[Jan]

Err... This time your code should fail I think...Otherwise, if you dont mind, post your code.

Input:

Code: Select all

7 7
X......
XX.....
X.X..X.
X......
X..X.X.
X......
XXXXXXX
0

And output is 2.

[LithiumDex]

There you go... I'm working a brute force solution right now... TLE, but I've got it down to just a bit over 20 seconds (on my PC) with 13 test cases of grids of 9x9 X's

[EDIT] Got it down to 4.6 seconds. Thanks, and AC

[LithiumDex]

I have the running theory.. that in the rare(?) case that the greedy algorithm fails, it will only be off by one -- I wonder if there's some way to detect this case quickly and subtract one? hmm...

[rujialiu]

I have the running theory.. that in the rare(?) case that the greedy algorithm fails, it will only be off by one -- I wonder if there's some way to detect this case quickly and subtract one? hmm...

Yep, that is exactly how I worried when designing test cases. So I used a few pairs of test cases with exactly one different square (marked vs unmarked) that have different answers. But I'm still unsure a clever "detector" would defeat my data... So if you succeeded one day, please tell me

[Akter_Sust]

6 5
XXXXX
XXXXX
XXX..
X.XX.
X..XX
X...X

5 6
XXXXXX
XXX...
XXXX..
XX.XX.
XX..XX
5 6
XXXXXX
...XXX
..XXXX
.XX.XX
XX..XX
6 5
XXXXX
XXXXX
..XXX
.XX.X
XX..X
X...X
0

For all this test case output is 2.
But type of the 2 and 3 no of test case is not in the judge test case
because one of my accepted code is fail generate this output.

[rujialiu]

For all this test case output is 2.
But type of the 2 and 3 no of test case is not in the judge test case
because one of my accepted code is fail generate this output.

Thanks I guess I'll improve the data someday later

[sclo]

I wonder if there is any faster optimizations. For the 9x9, my solution is fairly slow.

[baodog]

Hi,

About the question on how to optimize...
I got 30 milliseconds using
branch and bound Heuristic Search.