×

# STRINGRA HELP!!

 0 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 13●4 accept rate: 0%

 1 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. answered 19 Aug '17, 21:46 14.4k●1●16●53 accept rate: 18% 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? (19 Aug '17, 21:56) 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. (19 Aug '17, 21:58) f(1,2) =2 and f(2,1) =3....m i right? (19 Aug '17, 22:05) Yes, you are right. :) (19 Aug '17, 22:15) Thanks a lot :-) (19 Aug '17, 22:26)
 0 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 4★paddi 26●2 accept rate: 25%
 0 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 edges. answered 19 Aug '17, 21:45 4★paddi 26●2 accept rate: 25%
 0 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
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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:

×346
×335
×193

question asked: 19 Aug '17, 21:34

question was seen: 211 times

last updated: 20 Aug '17, 12:43