11055 - Homogeneous squares

[sakhassan]

Can any 1 give me some test cases???

[Martin Macko]

Code: Select all

10
37 96 55 -15 -79 31 81 -40 72 -63
77 136 95 25 -39 71 121 0 112 -23
3 62 21 -49 -113 -3 47 -74 38 -97
-98 -39 -80 -150 -214 -104 -54 -175 -63 -198
-24 35 -6 -76 -140 -30 20 -101 11 -124
48 107 66 -4 -68 42 92 -29 83 -52
-72 -13 -54 -124 -188 -78 -28 -149 -37 -172
-25 34 -7 -77 -141 -31 19 -102 10 -125
88 147 106 36 -28 82 132 11 123 -12
25 84 43 -27 -91 19 69 -52 60 -75
10
-59 -79 -86 25 -25 -53 23 86 -59 -78
77 57 50 161 111 83 159 222 77 83
48 28 21 132 -38 54 130 193 48 29
55 35 28 139 89 61 137 200 55 36
59 39 32 143 93 65 141 67 59 -82
-65 -85 -92 19 -31 -59 17 80 -65 -84
49 29 22 133 83 55 58 194 49 30
13 -7 -14 97 47 19 95 158 13 -6
-59 -79 -86 25 -25 -53 23 86 -59 -78
-8 -28 -35 76 26 -2 74 137 -8 -27
10
72 79 41 44 -39 -24 27 -18 -63 92
-82 -75 -113 -110 -193 -178 -127 -172 -217 -62
-63 -56 -94 -91 -174 -159 -108 -153 6 -43
-22 -15 -53 -50 -133 -118 -67 -112 -157 -2
92 99 61 64 -19 -4 47 2 -43 112
26 33 -5 -2 -85 -70 -19 -64 -109 46
67 74 36 39 -44 -29 22 -23 -68 87
-65 -58 -96 -93 -176 -161 -110 -155 -200 -7
64 71 33 61 -47 -32 19 -26 -71 84
21 -42 -10 -7 -90 -75 -24 -69 -114 41
10
52 -81 -33 -10 92 70 -95 -8 15 91
-68 -201 -153 -130 -28 -50 -215 -128 -105 -29
32 -101 -53 -30 72 50 -115 -28 -5 71
98 -35 13 36 138 116 -49 38 61 137
-89 -222 -174 -151 4 -71 -236 -149 -126 -50
-23 -156 -108 -85 17 -5 -170 -83 -60 16
18 -115 -67 -44 58 36 -129 -42 -19 57
-83 -216 -168 -145 -43 -65 -230 -143 -120 -44
-73 -206 -158 -135 -33 -55 -220 -133 -110 -34
69 -64 -16 7 109 87 -78 9 32 108
10
-45 63 -29 -9 -35 -1 19 -48 9 26
-3 105 13 33 7 41 61 -6 51 68
83 191 99 119 93 127 147 80 137 154
67 175 83 103 77 111 131 64 121 138
82 190 98 118 92 126 146 79 136 153
25 133 41 61 35 69 89 22 79 96
-48 60 -32 -12 -38 -4 16 -51 6 23
59 167 75 95 69 103 123 56 113 130
-12 96 4 24 -2 32 52 -15 42 59
-64 44 -48 -28 -54 -20 0 -67 -10 7
10
-69 -56 -75 70 45 -76 -36 95 -34 -83
93 106 87 -87 207 67 6 257 128 79
62 75 56 201 176 68 95 226 97 48
-65 -52 43 -9 49 -72 -72 99 43 87
-49 -99 92 42 -45 -19 -23 115 18 -63
-31 61 -31 108 83 17 2 133 4 69
-82 -92 -88 57 32 -89 -49 82 -47 37
-85 -72 -91 -22 29 -92 -52 -25 -50 -91
96 109 90 235 210 3 129 260 131 82
33 46 27 172 -39 26 66 197 68 19
0

My AC's output is

Code: Select all

homogeneous
not homogeneous
not homogeneous
not homogeneous
homogeneous
not homogeneous

[Darko]

I couldn't get this one right at the time of the contest, because it never occured to me that sums might not fit into 32-bit integers. I saw a 1000 and a million.. meh

The biggest problem I have with this ... uhm... problem is that my Java solution times out, but the same solution coded in C is AC in average time (~2.5secs). I can make an excuse for WA last night, it was ~4am when I tried it (well, not much of an excuse), but I am not sure why it would time out in Java.

Because it's Ulm problem, I'll ask because someone here might know - is there a reference solution in Java 1.1? I guess it only affected me - all Java submitions were mine, but still...

