STRINGRA HELP!!

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

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 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. :slight_smile:

Thanks a lot :slight_smile:

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).”