Problem Link : https://www.codechef.com/problems/STRINGRA Can Anyone please explain why the answer for this test case is 1 2 1 2 1 2 instead of 1 2 1 1 1 1 1 6 11 0 1 0 2 1 2 1 3 2 3 2 4 3 4 3 5 4 5 4 6 5 6 @vijju123 @admin3 @anmolmishra asked 19 Aug '17, 21:34

take a look at these edges : 2 3, 2 4 since 3 is connected to 1 and 3 both and 1 is connected to 2 that means 3 has a value 1(i.e at third position there is 1). Now 2 is connected to node 3 and 4 therefore 3rd and 4th position cannot have value 1. hence 4th node has value 2 (i.e subsequence 1212 and 122) .Similarly u can analyze for other nodes. answered 19 Aug '17, 21:45

If anyone struggling with the same doubt as mine.... u can read this Observation 2 from editorial "Observation 2: Consider an arbitrary position PP, you can note that the subsequence containing all elements AiAi (1≤i≤P)(1≤i≤P) cannot be formed without considering all elements till APAP let's denote this subsequence by S1S1. If there is an edge (P→Q)(P→Q), it means that QQ must be the first occurrence (to the right of PP) of one of our numbers (Why?), because if there was an earlier occurrence R(R<Q)R(R<Q), then the subsequence S1+AQS1+AQ (+ denotes concatenation) could be formed with the first RR elements, and that means an edge (P→R)(P→R) must exist and the other edge (P→Q)(P→Q) mustn't (contradiction)." answered 20 Aug '17, 12:43
