CODEWITHSUNDEEP
algorithmstringgraphdynamic-programming
Lin Jin
Lin Jin

Reputation: 113

A problem about algorithm of string, dp, graph or sth else

problem is following.

  1. about "nice"

    1) "ab" is nice

    2) A is nice => "a"+A+"b" is nice

    3) A and B are nice => A+B is nice

  2. about "~"

    1) "ab"~"ab"

    2) A~B => "a"+A+"b"~"a"+B+"b"

    3) A~B and C~D => A+C~B+D and A+C~D+B

now there are at most 1000 string of 'a' and 'b' forming a set S, find the biggest subset of S in which every element must be nice and none of pair (A,B) holds A~B. Output the Cardinality.

There are sth different from the problems i see before: A+B+C+D~A+C+B+D~B+D+A+C but A+B+C+D~B+D+A+C doesn't hold.

Two difficulties for me:

  1. how to check whether S1~S2
  2. if i know every pair's "~", how can i find the cardinality

more detail: https://www.spoj.pl/problems/ABWORDS/

Upvotes: 3

Views: 274

Answers (1)

lijie
lijie

Reputation: 4871

The rules for constructing a nice word imply that every nice word starts with "a" and ends with "b". Hence, there is a unique (up to sequencing - rule 3) decomposition of a nice word into nice sub-words: find all "ab"s, and then try to expand them using rule 2, and sequence them using rule 3. We can express this decomposition via a tree (n branches for repeated application of rule 3).

In the tree context, the "~" relation is simply expressing isomorphic trees, I think (where branch order does not matter).

EDIT: as pointed out, branch order does matter.

I'll attempt to solve the problem as stated in the original link (the 2 definitions of "nice" doesn't coincide).

First, similarity between two words X and Y, using DP.

Define f(a, b, n) to be the function that indicates that X[a..a+2n-1] is similar to Y[b..b+2n-1] and that both subwords are nice.

f(a, b, 0) = 1.

for n > 0,

f(a, b, n) = f1(a, b, n) or f2(a, b, n) or f3(a, b, n)
f1(a, b, n) = x[a] == y[b] == 'a' and x[a+2n-1] == y[b+2n-1] == 'b' and f(a+1, b+1, n-1)
f2(a, b, n) = any(1 <= k < n) f(a, b, k) and f(a+2k, b+2k, n-k)
f3(a, b, n) = any(1 <= k < n) f(a, b+2(n-k), k) and f(a+2k, b, n-k)

I think this is O(n^4) (urgh).

For the second part, if you represent the words as a graph with edges representing the similarity relation, you are essentially trying to find the maximum independent set, I think. If so, good luck! It is NP-hard (i.e. no known better solution than to try all combinations) in the general case, and I don't see any properties that make it easier in this :(

EDITED to make the definition of similarity automatically check niceness. It is quite easy.

EDITED yet again because of my stupidity.

Upvotes: 1

Related Questions