A bunch of new tests have been added. 33 of 38 authors lost their AC.

A little hint: this problem do has a polynomial solution, and it's not so tricky as you may think.

Edited by author 28.01.2016 15:20

OUCH

spam random @ pray

Didn't really expect it to work, especially after such a dramatic rejudge. And i didn't even get to use sorts of «clever» random with GA and mutating solutions.

Apparently, most of my WAs were because of inappropriate process of building candidate rectangles, or so i believe...

Also, here's a test that helped me, though quite likely it won't be too helpful for anyone else:

7 5
10001
11011
11111
11111
11110
11010
10010
---
5
1 1 7 1
2 1 6 2
3 1 5 4
2 4 7 4
1 5 4 5

The hint is clear: there is deterministic polynomial algorithm (~O(s^2)).

Some useful tests (for that algorithm):
4 9
010000010
111010111
101111101
000101000
9
---------
4 4
1100
1110
1111
0111
3
----
4 4
1100
1110
0111
0010
3
----
5 5
11100
11110
11111
01111
00111
3
-----
4 3
001
111
011
010
3
---
4 3
010
111
011
001
3
---
4 4
0010
1110
0111
0101
4
----
4 4
0101
1111
1110
0010
4
----
4 3
011
010
110
100
3
---

Oh, good job, and thanks for the tests~
I do have a certain algo in mind actually, but i'm afraid i'll be too lazy to try and code it yet — not until some test that breaks my program is added, haha.

Well, and here's another test case then, simple but could be useful. I had a bunch of WAs on 3 and 4 initially; i was building candidate rectangles by expanding them from corners. But then i realized there can be H-like cases, and that horizontal row isn't supported by any corners.

3 5
10001
11111
10001

Your smart randomized brute force approach is incredible at my mind.

I sure eventually there will be Sakura v2 (something like N=10000 (nonsensible) and M=500) and optimized O(s^2) algorithm became unavoidable.

Edited by author 27.05.2016 06:42

Edit: affirmative, remove it~

Edited by author 27.05.2016 00:09

Roger that. Removed.

Edited by author 27.05.2016 00:11