In this Hackerrank Determining DNA Health problem we have given an array of numbers with a given DNA standard and we need to find and print the respective strands of DNA as two space-separated values on a single line.
Problem solution in Python programming.
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)Problem solution in Java Programming.
import java.io.BufferedReader;
import java.io.File;
import java.io.InputStreamReader;
import java.io.PrintStream;
import java.util.Arrays;
public class Solution {
private static String[] genes;
private static int[] health;
public static void main(String[] args) throws Exception {
PrintStream out = new PrintStream(System.out);
long startMillis = System.currentTimeMillis();
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(in.readLine());
genes = new String[n];
int longestKey = 0;
String[] genesItems = in.readLine().split(" ");
Trie trie = new Solution().new Trie();
for (int i = 0; i < n; i++) {
String genesItem = genesItems[i];
genes[i] = genesItem;
trie.insert(genes[i], i);
if (genes[i].length() > longestKey)
longestKey = genes[i].length();
}
health = new int[n];
String[] healthItems = in.readLine().split(" ");
for (int i = 0; i < n; i++) {
int healthItem = Integer.parseInt(healthItems[i]);
health[i] = healthItem;
}
//out.println("Longest key: " + longestKey);
//out.println("Loading: " + (System.currentTimeMillis() - startMillis)/1000f);
startMillis = System.currentTimeMillis();
int s = Integer.parseInt(in.readLine());
long maxH = 0, minH = Long.MAX_VALUE;
for (int sItr = 0; sItr < s; sItr++) {
String[] firstLastd = in.readLine().split(" ");
int first = Integer.parseInt(firstLastd[0]);
int last = Integer.parseInt(firstLastd[1]);
String d = firstLastd[2];
long total = 0;
int keyLen = d.length();
for (int i = 0; i < keyLen; i++) {
total += trie.find(d.substring(i, keyLen > longestKey && i + longestKey < keyLen? i + longestKey : keyLen), first, last);
}
if (total > maxH)
maxH = total;
if (total < minH)
minH = total;
}
in.close();
out.println(minH + " " + maxH);
out.close();
}
class Trie {
private final short SIZE = 26;
private TrieNode root;
public Trie () {
this.root = new TrieNode();
}
class TrieNode {
private TrieNode[] children = new TrieNode[SIZE];
private int index[];
private boolean isEnd;
public TrieNode(){
isEnd = false;
}
@Override
public String toString(){
return (index != null? Arrays.toString(index) + " " : "")
+ Arrays.toString(Arrays.stream(children).filter(p -> p != null).toArray());
}
}
public void insert(String key, int index) {
int arrayPos;
TrieNode node = root;
for (int i = 0; i < key.length(); i++) {
arrayPos = key.charAt(i) - 'a';
if (node.children[arrayPos] == null) {
node.children[arrayPos] = new TrieNode();
}
node = node.children[arrayPos];
}
if (node.index == null) {
node.index = new int[1];
} else {
node.index = Arrays.copyOf(node.index, node.index.length + 1);
}
node.index[node.index.length - 1] = index;
node.isEnd = true;
}
public long find(String key, int start, int end) {
int arrayPos;
TrieNode node = root;
long result = 0;
int keyLen = key.length();
for (int i = 0; i < keyLen; i++) {
arrayPos = key.charAt(i) - 'a';
if (node.children[arrayPos] != null) {
node = node.children[arrayPos];
if (node.isEnd
&& ( start <= node.index[node.index.length - 1]
|| end >= node.index[0])) {
int sI = -1, eI = -1;
for (int j = 0, k = node.index.length - 1; j < node.index.length && k >= 0; j++, k--) {
if (sI == -1) {
if (node.index[j] >= start)
sI = j;
else if (node.index[k] < start && k + 1 < node.index.length && node.index[k + 1] >= start)
sI = k + 1;
}
if (eI == -1) {
if (node.index[k] <= end)
eI = k;
else if (node.index[j] > end && j - 1 >= 0 && node.index[j - 1] <= end)
eI = j - 1;
}
if (j == k || (sI != -1 && eI != -1))
break;
}
if (sI != -1 && eI != -1) {
for (int j = sI; j <= eI; j++) {
result += health[node.index[j]];
}
}
}
} else
break;
}
return result;
}
@Override
public String toString() {
return root.toString();
}
}
}Problem solution in C++ programming.
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <cstdlib>
#include <map>
#include <set>
#include <queue>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct trie
{
vector<int> term;
struct trie* next[26];
struct trie* fail;
trie()
{
fail = NULL;
for (int i=0; i<26; i++)
next[i] = NULL;
}
};
trie *root;
void insert(char str[], int index)
{
trie* p = root;
int len = strlen(str);
for (int i=0; i<len; i++)
{
int idx = str[i]-'a';
if (p->next[idx]==NULL)
p->next[idx] = new trie();
p = p->next[idx];
}
p->term.push_back(index);
}
void buildfail()
{
queue<trie*> q;
q.push(root);
while(!q.empty())
{
trie* cur = q.front();
q.pop();
for (int i=0; i<26; i++)
{
if (cur->next[i] != NULL)
{
if (cur == root)
cur->next[i]->fail = root;
else
{
trie* p = cur->fail;
while (p!=NULL && p->next[i] == NULL)
p = p->fail;
if (p==NULL)
cur->next[i]->fail = root;
else
cur->next[i]->fail = p->next[i];
}
q.push(cur->next[i]);
}
}
}
}
vector<pair<vector<int>, int> > query(char str[])
{
vector<pair<vector<int>, int> > ret;
int len = strlen(str);
trie* p = root;
for (int i=0; i<len; i++)
{
int idx = str[i] - 'a';
while (p->next[idx] == NULL && p!=root)
p = p->fail;
if (p->next[idx] == NULL)
continue;
p = p->next[idx];
trie* pp = p;
while (pp != root)
{
if (!pp->term.empty())
ret.push_back(make_pair(pp->term, i));
pp = pp->fail;
}
}
return ret;
}
int main()
{
int n;
int health[100000];
char str[2000001];
scanf("%d", &n);
root = new trie();
for (int i=0; i<n; i++)
{
scanf("%s", str);
insert(str, i);
}
for (int i=0; i<n; i++)
scanf("%d", &health[i]);
buildfail();
int q;
scanf("%d", &q);
long long mins=9999999999999,maxs=0;
for (int i=0; i<q; i++)
{
int a,b;
scanf("%d %d %s", &a, &b, str);
vector<pair<vector<int>,int> > ret = query(str);
long long sum = 0;
for (int i=0; i<ret.size(); i++)
for (int j=0; j<ret[i].first.size(); j++)
if (ret[i].first[j] >= a && ret[i].first[j] <= b)
sum += health[ret[i].first[j]];
if (sum > maxs)
maxs = sum;
if (sum < mins)
mins = sum;
}
printf("%lld %lld\n", mins, maxs);
}Problem solution in C programming.
#include <assert.h>
#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char* readline();
char** split_string(char*);
typedef struct TreeNode {
char ch;
int* ids;
int idsLen;
bool isBlue;
struct TreeNode* child;
struct TreeNode* next;
struct TreeNode* suffix;
struct TreeNode* blueSuffix;
} TreeNode;
TreeNode* initNode() {
TreeNode* node = malloc(sizeof(TreeNode));
node->ch = 0;
node->ids = NULL;
node->idsLen = 0;
node->isBlue = false;
node->child = NULL;
node->next = NULL;
node->suffix = NULL;
node->blueSuffix = NULL;
return node;
}
void fillSuffix(TreeNode* root, int size) {
TreeNode** queue = malloc(size*sizeof(TreeNode*));
queue[0] = root;
int head = 0;
int tail = 1;
while (head<tail) {
TreeNode* node = queue[head++];
TreeNode* child = node->child;
while (child != NULL) {
TreeNode* parent_suf = node->suffix;
bool found_suf = false;
while (!found_suf && parent_suf != NULL) {
TreeNode* parent_suf_child = parent_suf->child;
while (parent_suf_child != NULL && parent_suf_child->ch != child->ch) {
parent_suf_child = parent_suf_child->next;
}
if (parent_suf_child != NULL) {
child->suffix = parent_suf_child;
found_suf = true;
} else {
parent_suf = parent_suf->suffix;
}
}
if (!found_suf) child->suffix = root;
queue[tail++] = child;
child = child->next;
}
}
free(queue);
}
void fillBlueSuffix(TreeNode* root, int size) {
TreeNode** queue = malloc(size*sizeof(TreeNode*));
queue[0] = root;
int head = 0;
int tail = 1;
while (head<tail) {
TreeNode* node = queue[head++];
TreeNode* child = node->child;
while (child != NULL) {
TreeNode* parent_suf = node->suffix;
bool found_suf = false;
while (!found_suf && parent_suf != NULL) {
TreeNode* parent_suf_child = parent_suf->child;
while (parent_suf_child != NULL && parent_suf_child->ch != child->ch) {
parent_suf_child = parent_suf_child->next;
}
if (parent_suf_child != NULL && parent_suf_child->isBlue) {
child->blueSuffix = parent_suf_child;
found_suf = true;
} else {
parent_suf = parent_suf->suffix;
}
}
if (!found_suf) child->blueSuffix = root;
queue[tail++] = child;
child = child->next;
}
}
free(queue);
}
TreeNode* contructTree(char** genes, int genes_count) {
TreeNode* root = initNode();
int size=1;
for (int i=0; i<genes_count; i++) {
TreeNode* node = root;
char* gen = genes[i];
int len = strlen(gen);
for (int j=0; j<len; j++) {
TreeNode* child;
if (node->child == NULL) {
child = initNode();
node->child = child;
size++;
} else {
child = node->child;
while (child->ch != gen[j] && child->next != NULL) child = child->next;
if (child->ch != gen[j]) {
child->next = initNode();
child = child->next;
size++;
}
}
node = child;
node->ch = gen[j];
if (j==len-1) {
node->isBlue = true;
if (node->idsLen == 0) {
node->ids = malloc(sizeof(int));
} else {
node->ids = realloc(node->ids, (node->idsLen+1)*sizeof(int));
}
node->ids[node->idsLen] = i;
node->idsLen++;
}
}
}
fillSuffix(root, size);
fillBlueSuffix(root, size);
return root;
}
TreeNode* getChildNode(TreeNode* node, char ch) {
TreeNode* child = node->child;
while (child != NULL && child->ch != ch) child = child->next;
return child;
}
long calHealth(TreeNode* tree, int* health, int first, int last, char* d) {
long result = 0;
TreeNode* cur = tree;
for (int i=0; i<strlen(d); i++) {
TreeNode* child = getChildNode(cur, d[i]);
while (child == NULL && cur->suffix != NULL) {
cur = cur->suffix;
child = getChildNode(cur, d[i]);
}
if (child != NULL) cur = child;
TreeNode* blue_suffix = cur;
while (blue_suffix != NULL) {
for (int i=0; i<blue_suffix->idsLen; i++) {
if (blue_suffix->ids[i]>=first && blue_suffix->ids[i]<=last) {
result += health[blue_suffix->ids[i]];
}
}
blue_suffix = blue_suffix->blueSuffix;
}
}
return result;
}
int main()
{
char* n_endptr;
char* n_str = readline();
int n = strtol(n_str, &n_endptr, 10);
if (n_endptr == n_str || *n_endptr != '\0') { exit(EXIT_FAILURE); }
char** genes_temp = split_string(readline());
char** genes = malloc(n * sizeof(char*));
for (int i = 0; i < n; i++) {
char* genes_item = *(genes_temp + i);
*(genes + i) = genes_item;
}
TreeNode* tree = contructTree(genes, n);
char** health_temp = split_string(readline());
int* health = malloc(n * sizeof(int));
for (int i = 0; i < n; i++) {
char* health_item_endptr;
char* health_item_str = *(health_temp + i);
int health_item = strtol(health_item_str, &health_item_endptr, 10);
if (health_item_endptr == health_item_str || *health_item_endptr != '\0') { exit(EXIT_FAILURE); }
*(health + i) = health_item;
}
char* s_endptr;
char* s_str = readline();
int s = strtol(s_str, &s_endptr, 10);
if (s_endptr == s_str || *s_endptr != '\0') { exit(EXIT_FAILURE); }
long* dna_healths = malloc(s*sizeof(long));
for (int s_itr = 0; s_itr < s; s_itr++) {
char** firstLastd = split_string(readline());
char* first_endptr;
char* first_str = firstLastd[0];
int first = strtol(first_str, &first_endptr, 10);
if (first_endptr == first_str || *first_endptr != '\0') { exit(EXIT_FAILURE); }
char* last_endptr;
char* last_str = firstLastd[1];
int last = strtol(last_str, &last_endptr, 10);
if (last_endptr == last_str || *last_endptr != '\0') { exit(EXIT_FAILURE); }
char* d = firstLastd[2];
dna_healths[s_itr] = calHealth(tree, health, first, last, d);
}
long minHealth = 1000000000000000000;
long maxHealth = 0;
for (int i=0; i<s; i++) {
if (minHealth>dna_healths[i]) minHealth=dna_healths[i];
if (maxHealth<dna_healths[i]) maxHealth=dna_healths[i];
}
printf("%ld %ld", minHealth, maxHealth);
return 0;
}
char* readline() {
size_t alloc_length = 1024;
size_t data_length = 0;
char* data = malloc(alloc_length);
while (true) {
char* cursor = data + data_length;
char* line = fgets(cursor, alloc_length - data_length, stdin);
if (!line) { break; }
data_length += strlen(cursor);
if (data_length < alloc_length - 1 || data[data_length - 1] == '\n') { break; }
size_t new_length = alloc_length << 1;
data = realloc(data, new_length);
if (!data) { break; }
alloc_length = new_length;
}
if (data[data_length - 1] == '\n') {
data[data_length - 1] = '\0';
}
data = realloc(data, data_length);
return data;
}
char** split_string(char* str) {
char** splits = NULL;
char* token = strtok(str, " ");
int spaces = 0;
while (token) {
splits = realloc(splits, sizeof(char*) * ++spaces);
if (!splits) {
return splits;
}
splits[spaces - 1] = token;
token = strtok(NULL, " ");
}
return splits;
}Problem solution in JavaScript programming.
'use strict';
process.stdin.resume();
process.stdin.setEncoding('utf-8');
let inputString = '';
let currentLine = 0;
process.stdin.on('data', inputStdin => {
inputString += inputStdin;
});
process.stdin.on('end', _ => {
inputString = inputString.replace(/\s*$/, '')
.split('\n')
.map(str => str.replace(/\s*$/, ''));
main();
});
function readLine() {
return inputString[currentLine++];
}
function Node() {
this.index = [];
this.indexH = [];
this.children = {};
}
function Trie() {
var root = new Node();
function add(word, node, index, health) {
var char, previousHealth = 0, len;
if (word === '') {
len = node.index.length;
if (len) {
previousHealth = node.indexH[len-1];
}
node.index.push(index);
node.indexH.push(health + previousHealth);
return;
}
char = word[0];
if (!node.children[char]) {
node.children[char] = new Node();
}
add(word.substr(1), node.children[char], index, health);
}
return {
add: function(word, index, health) {
add(word, root, index, health);
},
getRoot: function() {
return root;
}
}
}
function findIndex(arr, start, end, val) {
var index = Math.floor((end - start) / 2) + start;
if (arr[index] === val) return index;
if (arr[start] === val) return start;
if (arr[end] === val) return end;
if (arr[index] > val) {
end = index;
} else {
start = index;
}
if (end - start <= 1) {
if (arr[end] < val) {
return end;
}
return start;
}
return findIndex(arr, start, end, val);
}
function main() {
const n = parseInt(readLine(), 10);
const genes = readLine().split(' ');
const health = readLine().split(' ').map(healthTemp => parseInt(healthTemp, 10));
const s = parseInt(readLine(), 10);
var trie = new Trie();
var min = null;
var max = null;
genes.forEach((gene, index) => {
trie.add(gene, index, health[index]);
});
for (let sItr = 0; sItr < s; sItr++) {
const firstLastd = readLine().split(' ');
const first = parseInt(firstLastd[0], 10);
const last = parseInt(firstLastd[1], 10);
const d = firstLastd[2];
var len = d.length;
var dnaHealth = 0;
var getSum = function(cn) {
var cnIndexLen = cn.index.length;
var startIndex, endIndex;
if (cnIndexLen === 0) return;
startIndex = findIndex(cn.index, 0, cnIndexLen - 1, first - 1);
endIndex = findIndex(cn.index, 0, cnIndexLen - 1, last);
if (cn.index[endIndex] <= last) {
dnaHealth += cn.indexH[endIndex];
}
if (cn.index[startIndex] < first) {
dnaHealth -= cn.indexH[startIndex];
}
};
for (let i = 0; i < len; i++) {
var iter = i;
var node = trie.getRoot();
do {
node = node.children[d[iter++]];
if (!node) {
break;
}
getSum(node);
} while(iter < len);
}
min = min === null ? dnaHealth : Math.min(min, dnaHealth);
max = max === null ? dnaHealth : Math.max(max, dnaHealth);
}
console.log(`${min} ${max}`)
}
0 Comments