This is an excellent problem! (If you really delve into it...)

First you need to understand what you are trying to solve. The descriptions are already very clear. This problem is nothing but a string matching task. Don't be confused by those "DNA", "gene" terms. If you don't understand, like many of you posted here, read again carefully and pay attention to the example given here. The example already covers all the cases you need to consider.

This problem makes you think about: What really slows down my string matching? Why this strategy is bad? You may need to see some test case files to know what you are really facing with. (100,000 pattern strings to search for, for each 'DNA' text string; file size up to several MB)

You need to know some advanced string matching algorithms, way beyond KMP, as you may know as a fast one. If you really don't, it is a perfect chance to learn about them this time! (And yes, other players here already gave you the hint Aho-Corasick algorithm is the one you should go after.) You need to understand why you are choosing AC instead of other advanced algorithms. AC is, to some extent, similar to KMP in its idea.

You will not only need to fully understand AC algorithm, but also make some implementation designing, because AC itself tells you the presence of a pattern string, while you need the "health score".

I don't know about AC and some other advanced string matching algorithms before doing this problem. It took me at least 8 hours to get all ACCEPTED. I feel really happy when I am done!

This is very poorly explained. Need to clarify with plain language, and give better examples.

That's my favorite challenge to date on this website. Made me learn about string search algorithms, then made me learn about code optimization. Thanks author.

Does anybody know how a sequence of genes comprised of overlaping genes should be handled?

It's not clear from the exercise if, once a sequence has been found, if it is maximal then another should be looked up even if it may have a lower value and is also overlapping the first sequence.

For example: gene "caaab" with gene pairs

b c aa aaa b

and health values

2 3 4 9 6

"aaa" (9) is healthier than two "aa"'s (4 * 2 = 8). Should the algorithm pick

"aaa",

"aa" + "aaa" (and the its swapped equivalent)

or the maximal value of overlapping sequences:

"aa" + "aaa" + "aa" or "aaa" + "aa"

This looks like it could only be solved through bruteforcing gene subsequences and check for a maximal value. The gene lookup could be optimized using a hash table but that seems pretty much it.

Very beautiful (and hard) problem. My super optimized solution in Python3 (easily passes all the test cases):

from math import inf
from bisect import bisect_left as bLeft, bisect_right as bRight
from collections import defaultdict

# ------------------------------------------------------------------------------
def getHealth(seq, first, last, largest):
  h, ls = 0, len(seq)
  for f in range(ls):
    for j in range(1, largest+1):
      if f+j > ls: break
      sub = seq[f:f+j]
      if sub not in subs: break
      if sub not in gMap: continue
      ids, hs = gMap[sub]
      h += hs[bRight(ids, last)]-hs[bLeft(ids, first)]
  return h

# ------------------------------------------------------------------------------
howGenes = int(input())
genes = input().rstrip().split()
healths = list(map(int, input().rstrip().split()))
howStrands = int(input())
gMap = defaultdict(lambda: [[], [0]])
subs = set()
for id, gene in enumerate(genes):
  gMap[gene][0].append(id)
  for j in range(1, min(len(gene), 500)+1): subs.add(gene[:j])
for v in gMap.values():
  for i, ix in enumerate(v[0]): v[1].append(v[1][i]+healths[ix])

# ------------------------------------------------------------------------------
largest = max(list(map(len, genes)))
hMin, hMax = inf, 0
for _ in range(howStrands):
  firstLastd = input().split()
  first = int(firstLastd[0])
  last = int(firstLastd[1])
  strand = firstLastd[2]
  h = getHealth(strand, first, last, largest)
  hMin, hMax = min(hMin, h), max(hMax, h)
print(hMin, hMax)