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

×

BSTRLCP - Editorial

PROBLEM LINK:

Practise
Contest

DIFFICULTY:

Medium - Hard

PREREQUISITS:

DP , Finite Automata/KMP , Bitmasking

PROBLEM:

Given positive integers $N$, $K$ and $M$, count how many binary strings $S$ of length $N$ exist such that there exist more than $M$ indices $i$ such that $LCP(S[1, i], S[i + 1, N]) ≥ K$ and $1 ≤ i < N$.

QUICK EXPLANATION :-

The problem is equivalent to finding the numbers of strings such that number of occurrence of $S[1,k] in S[k+1,N]$ is $>M$. We will fix the first $k$ bits by using a k-bit mask and solve the problem for each mask differently. Each problem can be solved by using a simple dp having a count of the number of occurrences till now, and the current match of the string alongwith the length. Then either add $0$ or $1$ . The complexity is $ O( 2^K * K * N * M)$.

DETAILED SOLUTION:-

For any string first lets find number of $i$ such that $LCP(S[1, i], S[i + 1, N]) ≥ K$ and $1 ≤ i < N$. If $LCP(S[1, i], S[i + 1, N]) ≥ K$, then it means that $S[i+1,i+K] = S[1,K]$. So basically if for a fixed $K$, this is equal to the number of occurrence of $S[1,k]$ in $S[k+1,N]$. Now for given $N,M,K$ we need to find number of binary strings in which the count of such occurrences are $>M$.

Since $K<=10$. We can solve the problem for each possible $S[1,k]$ ($2^k$ different strings). Let us denote $S[1,k]$ with a bitmask ‘mask’ and solve the subproblem differently for each mask and sum up the result. Now we will use dp to find out the no of such strings of length $N-K$ , in which the mask occurs $>M$ times.

Let $dp[len][matchCount][prefixMatch]$ denote the count of strings of length $len$ , which have the $mask$ occuring in them exactly $matchCount$ times and currently suffix of maximum length $prefixMatch$ matches the prefix of same length of mask.

For the $prefixMatch$ part, we we can use Finite Automata. I guess it can also be done by modifying KMP. Finite automata is more suitable and easy to visualize for this problem. You can read more about pattern matching from finite automata online. For the current prefix of the string, it keeps track of the max length suffix that matches the some prefix of the pattern. We create a transition table $state[a][b]$ for each mask, in which $a$ stands for the current state and $b$ stands for the next character. Now $state[a][b]$ denotes the next state in which it transitions. Here the index of the state denotes the maximum length prefix of pattern which matches with some suffix of the string.

Now whenever a compete match occurs we can update $matchCount$. And sum $dp[N-K][x][y]$ for all $x>M$ , and all $y$. The transitions are as follows:-

dp[a+1][b+(states[str][c][0]==k?1:0)][states[str][c][0]] += (dp[a][b][c]); dp[a+1][b+(states[str][c][1]==k?1:0)][states[str][c][1]] += (dp[a][b][c]);

where $states[str][x][y]$ denotes the value of $state[x][y]$ for $mask str$.

Setter's Solution

asked 06 Dec '15, 12:01

vy007vikas's gravatar image

3★vy007vikas
112
accept rate: 0%

edited 08 Dec '15, 21:29

admin's gravatar image

0★admin ♦♦
19.8k350498541

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:

×1,250
×643
×281
×49

question asked: 06 Dec '15, 12:01

question was seen: 885 times

last updated: 08 Dec '15, 21:29