At contest time i was thinking considering all paths and check all string(by contactaenating those string which are present in path) and print smallest lexicographical but…unable to did…so hack 2 TC
Unrelated, but did they actually say a DAG is equivalent to a tree?
1 Like
and all solution (which are AC) have same type of thing means they consider 0->1->2->3 path even by using this path the resultant string is not lexicographical smaller.
I commented too but nobody answered! Codechef should have a “Clarification” button. In the first testcase abcddabcddbbba is smaller than abcddabcddkooabbba but for unexplicable reason the second is the smaller one according to some weird logic I just cannot get! I don’t think I am missing anything they must be wrong, and doing nothing to clarify that!
Yeah, wouldn’t the optimal answer be a path of length 1 anyway? Because appending characters to a string makes it lexicographically larger no matter what. The problem specifies any path.
3 Likes
Yes…But let’s consider the setter want longest path ok…even if it is wrong
What I did -> I started from 0 and out of all nodes connected to 0 (0 -> x), I chose the node which was alphabetically smallest and marked that node as visited and continued the process till I get a node from which I can’t go to any un-visited node which is basically a leaf (kind of dfs only).
LOL, you have to assume that? This is the worst statement ever
1 Like
I also thought the same thing and this is correct. The question was wrong…considering the test cases…I had to go for another approach.
At contest time , I consider setter want me largest path such that the string made by that path is lexicographical (alphabetically smaller)
see in first test case two longest path possible either 0->1->2->3 or 0->1->2->3 string made by first path is “abcddabcddkooabbba” while second path will made “abcddabcddkooaolop” so in sample TC it is correct but my question is what actually setter wanna say ?
In ongoing contest we have no other option as many user already said that no one reply 
@ssrivastava990
If setter wants the longest path, then what is the problem with the test cases…in that case they are correct.
In Question the test cases are correct but when i saw many solutions they just print that path which occur first no need to traverse any other path even some other path (longest too) give optimal result
Yes agreed that todays setting was all messy. l apologise. I have for first time tried to set difficult problems in keteki…
I resort to using more time to set problems so that logical and artistic mistakes are not made. I feel mathematically trying to prove solutions and then trying to programmatically prove it wrong should work. Also the problem should have solid theoritical background.
I also found that setting is not just solving… it is more testing and documenting. At testing and documenting internally it is about some form of memory usage. I need practice in that. I will use time and take help of tester next. Harsh raj helps me in testing. And possibly will be able to say if problem is clear enough.
Regarding the question yes i wanted the longest path but the smallest alphabetical string possible till a leaf is reached which i didnt mentioned.
That is just because the test cases were highly weak.
2 Likes
And yes that too. However regarding documenting the statement, i might still miss mentioning about the leaf node. Even though strong cases are set. It involves both more time usage, of self memory and a tester. Thank you.
2 Likes
@akshitm16 @galencolin so how can i find all longest path in given Adajcency matrix help me in this 
1 Like
I don’t have any idea till now…but I guess BFS might work… though I’m not sure. I’ll update when I myself get an idea.
1 Like
Well, you’re given that the graph is a DAG (or a tree, either way), so you can do something like this (do DP with topological sort). Were it not a DAG, the problem would be NP-complete.
1 Like
Thank you!
1 Like