[leocm]

How can I generate all the n! different ways to choose n independent positions? Somebody could explain me a algorithm? With out this, it's impossible to make the exercise.

My question is similar to the problem of how can I generate, for example, the sequence:

0 1 2
0 2 1
1 0 2
1 2 0
2 0 1
2 1 0

This is a example for a input with n = 3, where the numbers above are representing the order of the rows, where the columns will always been in the order 0 1 2.

That is, the sum of all the ways to choose n independent positions in a matrix A representing the numbers will be:

Sum1 = A[0][0] + A[1][1] + A[2][2]
Sum2 = A[0][0] + A[2][1] + A[1][2]
Sum3 = A[1][0] + A[0][1] + A[2][2]
Sum4 = A[1][0] + A[2][1] + A[0][2]
Sum5 = A[2][0] + A[0][1] + A[1][2]
Sum6 = A[2][0] + A[1][1] + A[0][2]

Then, it's only to verify if all the sums are equal.

Forgive me for my poor english...

Thank you,
Leonardo.

[StatujaLeha]

Hi!
I solved this problem, but i have one question.
My first algorithm got TLE. It worked in O(n^3). Did someone get accepted with algorithm with complexity O(n^3)?

[Adrian Kuegel]

Because it's Ulm problem, I'll ask because someone here might know - is there a reference solution in Java 1.1? I guess it only affected me - all Java submitions were mine, but still...

The real Ulm local contest allowed Java 1.5, and we had an increased time limit for Java solutions because of the slow I/O. The Java reference solution uses the class Scanner to read the input and takes 30 seconds.

[Adrian Kuegel]

How can I generate all the n! different ways to choose n independent positions? Somebody could explain me a algorithm? With out this, it's impossible to make the exercise.

Actually, with this it is impossible to solve this problem. Have you ever thought about how long it would take for a homogeneous square of size 1000 by 1000 to check that all 1000 factorial sums are equal?
However, a randomized algorithm which tries only a few such permutations is possible. You can calculate the probability that it fails (if you assume that in the worst case, only 1 cell has a wrong value), and after about trying 5000 iterations the probability that it fails is at most 1 percent.
Of course there is also a non-randomized solution which correctly determines if a square is homogeneous in O(n^2) time.

[Krzysztof Duleba]

My solution is even simpler than the one mentioned in the editorial: a square is homogeneous if cell[j] + cell[i-1][j-1] == cell[i-1][j] + cell[j-1] for each 0<i<n, 0<j<n.

[Nazmul Quader Zinnuree]

a square is homogeneous if cell[j] + cell[i-1][j-1] == cell[i-1][j] + cell[j-1] for each 0<i<n, 0<j<n.

The last solution is simpler and nice. But how it works? What is the math behind it? Any explanation, plz.

Thanks.

[little joey]

The method mentioned in the editorial boils down to: if cell[j] - cell[0][j] == cell[0] - cell[0][0] for each 0<i<n, 0<j<n (or the equivalent, switching rows and columns), so I don't see why your solution would be 'simpeler'.

[Krzysztof Duleba]

OK, I agree it "boils down" to it if you know you can take that one more step further instead of simply following the directions ("reduce the first row and column to zero")

What is the math behind it? Any explanation, plz.

If cell[j] + cell[i-1][j-1] == cell[i-1][j] + cell[j-1] for each 0<i,j<n, then actually cell[k][l] + cell[p][q] == cell[k][q] + cell[p][l] for each 0<=k,l,p,q<n (easy to see once you draw it on a piece of paper).

[cmad]

No it's exactly the same... Your solution holds holds the width and height fixed, whereas the other solution holds the coordinates of the top-left cell fixed. Exactly the same thing, different approach.

[Darko]

Adrian: Thanks for the clarification.

I just read the editorial, that is very nice, never ocured to me to do it that way :)
I added wrapped-around diagonals and checked if they were all totalSum/n. I did it both UL-LR and LL-UR (not sure if it's redundant). It worked for these cases, but should it work in general?

[Adrian Kuegel]

It is not redundant to do both UL-LR and LL-UR.
For example look at following non-homogeneous square:
1 1 1
3 2 2
3 2 3

If you do just the UL - LR diagonals, you will think it is homogeneous.
However, so far I found no test case where your method fails (but I didn't spend much time on it).

[leocm]

My solution is even simpler than the one mentioned in the editorial: a square is homogeneous if cell[j] + cell[i-1][j-1] == cell[i-1][j] + cell[j-1] for each 0<i<n, 0<j<n.

Where can I find this editorial? What is this? Cell is the same thing that a matrix?