SuhasJain's blog

By SuhasJain, history, 3 years ago, In English

I need help with this problem asked in Google Online Challenge.

You are given the following:
- An integer value N
- M pairs of distinct characters (lowercase English alphabets)
A pair of characters in the given pairs holds a relation between them. The relation among the given pairs is also transitive, which means if you consider 2 pairs (u, v) and (v, w) which holds relation, then pair (u, w) also holds the relation. Also, the relation states that those pairs of characters cannot occur together in a formed string.
Determine the total number of strings of length N such that any string does not contain a pair of adjacent characters holding any relation. Since this number can be large output it modulo 10^9+7.

Constraints
1 <= T <= 10 (Number of test cases)
1 <= N <= 10^4
0 <= M <= 325 (M is the number of pairs given)

Example
Input:
N = 2
M = 3
Pairs = [[a,b], [b,c], [c,d]]

Approach:
- Since [a,b] and [b,c] hold a transitive relation, thus a relation among all pairs in [a, b, c] holds true.
- Since [a, b, c] and [c, d] shares a transitive relation thus a relation among all pairs in [a, b, c, d] holds true.
- So the following pairs cannot occur : [ab, ac, ad, ba, bc, bd, ca, cb, cd, da, db, dc]
- The strings that can be formed of length 2 are : ["aa", "ae", "af", .....]

Output:
664

Full text and comments »

  • Vote: I like it
  • +6
  • Vote: I do not like it