SuhasJain's blog

Google Online Coding Challenge 2021 — 24th July
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

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

Comments Comments (14)
| Write comment?
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by SuhasJain (previous revision, new revision, compare).

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

I think the key Concepts are dfs and dp - First Find the number of Connected Components (let it be x )and Store The size of each connected component - now creat a 2D dp array dp[n][x] , where dp[i][j] (0 based indexing) number of strings of length i which end with a character from jth component -Base Case dp[0][j]=size of jth component (0 based indexing) - Recurrence dp[i][j]= size of jth component * (sum of dp[i-1][k] over all k from 0 to x-1 excluding j) - Take mod at appropriate places and get the value - number of strings = sum of dp[n-1][j] for all j from 0 to x-1 As x can be max 26 so Time Complexity is O(n)

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    If in pairs we are given [[a,b], [b,c], [b, d]], then a, b, c and d form a connected component but still neither [c, d] nor [d, c] can be generated by any transitive relation and thus they can be adjacent in a string. So is it fair to assume no 2 elements in a connected component can be adjacent?

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes Sorry for That , I misunderstood .What we can do is as number of alphabets is only 26 , for every character we can store those characters which are in a transitive relation with it and after that create dp[n][26] and use the similar recurrence I mentioned above .

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        Yes, that'll work. Thank you.

        → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        I did exact same still got memory limit exceeded on last three test cases.

        Very tight Memory limit.

        → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          To Reduce Memory Requirements we can instead of dp[n][26] use dp[26](for previous state)and dp1[26](for current state) because we need the values of just the previous state to get the values of current state and update dp1 and dp for each i

          → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      Is the relation given here symmetric because the relation is not stated in some directed sense, a,b relation implies b,a relation.
      Then, it will be same as avoiding characters in a connected component as adjacent characters.
      Also, you have mentioned 

      N = 2
M = 3
Pairs = [[a,b], [b,c], [c,d]]
So the following pairs cannot occur : [ab, ac, ad, ba, bc, bd, ca, cb, cd, da, db, dc]
bd and db is written here.
      → Reply
      • »
        »
        »
        »
        13 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        If symmetric relations are allowed that would mean that the relation is reflexive too which is a contracdiction.

        → Reply
»
3 years ago, # |
← Rev. 4   Vote: I like it +17 Vote: I do not like it

You can use Floyd warshall, to get transitive relation in 26 phases, binary matrix denote 1 if i -> j cannot be edge else 0, take complement of this(after applying floyd warshall) and you will get your transition matrix and then apply matrix exponentiation or just multiplication to calculate the answer, this will be your steps to reduce dp.total complexity will be 26^3 log N

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Floyd warshall + dp will do the job.

→ Reply
»
3 years ago, # |
  Vote: I like it +7 Vote: I do not like it

how to register for these online challenges?

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I will try to explain how to get the transition matrix. We will model it as graph with directed edges , then run a dfs and maintain two colors in the visited array(Refer to cycle detection in directed graphs with colors). Whenever we would enter a vertex v in dfs we would make transition_matrix[u][v]=1 for all u which are not yet completely processed(again refer to cycle detection in directed graphs).

→ Reply