ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1548. Sakura and Statistics

Problem 1548 "Sakura and Statistics" has been rejudged
Posted by Vladimir Yakovlev (USU) 28 Jan 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
Re: Problem 1548 "Sakura and Statistics" has been rejudged
Posted by bsu.mmf.team 18 Feb 2016 22:36
OUCH
Re: Problem 1548 "Sakura and Statistics" has been rejudged
Posted by Jane Soboleva (SumNU) 18 May 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
Re: Problem 1548 "Sakura and Statistics" has been rejudged
Posted by Orient 26 May 2016 23:21
Jane Soboleva (SumNU) wrote 18 May 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
---
Re: Problem 1548 "Sakura and Statistics" has been rejudged
Posted by Jane Soboleva (SumNU) 26 May 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
Re: Problem 1548 "Sakura and Statistics" has been rejudged
Posted by Orient 26 May 2016 23:51
Jane Soboleva (SumNU) wrote 26 May 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
Re: Problem 1548 "Sakura and Statistics" has been rejudged
Posted by Jane Soboleva (SumNU) 27 May 2016 00:02
Edit: affirmative, remove it~

Edited by author 27.05.2016 00:09
Re: Problem 1548 "Sakura and Statistics" has been rejudged
Posted by Orient 27 May 2016 00:03
Roger that. Removed.

Edited by author 27.05.2016 00:11