Connection Status:
Competition Arena > Undivisors

Undivisors

SRM 691 · 2016-05-02 · by subscriber

SRM 691 · 2016-05-02 · by subscriber · Advanced Math, Dynamic Programming, Math
Class Name: Undivisors
Return Type: double
Method Name: getexp
Arg Types: (vector<string>)
Problem Statement

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:
  1. 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.)
  2. He will choose a submatrix B of his matrix uniformly at random. (B may be the same submatrix as A.)
  3. He will find the set S of numbers that occur in at least one of A and B.
  4. He will calculate X: the least common multiple of all numbers in S.
  5. 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.

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
0)
{"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.

1)
{"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.

2)
{"4356"}
Returns: 5.4
3)
{"12"
,"11"}
Returns: 2.691358024691358
4)
{"2345"
,"AEa9"}
Returns: 6.34

Submissions are judged against all 58 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class Undivisors with a public method double getexp(vector<string> a) · 58 test cases · 2 s / 256 MB per case

Submitting as anonymous