You are not logged in. Please login at www.codechef.com to post your questions!

×

Codeforces - D.Substring !

Can anyone tell me what's the need of topological sort in this question ?? Cant we do this just running DFS on any random node and continuing until all the nodes are visited and in DFS we keep an array of size 26 in each node and store the count of that current character and update the child node array accordingly and when we are done with a path (root to leaf) we take maximum count of that array in current node(leaf node) ! And finally printing the count ! If there is a cycle print -1 instead ! My code fails for the 3rd sample case !

Ques : http://codeforces.com/problemset/problem/919/D My code : http://codeforces.com/contest/919/submission/38124119

Pls help !1

asked 12 May '18, 09:52

msd_007's gravatar image

1★msd_007
3178
accept rate: 5%


instead of using union you should use a simple dfs. The problem is that you are merging two nodes which are in different branches of root and thus they will not form a cycle (back edges) but when you are merging they are joined and hence any children of the other branch seems to form a cycle(having same parent) which is actually not the case!

link

answered 12 May '18, 19:22

pk301's gravatar image

2★pk301
62710
accept rate: 16%

thanks bro ! got it !

(12 May '18, 21:31) msd_0071★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×373

question asked: 12 May '18, 09:52

question was seen: 124 times

last updated: 12 May '18, 21:31