DCP-328: Reconstructing Blue Print of Life Back to All Problems

Hard String > Suffix Array/Suffix Tree

Dr. **Takiona** is a great geneticist. Currently he is researching on a life form which DNA consists of 26 amino acids. They are described from 'a' to 'z' in english alphabet. Where as human DNA bases comprises of only 4 amino acids. They are 'A','G','T', 'C'. For some strange reason Dr. Takiona gets only a single long strand of DNA. You can consider the DNA strand as a single long string like **'aaasdfteruiiiookxmndhfkkkkkkkrtyueiissdfert'**. Now Dr. Takiona doesn't want to experiment on that sample. Rather he wants to reconstruct the DNA strand and work on the copy strand and keep the original strand intact. But as construction technology for 26 amino acid based DNA is not cheap there is always a cost. Starting with an empty strand **G**, Dr. Takiona can perform **2** operations: 1. Add a character(amino acid base) to the end of **G** for **X** dollars. 2. Copy any of the substrings of **G**, which can have length in between 2 and **K** inclusive, and then add it to the end of **G** for **Y** dollars. (Keep in mind that after every operation **G** changes and you have to consider substrings of the new **G**) Now help Dr. Takiona calculate minimum amount of money he needs to reconstruct the DNA strand **S** of length **N**. Input: ------ The first line contains number of testcases **T (1 ≤ T ≤ 10)**. Next **(2xT)** lines each describe a test case over **2** lines: The first line contains 4 space-separated integers **N (1 ≤ N ≤ 30000)**, **X** , **Y (1 ≤ X, Y ≤ 10000)** and **K (2 ≤ K ≤ N)** respectively. The second line contains the DNA strand **S** (the DNA strand Dr. Takiona wishes to build). Output: ------- On a single line for each test case, print the minimum cost to reconstruct the DNA strand . Sample Input ------------ 2 9 7 8 4 aaaaaaaaa 9 15 12 9 abaabaccc Sample Output ------------- 37 102

Problem Setter:

Md. Khairullah Gaurab

Please login to submit solution to this problem.

Problem Limits

Language Time Limit (seconds)
C 5.00
C++ 5.00
C++14 5.00
C# 6.00
Go 6.00
Java 6.00
JavaScript 6.00
Objective-C 6.00
Perl 6.00
PHP 6.00
Python 6.00
Python3 6.00
Ruby 6.00
VB.Net 6.00

Problem Stats




# User Language Timing
01 Robbinb1993 Cpp14 0.02s
02 feodorv C 0.14s
03 Morass Cpp14 0.45s

Your feedback is our precious!

Or call +88 02 9853138 for support