SYNBAC - Editorial

vijju123 · August 14, 2019, 6:28pm

PROBLEM LINK:

Div1
Div2
Practice

Setter- Alei Reyes
Tester- Suchan Park
Editorialist- Abhishek Pandey

DIFFICULTY:

Challenge

PRE-REQUISITES:

A Knack of Programming .

PROBLEM:

Given a genome G, you need to modify using mutations (replacing characters) or reversals (reversing a subarray) it to get proteins and minimize the amount of Chef coins spent on the process.

QUICK-EXPLANATION:

Key to Good Score- Trying to get the initial sequence T tended to give high scores! Test Generation Plan cannot be ignored.

Try to generate the shortest string , say T' by which all proteins could be generated. This string will let you generate a lot of proteins and has given contestants a good score. Realize that buying a protein is pretty expensive, so tend to generate as many proteins as you can. To get T', you can use algorithms of DNA Sequencing which use things like Eulerian Paths &etc.

Another way is to divide the protein P_i into chunks, and mutate the genome G to contain those chunks (if it does not have them already), and move then chunks using reversal operations to finally group them to make P_i

EXPLANATION:

For the editorial of challenge problem, we will discuss some of the solutions - some trivial, some complex - and try to get a high-level abstraction of the idea.

The very first thing which one sees on opening this problem is a long statement. And an equally long test generation plan. And somewhere between it, there is a line that you need to generate at least 50 proteins - you cannot buy all. This cost a few submissions to many div2 users. . Now, some people feel long things are scary (especially a 6.9999 star guy around here) - but trust me, once you read them you’d realize things are so simple. The length is there so that things do not seem complex to you.

The next naive trick which many people (tried to) use was to see which proteins are of shortest length and make them. A few variants of it were there - but more or less everyone got a similar score. ( < 1 if I recall correctly ).

After this naive solution, almost every one else (whose code was a little bit readable ) tried to mess with G and attempt to get T or something similar.

For starters, @alei pointed out that there exists an algorithm known as “Reversal Sort” (or “sort reversals”) which can yield a required permutation P_t given some starting permutation P_i. (More about it here ). This can help you for cases where N_M=0 and provide some improvement in the score.

Another variant is, to obtain the sequence T by somehow obtaining the smallest string T' by which all proteins can be manufactured. This was actually used by wjli (as he described here ) . Now, this is actually a pretty complex step. Some people tried to do this for all proteins while some tended to first select randomly which K proteins they would want the genome to make, and then find T' for them and then see if they can squeeze in anymore proteins. At this part, randomized algorithms, string matching algorithms like KMP etc. and optimizations like Hashing etc. can be used.

Its noteworthy to mention that some contestants did explore the background behind the problem, and exploited some known algorithms/methods. For instance, one can apply concepts of algorithms like BLAST after generating T'.

And thats it from the analysis from our side - for now . Ending the editorial with a common quote, which has for long motivated people across all divisions to score better in challenge problem-

“See that TL of 5 seconds? Use it! What good is your solution if it runs in 0.01 second and gets a score of 0 ? Worst case, just keep trying random solutions/permutations and give the best result. USE THAT PRECIOUS COMPUTATION TIME! YES YOU CAN! DO IT! JUST DO IT!”

SOLUTION

I’d like to invite every body to share their approach for the challenge problem and how they fared. Even if your approach is covered in the editorial, you can always highlight upon your learnings and contribute to a informative discussion

CHEF VIJJU’S CORNER

Hall of Fame:
- @wjli - He has written a wonderful editorial here . Do give it a read - and when you do, DO NOT FORGET TO GIVE IT A . Thanks to him for sharing his approach
- ??? - Could be YOU! Just let us know what you did

Beginners on Challenge Problems

For beginners, I’d say that keep exploring the challenge problems without getting disheartened. Challenge problems are open ended problems where you put all the concepts you currently know to test! This is also the perfect platform to see how someone else used those concepts, and as well as get introduced to new concepts to learn. Prizes are given top Top 3 challenge problem scorers, and let me tell you from my personal experience - all that it sometimes takes is to have a grasp on concepts, figure out which out of them is best applicable, and use randomizations (whereever applicable) properly to give only the best solutions