11197 - Counting RNA sequences

[rio]

With my poor English, I can't understand the statement well.
Could someone explain this problem with simple words ?

Thanks in advance.
----
Rio

[rujialiu]

Count the number of RNA primary sequences that are compatible with n secondary structures.

primary sequence: a string of A,C,G,U.
secondary structure: a well-formed dot-bracket sequence.

a primary sequence S is compatible with a secondary structure P:
* Len(S)=Len(P)
* if P(a)='(', P(b)=')', and they are MATCHED. then (S(a),S(b)) must be one of (A,U),(U,A),(C,G),(G,C),(G,U),(U,G). in the problemset they are called canonilal base pairs

convince yourself by examing the sample I/O with explanation

[rio]

Thanks, rujialiu I understood it.

Now solving ....

EDIT : Solved Thanks.
----
Rio

[sclo]

I keep getting TLE for this problem.

Here's my idea:
I treat each base as a vertex. Each base pairing becomes an edge, resulting in a graph.
I count the number of valid colouring of that graph using standard backtracking.
Here's a quick way of checking valid colourings:
Let the set of colours be {0,1,2,3}
If there's an edge between vertex u,v and that c(u),c(v) be their colours respectively, then abs(c(u)-c(v)) == 1

However, I get tle. Is there other stuff that I missed?

[little joey]

Some things to note (they may be spoilers):

- when doing backtracking, you're in fact building a bfs-forest; are you sure you calculate every tree in it only once?

- consider the back-edges in a bfs-tree; what simple property must they obey that can be checked before the actual back-tracking?

- how many different colors do you need to give to a root of a bfs-tree?

That are my considerations, but I can't beat Rio's splintering time...

[rio]

I think my solution is very close to little joey's, except I'm using dfs (not bfs) + bactrack.
The idea that killed the time was:

- Using dfs, you don't need to color all the nodes. (This way needs little precalculation)

Example.

Code: Select all

b ---- a ---- c ---- d ---- e
                     |      |
                     |      |
                     g ---- f

Starting backtrack with node a, and got dfs-tree:

Code: Select all

b <--- a ---> c ---> d ---> e
                            |
                            v
                     g <--- f

Need to consider only the color of a, b and d.

ADD : Didn't write the detail of the idea to avoid to be a spoiler. But maybe enough to give you some inspiration.
ADD2 : Sory for my poor English. After posting, even I couldn't understand my sentence well
----
Rio

[sclo]

Rio: I don't quite understand what you mean by only considering coloring of a,b,d. Could you explain it a bit more?

Little Joey: I do check the distances to avoid odd cycles. In that case I don't even do the backtracking. Also, the root is only colored in 2 colours. That's because color i and 3-i are complementary.

[little joey]

I must have been very tired when writing the above; I meant a dfs-tree too (bfs = brute force search builds a dfs-tree... it's so confusing).

[rio]

I'll try to explain a little bit more.

First, precalculate the table: (colors are numbered 0, 1, 2 and 3)

Code: Select all

tbl[i][j][k] := How many ways to color a straight graph which two sides colored with i and j, and the graph length is k.

Using this table, the ways to color the graph ubove is: (node a is colored with i)

Code: Select all

(tbl[i][0][1] + tbl[i][1][1] + tbl[i][2][1] + tbl[i][3][1]) * 
(tbl[i][0][2]*tbl[0][0][4] + tbl[i][1][2]*tbl[1][1][4] + tbl[i][2][2]*tbl[2][2][4] + tbl[i][3][2]*tbl[3][3][4])

The first term is coloring b, and the second is coloring d.

I hope you understand my English.
----
Rio

[sclo]

Thanks everyone, I finally found my mistake that resulted in TLE, I was recomputing the dfs tree too many times because I forgot to store some index, resulting in backtracking each node more than once.

Rio: the idea is very nice, I'll try modifying my code and see the level of improvement.