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
Auto comment: topic has been updated by SuhasJain (previous revision, new revision, compare).
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-1As x can be max 26 so Time Complexity is O(n)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?
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 .
Yes, that'll work. Thank you.
I did exact same still got memory limit exceeded on last three test cases.
Very tight Memory limit.
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
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
If symmetric relations are allowed that would mean that the relation is reflexive too which is a contracdiction.
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
Floyd warshall + dp will do the job.
how to register for these online challenges?
These tests are meant for oncampus hiring.
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).