| ENG RUS | Timus Online Judge |
Обсуждение задачи 1548. Сакура и статистикаDeepesson Got AC with random algorithm // Задача 1548. Сакура и статистика 23 апр 2024 03:52 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... Serhiy Ivanov propose to rejudge [2] // Задача 1548. Сакура и статистика 8 авг 2016 22:33 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 Shen Yang Re: propose to rejudge [1] // Задача 1548. Сакура и статистика 15 ноя 2016 07:19 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 Shen Yang Re: propose to rejudge // Задача 1548. Сакура и статистика 15 ноя 2016 07:23 now 13 problems with 10W+ rating... Vladimir Yakovlev (USU) Problem 1548 "Sakura and Statistics" has been rejudged [7] // Задача 1548. Сакура и статистика 28 янв 2016 15:17 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 bsu.mmf.team Re: Problem 1548 "Sakura and Statistics" has been rejudged [6] // Задача 1548. Сакура и статистика 18 фев 2016 22:36 OUCH Jane Soboleva (SumNU) Re: Problem 1548 "Sakura and Statistics" has been rejudged [5] // Задача 1548. Сакура и статистика 18 май 2016 05:36 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 Orient Re: Problem 1548 "Sakura and Statistics" has been rejudged [4] // Задача 1548. Сакура и статистика 26 май 2016 23:21 Jane Soboleva (SumNU) писал(a) 18 мая 2016 05:36 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 --- Jane Soboleva (SumNU) Re: Problem 1548 "Sakura and Statistics" has been rejudged [3] // Задача 1548. Сакура и статистика 26 май 2016 23:44 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 Orient Re: Problem 1548 "Sakura and Statistics" has been rejudged [2] // Задача 1548. Сакура и статистика 26 май 2016 23:51 Jane Soboleva (SumNU) писал(a) 26 мая 2016 23:44 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:42 Jane Soboleva (SumNU) Re: Problem 1548 "Sakura and Statistics" has been rejudged [1] // Задача 1548. Сакура и статистика 27 май 2016 00:02 Edit: affirmative, remove it~ Edited by author 27.05.2016 00:09 Orient Re: Problem 1548 "Sakura and Statistics" has been rejudged // Задача 1548. Сакура и статистика 27 май 2016 00:03 Roger that. Removed. Edited by author 27.05.2016 00:11 Al.Cash Some tests [1] // Задача 1548. Сакура и статистика 29 янв 2015 00:45 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 Al.Cash Re: Some tests // Задача 1548. Сакура и статистика 29 янв 2015 22:20 This helped with test 20, now WA31 to overcome! 4 5 00100 01110 01010 11011 answer: 5 mark901 Pls someone give me some tests. Can't understand what's the problem in my solution. // Задача 1548. Сакура и статистика 4 окт 2013 19:47 kostan3 что в 3 тесте // Задача 1548. Сакура и статистика 3 июн 2013 20:00 помогите svr "kibernetic" Np set cover problem works! // Задача 1548. Сакура и статистика 3 окт 2009 18:58 Firstly in timus backtracking set cover problem helped to get Ac. OpenGL Mistake in statement :) [1] // Задача 1548. Сакура и статистика 22 июн 2009 15:55 All statement have words "Input" and "Output" (in russian "Исходные данные" and "результат"). But on this problem word "output" ("результат") is not exists. Sandro (USU) Thank you. :) (-) // Задача 1548. Сакура и статистика 22 июн 2009 20:23 vetas Queestion about task? [1] // Задача 1548. Сакура и статистика 4 май 2007 14:36 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? Zheka Re: Queestion about task? // Задача 1548. Сакура и статистика 4 авг 2007 14:16 1 1 1 3 3
|