Help for Discount on Crackers (ACM14KG3)

CodeChef-DSA-learners
,
1

Link to the question:

I ended up doing this differently and getting AC, but I’m getting WA on my original solution and I can’t seem to figure out why.

My original logic was instead of perform DFS on each character which I thought would be expensive, use DFS once and store a boolean in a 2D matrix indicating whether there’s a path from node s → t. With this information, I can use constant time queries to determine whether there’s a path from one character to another.

I’ve tried testing my implementation on different graphs, but it works on all of the things I could come up with.

Here’s my submission: CodeChef: Practical coding for everyone

2

I can only find the following problem:

because you check if the length of S and T are equal before reading in the transitions you could end up in a situation where your input is offset from the actual input for the next test case.

Furthermore I am not really certain if a transition like ab->c is allowed or not.