You are not logged in. Please login at www.codechef.com to post your questions!

×

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

asked 19 Aug '17, 21:34

amanharitsh's gravatar image

1★amanharitsh
134
accept rate: 0%


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.

link

answered 19 Aug '17, 21:46

vijju123's gravatar image

5★vijju123 ♦
13.6k11036
accept rate: 19%

edited 19 Aug '17, 21:46

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) amanharitsh1★

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) vijju123 ♦5★

f(1,2) =2 and f(2,1) =3....m i right?

(19 Aug '17, 22:05) amanharitsh1★

Yes, you are right. :)

(19 Aug '17, 22:15) vijju123 ♦5★

Thanks a lot :-)

(19 Aug '17, 22:26) amanharitsh1★

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.

link

answered 19 Aug '17, 21:45

paddi's gravatar image

3★paddi
262
accept rate: 25%

edited 19 Aug '17, 21:47

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.

link

answered 19 Aug '17, 21:45

paddi's gravatar image

3★paddi
262
accept rate: 25%

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

link

answered 20 Aug '17, 12:43

amanharitsh's gravatar image

1★amanharitsh
134
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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:

×332
×323
×193

question asked: 19 Aug '17, 21:34

question was seen: 180 times

last updated: 20 Aug '17, 12:43