|
|
After cracking my brain for 2 weeks in the search of the polynominal solution, I decided to use my observations to code the most optimized random algorithm I could think of. Surprisingly, I didn't even have to use simulated annealing: hill climb was enough. I also have 2 optimizations that I planned to implement but didn't have enough time. I was expecting very strong tests considering all the dramatic comments from coders way better than me. Maybe it's only a matter of time before admins add new tests that crack my solution, but I can't think of a single test that is strong enough to survive all optimizations... I'm extremely curious about the polynominal solution, so maybe I will continue thinking about this problem... But it's so incredibly hard... I was bit confused to obtain accepted. I applied my solution to test straightforward approach and obtain TLE but i'm not. With next example i would defenitely obtain TLE: 50 50 00000000000000000000000001111111111111111111111111 00000000000000000000000011111111111111111111111111 00000000000000000000000111111111111111111111111111 00000000000000000000001111111111111111111111111111 00000000000000000000011111111111111111111111111111 00000000000000000000111111111111111111111111111111 00000000000000000001111111111111111111111111111111 00000000000000000011111111111111111111111111111111 00000000000000000111111111111111111111111111111111 00000000000000001111111111111111111111111111111111 00000000000000011111111111111111111111111111111111 00000000000000111111111111111111111111111111111111 00000000000001111111111111111111111111111111111111 00000000000011111111111111111111111111111111111111 00000000000111111111111111111111111111111111111111 00000000001111111111111111111111111111111111111111 00000000011111111111111111111111111111111111111111 00000000111111111111111111111111111111111111111111 00000001111111111111111111111111111111111111111111 00000011111111111111111111111111111111111111111111 00000111111111111111111111111111111111111111111111 00001111111111111111111111111111111111111111111111 00011111111111111111111111111111111111111111111111 00111111111111111111111111111111111111111111111111 01111111111111111111111111111111111111111111111111 11111111111111111111111111111111111111111111111111 11111111111111111111111111111111111111111111111111 11111111111111111111111111111111111111111111111110 11111111111111111111111111111111111111111111111100 11111111111111111111111111111111111111111111111000 11111111111111111111111111111111111111111111110000 11111111111111111111111111111111111111111111100000 11111111111111111111111111111111111111111111000000 11111111111111111111111111111111111111111110000000 11111111111111111111111111111111111111111100000000 11111111111111111111111111111111111111111000000000 11111111111111111111111111111111111111110000000000 11111111111111111111111111111111111111100000000000 11111111111111111111111111111111111111000000000000 11111111111111111111111111111111111110000000000000 11111111111111111111111111111111111100000000000000 11111111111111111111111111111111111000000000000000 11111111111111111111111111111111110000000000000000 11111111111111111111111111111111100000000000000000 11111111111111111111111111111111000000000000000000 11111111111111111111111111111110000000000000000000 11111111111111111111111111111100000000000000000000 11111111111111111111111111111000000000000000000000 11111111111111111111111111110000000000000000000000 11111111111111111111111111100000000000000000000000 rejudge me please, I also get AC using brute_force and can't pass this test case Edited by author 15.11.2016 07:21 now 13 problems with 10W+ rating... 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 spam random @ pray 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 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. 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:42Edit: affirmative, remove it~ Edited by author 27.05.2016 00:09 Roger that. Removed. Edited by author 27.05.2016 00:11 This tests helped me with WA3, WA5 and WA10, but now I'm stuck at test 20. Any hints? 4 9 010000010 111010111 101111101 000101000 answer: 9 4 5 11000 01100 00110 00011 answer: 4 5 5 11100 11110 11111 01111 00111 answer: 3 4 9 100111100 100100100 100100100 111100111 answer: 6 This helped with test 20, now WA31 to overcome! 4 5 00100 01110 01010 11011 answer: 5 Firstly in timus backtracking set cover problem helped to get Ac. All statement have words "Input" and "Output" (in russian "Исходные данные" and "результат"). But on this problem word "output" ("результат") is not exists. What shell I do with such case as: 3 3 111 111 111. What will be the answer: 1 1 1 3 3 or 3 1 1 1 3 2 1 2 3 3 1 3 3 or 3 1 1 3 1 1 2 3 2 1 3 3 3? |
|
|