Discussion @ 1861. Graveyard in Deyja @ Timus Online Judge

Some hints needed. 72VanVector[SevNTU] 24 Sep 2011 22:19

Can somebody give hints to solve this task?

Re: Some hints needed. svr 8 Oct 2011 19:06

Conflict graph may help.
Positions of possible substrings are vertices and two positions
conflict if they can not be simultaneously.
Answer= max number of independent vertices.
Also let relation a<b means that position is before of position b and they don't conflict.Then a<b,b<c=> a<c so we have an order. Answer is a height of ordered structure.

Edited by author 08.10.2011 19:07

Re: Some hints needed. bsu.mmf.team 9 Oct 2011 02:04

Just easy DP.

Re: Some hints needed. svr 10 Oct 2011 11:47

But Dp may be difficult- problem of 35 test.
When poset is used and standard dfs for it's height we have Ac without any problems.

Discussion of Problem 1861. Graveyard in Deyja