Connection Status:
Competition Arena > Homomorphism

Homomorphism

SRM 190 · 2004-04-06 · by dgarthur

SRM 190 · 2004-04-06 · by dgarthur · Brute Force, String Manipulation
Class Name: Homomorphism
Return Type: int
Method Name: count
Arg Types: (string, string)
Problem Statement

Problem Statement

A binary string is a non-empty finite sequence of 0's and 1's. Given two binary strings, u and v, their concatenation, u * v, is defined to be the binary string obtained by appending v to the end of u. For example, if u = 01100 and v = 110, then u * v = 01100110.

Consider a function, h, that maps binary strings to other binary strings. Suppose that for every string u with digits a1, a2, ..., ak in that order, it is true that h(u) = h(a1) * h(a2) * ... * h(ak). Then, h is called a non-degenerate homomorphism. In general, this means that h is uniquely determined by the values of h(0) and h(1). For example, if h(0) = 001, and h(1) = 10, then,

  • - h(110) = h(1) * h(1) * h(0) = 1010001.
  • - h(00) = h(0) * h(0) = 001001.
  • - h(0101) = h(0) * h(1) * h(0) * h(1) = 0011000110.

Create a class Homomorphism that contains a method count, which is a given a String u and a String v. The method should return the number of distinct non-degenerate homomorphisms, h, which satisfy h(u) = v. If there are infinitely many such non-degenerate homomorphisms, the method should return -1.

Notes

  • Two non-degenerate homomorphisms, h and h' are considered distinct if and only if h(u) is different from h'(u) for at least one binary string, u.

Constraints

  • u and v will each contain between 1 and 50 characters inclusive.
  • Each character in both u and v will be either '0' or '1'.
Examples
0)
"10"
"11001"
Returns: 4

Since h(0) and h(1) cannot be empty strings, there are precisely 4 legal non-degenerate homomorphisms: 1. h(1) = 1 and h(0) = 1001. 2. h(1) = 11 and h(0) = 001. 3. h(1) = 110 and h(0) = 01. 4. h(1) = 1100 and h(0) = 1.

1)
"00"
"11111"
Returns: 0

If h is a valid non-degenerate homomorphism, then h(00) = h(0) * h(0), which implies that h(00) has an even length. Thus, there are no non-degenerate homomorphisms satisfying h(00) = 11111.

2)
"11"
"00"
Returns: -1

Any non-degenerate homomorphism, h, satisfying h(1) = 0 will also satisfy h(11) = 00. This leaves no restrictions at all on h(0), so there are an infinite number of such non-degenerate homomorphisms.

3)
"001"
"1010001"
Returns: 1

The unique non-degenerate homomorphism, h, satisfying h(001) = 1010001 is given by h(0) = 10 and h(1) = 001.

4)
"101"
"11111111111111111111111111111111111111111111111111"
Returns: 24

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

Coding Area

Language: C++17 · define a public class Homomorphism with a public method int count(string u, string v) · 75 test cases · 2 s / 256 MB per case

Submitting as anonymous