Discount On Crackers: Kharagpur Regionals

general
1

Here’s the link to the problem: http://www.codechef.com/ACMKG14R/problems/ACM14KG3

I have built a graph having nodes a-z. and mapped each rule (a->b, b->c, etc) as edges of the graph.

Go through each character of both strings( say, character a and b) and check if both nodes a and b are connected using a depth-first-search.

I have got a lot of wrong answers during the contest. It might be due to few edge cases which I could miss or my approach could have been outright wrong.

Please help me figure it out.

Here’s my code: http://ideone.com/qyZW2D

2

i solved it using floyd warshall… cant see your code…but a question…are you taking care of this case
1
aa
aa
2
// modifications

as all the modifications will be useless and modifications won’t provide a->a…

Rest of your approach seems correct …

2 Likes
3

Thanks for the reply.
I have checked the case which you have provided. It works. There might be some test case for which my approach fails. Is there any way by which I could find it out?

4

Brother, try this : https://ideone.com/IV6p3h

1 Like
5

Thanks bro. But I wanted to know the fault in my approach. :frowning: