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

×

Unofficial Editorial: Chef and Two String : CHEFTWOS

0
1

I used state machine concept. Identified 5 different states using two character combination. See this in my solution

Explaination:

State is represented by two state variables a and b. if the string is ending at b then a is zero (to indicate the end state). If a is not zero then a and b represent the last two point (character) states when b is not the end point, but a is the end point. So (0, 1) and (0, 2) means the good string is ending at character 1 and 2 respectively. The valid states can be (2, 1) when it is like (***21) and from b(1) the dog can jumps to a(2) and so a(2) is the end point, not the last character b(1).

(2, 2) when it is like (**22) and dog is at the a(2) and b(2) is unvisited character.

So moving to next character is like state transition, this will be clear by following example:

  1. String is in state (0, 1) and the next character is '2', then the new state would be (0, 2).

  2. Current state is (2, 1) and the next character is '2', the new state would be (0, 2).

  3. Current state is (2, 1) the the next character is '1' then the new state would be (0, 1).

  4. Current state is (2, 2) and the next character is '1' then the new state would be (2, 1).

This is explained in the code.

asked 17 Oct '16, 15:26

ashok1113's gravatar image

4★ashok1113
913
accept rate: 0%

edited 20 Oct '16, 15:01

admin's gravatar image

0★admin ♦♦
19.8k350498541


16

By making some "good strings" manually you can easily see that following two conditions should be hold-

  1. always exactly two "2" will come together eg. 1221 but not "2222 or 1211".
  2. always second last digit of strings should be "1".

Now after determining these conditions you just have to form a dynamic programming solution in which at each index you have two choices , either swap the corresponding digits or don't. here is the link of my solution my_solution .

P.S. I took digits "0 and 1" instead of "1 and 2" in my solution .

link

answered 17 Oct '16, 19:15

anshal21's gravatar image

4★anshal21
6068
accept rate: 7%

edited 17 Oct '16, 19:20

After determining the condition for a good string, I used $dp[i][j][k]$ where $i$ denotes the current position, $j$ denotes the state of first string and $k$ denotes the state of second string. State of a string is either "free" (next letter can be either 1 or 2), "open" (there is a single 2 and thus the next letter must be 2) and "closed" (there was a pair of 2s before so the $i$-th lettter must be 1). The state transitions are not hard once you get this idea.

My code

link

answered 17 Oct '16, 15:38

zscoder's gravatar image

6★zscoder
62813
accept rate: 6%

Seeing other people's solution, I guess my implementation was the best(very short). Code

link

answered 17 Oct '16, 15:46

rachitjain's gravatar image

5★rachitjain
1307
accept rate: 0%

link

answered 17 Oct '16, 16:12

nirjhor's gravatar image

6★nirjhor
812
accept rate: 0%

Nice ones, especially compared to mine (I wonder how such a mess might work at all) :D https://www.codechef.com/viewsolution/11847204

(17 Oct '16, 16:18) pkacprzak ♦♦5★

^That was so clean. Good job!

(17 Oct '16, 16:20) rachitjain5★

A pretty fast solution.

https://www.codechef.com/viewsolution/11823381

The logic being that at any index i, if ai=bi then we don't need to look out for anything. Now we divide the two strings into partitions - each partition [i,j] such that ai=bi and aj=bj and ak≠bk for k belonging to (i,j). In such partitions we can derive some conditions based on observed pattern. These conditions fulfill all the requirements of a 'good' string. The conditions are clearly written in my solution.

The problem was an ad-hoc one, with no special prerequisite.

link

answered 17 Oct '16, 16:14

utkarsh1997's gravatar image

4★utkarsh1997
77410
accept rate: 11%

I also did something similar, dividing string into parts where ai=bi=1. https://www.codechef.com/viewsolution/11825823

(17 Oct '16, 19:30) prakhariitd6★

The state space is small - N x 3 x 3. You could hard code and solve as an ad-hoc problem, but a dp solution would be easier to understand.

link

answered 17 Oct '16, 17:06

noob333's gravatar image

5★noob333
10414
accept rate: 0%

My solution did not pass all test cases only 6 but still my approach was as follows

I identified some conditions the string must satisy to be a good string. 1) second last element of the string must be 1, if 2 it is a bad string 2) 2 cannot appear independently it must always appear as 221 (except as last element)

So what I did was I looped through a[i] & b[i] dividing the elements into 'N' segments (a[p],b[p])->(a[q],b[q]) such that they are isolated by a[p-1]=b[p-1]=1 and a[q+1]=b[q+1].122122112211-> 112211221221 each such segment can have 2 ways of swapping their elements. So n such elements have pow(2,N) ways of swapping. Also count the no: places where a[i]=b[i] as countident. elements at identical places can be swapped in pow(2,countident) ways So final answer=pow(2,N+countident) Also make sure that in cases where a[i]=b[i]=2,a[i+1]=b[i+1]=2,a[i+2]=b[i+2]=1 both countident and N will count them so that condition must be checked seperately.

link

answered 18 Oct '16, 14:12

nan_1729's gravatar image

2★nan_1729
111
accept rate: 0%

edited 18 Oct '16, 14:15

codechef is very slow in updating editorials

link

answered 18 Oct '16, 14:45

akki28's gravatar image

4★akki28
783
accept rate: 10%

I think you should see my solution if you are not very good in dp(dynamic programming)
Solution

link

answered 17 Oct '16, 17:22

yb4singh's gravatar image

4★yb4singh
1215
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:

×15,719
×20

question asked: 17 Oct '16, 15:26

question was seen: 2,399 times

last updated: 20 Oct '16, 15:01