Problem Link : STRINGRA Problem - CodeChef
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
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.
2 3
2 4
Think, what does this mean? This means that there is a sub-sequence ending at index 2 such that if we add 1 element to it, we get a sequence ending at index 3, and index 4 respectively.
But, in case of 1 2 1 1, the sub-sequence would be {1 2 1} or {2 1} (depending on starting index). In this case, we cannot have an edge 2,4 , reason being in definition of function.
If we have a sub-sequence starting at index i,then f(i) is the minimum i at which this sub sequence ends. So, for f{1,2,1} and f{2,1}, the minimum i is 3, not 4. So there no edge from 2 to 4 is possible.
In short, if you have an edge from 2 to 3 and 2 to 4, this implies that element at 3 and 4 MUST be different.
1 Like
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).”
if i append ‘1’ to {2,1} to get {2,1,1}…then i can write this as 1 2 1 and the f( {2,1,1} ) is 3…m i right?
To get 2,1,1 , you are appending 2 elements not 1. Remember, f(i) means that for a series ENDING (and not starting) at index i. there are only 2 series ending at index 2 (1-based indexing) and they are {1,2} and {2}. Appending 1 to them gives {1,2,1} and {2,1} , both of these end at 3 (minimum i to be considered). So only edge from 2 to 3 possible.
f(1,2) =2 and f(2,1) =3…m i right?
Yes, you are right. 
Thanks a lot