- RNA consists of one strand (chain of ribonucleotides) most of the time,
and sometimes it can fold into the secondary structure. In this problem
we consider a simpler secondary form than in real life. In this form,
some pairs of complementary ribonucleotides build hydrogen bonds between
them and each ribonucleotide can build at most one bond. Each bond can
be represented as a pair of indices (i,j) (i<j) of
the string S that represents RNA. These indices indicate the positions
of the symbols in S corresponding to these ribonucleotides.
Also, in the secondary structure one additional condition holds for each pair of hydrogen bonds (i1,j1), (i2,j2), such that i1<i2:
- they do not intersect i1<j1<i2<j2))
- or the second bond is inside the first one (i1<i2<j2<j1).
My first solution:
import sys
import math
def norm(str1, str2):
return math.fabs(int(str1) - int(str2))
def check_perfect(s):
len_s = len(s)
loops_tops = []
for i in range(1, len_s):
if norm(s[i], s[i - 1]) == 1:
loops_tops.append(i)
if len(loops_tops) == 0:
return False for start in loops_tops:
step_right = 0 step_left = 1 move = True while move:
right = int(s[start + step_right])
left = int(s[start - step_left])
if (right == 9) or (left == 9):
move = False elif norm(left, right) != 1:
move = False else:
s[start + step_right] = '9' s[start - step_left] = '9' if ((start + step_right + 1) >= len_s) or ((start - step_left - 1) < 0):
move = False step_right += 1 step_left += 1 new_s = [x for x in s if x != '9']
len_new_s = len(new_s)
if len_new_s == 0:
return True else:
if len_new_s == len_s:
return False else:
return check_perfect(new_s)
def check_perfect_if_one_hole(s):
len_s = len(s)
if len_s == 1:
return True holed_tops = []
for i in range(2, len_s):
if norm(s[i], s[i - 2]) == 1:
holed_tops.append(i - 1)
for hole in holed_tops:
s1 = s.copy()
del s1[hole]
if check_perfect(s1):
return True loops_tops = []
for i in range(1, len_s):
if norm(s[i], s[i - 1]) == 1:
loops_tops.append(i)
if len(loops_tops) == 0:
return False for start in loops_tops:
step_right = 0 step_left = 1 move = True while move:
right = int(s[start + step_right])
left = int(s[start - step_left])
if (right == 9) or (left == 9):
move = False elif norm(left, right) != 1:
if (start + step_right + 1) < len_s:
if norm(int(s[start + step_right + 1]), left) == 1:
s1 = s.copy()
del s1[start + step_right]
if check_perfect(s1):
return True if (start - step_left - 1) > -1:
if norm(right, int(s[start - step_left - 1])) == 1:
s1 = s.copy()
del s1[start - step_left]
if check_perfect(s1):
return True move = False else:
s[start + step_right] = '9' s[start - step_left] = '9' if ((start + step_right + 1) >= len_s) or ((start - step_left - 1) < 0):
move = False step_right += 1 step_left += 1 new_s = [x for x in s if x != '9']
len_new_s = len(new_s)
if len_new_s == len_s:
return False else:
return check_perfect_if_one_hole(new_s)
s0 = sys.stdin.readline()
s0 = s0.replace('\n', '')
s1 = s0.replace('U', '2')
s2 = s1.replace('A', '1')
s3 = s2.replace('G', '5')
s4 = s3.replace('C', '6')
s = list(s4)
lens = len(s)
if lens % 2 == 0:
if check_perfect(s):
print('perfect')
else:
print('imperfect')
else:
if check_perfect_if_one_hole(s):
print('almost perfect')
else:
print('imperfect')
Hint:
One could notice that the previous Dynamic Programming solution
resembles the solutions for problems with bracket sequences. We could
see a perfect string as a correct bracket sequence and we check the
correctness of bracket sequences using stack!
So, to check if the string is perfect we iterate through bases and maintain a stack:
- If the current base is complementary to the base on top of the stack, then we pop from the stack.
- Otherwise, we put the current base into the stack.
If there is no base in the stack, then the given string is perfect.Now,
how to understand that the string is almost perfect? The simplest
solution will be to delete each symbol and check the resulting string to
be perfect. Unfortunately, such solution works in
O(|S|2)
time and does not fit into timelimit.
But
the way to deal with it is quite easy. Let us perform the solution as
in the case of the perfect string. We state that if the string is almost
perfect then the base to delete is the middle base of the stack. We
remove this base and check that the stack collapses. (In other words, we
check that the stack has odd length and it holds a palindrome)
So, suitable solution is:
import sys
def complementary(a, b):
if (a == 'A' and b == 'U') or (a == 'U' and b == 'A') or (a == 'G' and b == 'C') or (a == 'C' and b == 'G'):
return True else:
return False
def go_stack(str):
stack = []
for i in str:
if len(stack) > 0:
if complementary(stack[-1], i):
stack.pop()
else:
stack.append(i)
else:
stack.append(i)
return stack
s = sys.stdin.readline().strip()
stack = go_stack(s)
len_stack = len(stack)
if len_stack == 0:
print('perfect')
else:
if len_stack % 2 == 0:
print('imperfect')
else:
stack.pop(int((len_stack - 1)/2))
stack2 = go_stack(stack)
if len(stack2) == 0:
print('almost perfect')
else:
print('imperfect')
