| Show all threads Hide all threads Show all messages Hide all messages |
| Got AC with random algorithm | Deepesson | 1548. Sakura and Statistics | 23 Apr 2024 03:52 | 1 |
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... |
| propose to rejudge | Serhiy Ivanov | 1548. Sakura and Statistics | 15 Nov 2016 07:23 | 3 |
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... |
| Problem 1548 "Sakura and Statistics" has been rejudged | Vladimir Yakovlev (USU) | 1548. Sakura and Statistics | 27 May 2016 00:03 | 8 |
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 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 |
| Some tests | Al.Cash | 1548. Sakura and Statistics | 29 Jan 2015 22:20 | 2 |
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 |
| Pls someone give me some tests. Can't understand what's the problem in my solution. | mark901 | 1548. Sakura and Statistics | 4 Oct 2013 19:47 | 1 |
|
| что в 3 тесте | kostan3 | 1548. Sakura and Statistics | 3 Jun 2013 20:00 | 1 |
|
| "kibernetic" Np set cover problem works! | svr | 1548. Sakura and Statistics | 3 Oct 2009 18:58 | 1 |
Firstly in timus backtracking set cover problem
helped to get Ac. |
| Mistake in statement :) | OpenGL | 1548. Sakura and Statistics | 22 Jun 2009 20:23 | 2 |
All statement have words "Input" and "Output" (in russian "Исходные данные" and "результат"). But on this problem word "output" ("результат") is not exists. |
| Queestion about task? | vetas | 1548. Sakura and Statistics | 4 Aug 2007 14:16 | 2 |
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? |
