Undivisors | Topcoder Archive

Problem Statement

The submatrix of a matrix is any non-empty contiguous rectangular subarray of the matrix. In other words, each submatrix is uniquely determined by a non-empty range of rows and a non-empty range of columns of the original matrix. For example, a 3x3 matrix has exactly 36 different submatrices. Hero has a matrix of positive integers. He is now going to perform the following steps:

He will choose a submatrix A of his matrix uniformly at random. (Each possible submatrix has the same probability of being chosen, regardless of its size.)
He will choose a submatrix B of his matrix uniformly at random. (B may be the same submatrix as A.)
He will find the set S of numbers that occur in at least one of A and B.
He will calculate X: the least common multiple of all numbers in S.
He will find the smallest positive integer Y that does not divide X.

You are given Hero's matrix encoded in the String[] a. Elements of a represent rows of Hero's matrix from top to bottom. Characters of each element represent the values in that row from left to right, using the following map:

The characters '1'-'9' represent the values 1-9.
The characters 'A'-'Z' represent the values 10-35.
The characters 'a'-'z' represent the values 36-61.

Find and return the expected value of Y.

Definition

Class:: Undivisors
Method:: getexp
Parameters:: String[]
Returns:: double
Method signature:: double getexp(String[] a)
(be sure your method is public)

Constraints

n will be between 1 and 50, inclusive.
m will be between 1 and 50, inclusive.
a will contain exactly n elements.
Each element of a will contain exactly m characters.
Each character in a will be either a non-zero digit ('1'-'9') or lowercase letter ('a'-'z') or uppercase letter ('A'-'Z').

Examples

```
{"11"
,"11"}
```
```
Returns: 2.0
```
Regardless of the choice of A and B, the set S will always be {1}, its least common multiple will always be X = 1, and the smallest integer that does not divide 1 is Y = 2.
```
{"234"}
```
```
Returns: 4.5
```
A will be one of {"2"}, {"3"}, {"4"}, {"23"}, {"34"}, or {"234"}. Independently of the choice of A we will then have the same six possibilities for B. Here are all possible outcomes of Hero's procedure: With probability 1/36 we have S = {2}, X = 2, and Y = 3. With probability 1/36 we have S = {3}, X = 3, and Y = 2. With probability 1/36 we have S = {4}, X = 4, and Y = 3. With probability 7/36 we have S = {2,3}, X = 6, and Y = 4. With probability 7/36 we have S = {3,4}, X = 12, and Y = 5. With probability 2/36 we have S = {2,4}, X = 4, and Y = 3. With probability 17/36 we have S = {2,3,4}, X = 12, and Y = 5. Hence, the expected value of Y is (1*3 + 1*2 + 1*3 + 7*4 + 7*5 + 2*3 + 17*5) / 36 = 4.5.
```
{"4356"}
```
```
Returns: 5.4
```
```
{"12"
,"11"}
```
```
Returns: 2.691358024691358
```
```
{"2345"
,"AEa9"}
```
```
Returns: 6.34
```

{"ABC2DE"
,"abc3de"}

Returns: 6.668430335097002

{"ztTxP64OvgP",
"MYp2q3YQwS1",
"9BwRVK4SvFL",
"VQHojP7HyjF",
"Il4ZCEs7vxP",
"dEvUxcOqw9v",
"f5wmo9OigOD",
"CUhrwte35Af",
"LVn1kAmNgOU",
"bhVmE2bgzHo",
"1NPp2dXsc4g",
"LqUEuGQmJfK",
"ewihrw9MHPQ",
"T7Ru3udY5IK"}

Returns: 21.728568950690164

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.