Hello Codeforces community,

I am happy to announce that Rocket Fuel Inc. will soon be hosting a contest called Rockethon on Codeforces. The contest is prepared by Rocket Fuel employees Jon Derryberry, Alexander Ruff and me, Eldar Bogdanov. We hope you will have as much fun solving the problems as we had crafting them. The contest will feature prizes and T-shirts for top performers. Also, Rocket Fuel is interested in hiring the best of you after this event, so let me tell you about the company and why you would want to join us.

About Rocket Fuel

Rocket Fuel is building technology platform to do automatic targeting and optimization of ads across all channels — display, video, mobile and social. Our pitch to advertisers is very simple "If you can measure metrics of success of your campaign, we can optimize". We have run campaigns for many large advertisers. Examples include BMW, Pizza Hut, Brooks Running Shoes and many more!

We buy all our inventory through real time bidding on ad exchanges like Google and Yahoo. Ad exchanges are similar to stock exchanges except the commodity being traded is ad slots on web pages. Our serving systems currently process 40B requests/ day (~6X Google search volume), 600K requests/ second at peak with response time requirement of 100ms. Our data platform has several PBs data that is used for analytics as well as modeling.

Our engineering team is still small (~100) enough for any one person like yourself to make a huge impact. The team represents many top schools in US and outside — Stanford, CMU, MIT, Wisconsin-Madison, IIT (India), Tsinghua (China).

Rocket Fuel has been named #4 on Forbes Most Promising Companies in America List in 2013 and #1 Fastest Growing Company in North America on Deloitte’s 2013 Tech Fast 500.

In this post you will find the authors' solutions for the problems and subproblems featured in the competition, as well as some bonus questions related to these tasks.

391A - Genetic Engineering

Note that we can consider each maximal sequence of identical characters independently, since there is no way to insert a character and affect more than one such sequence. Also, note that there are multiple ways to correct a single maximal sequence by inserting one character into it: we can either insert a different character somewhere in this sequence and divide it into two sequences of odd length (this is always possible for a sequence of even length), or even just add the same character in any point of this sequence, thus increasing its length by 1 and changing its parity.

Therefore, the answer to the problem is the number of maximal sequences of even length. One can find all such sequences in linear time. A pseudocode of the solution follows:

i = 1
ans = 0
while i <= length(s) do
  end = length(s) + 1  // we will use this value if current sequence is the last in this string
  for j = i + 1 .. length(s)
    if s[j] <> s[i] then
      end = j
      break
  // at this point, we have the next maximal sequence of identical characters between i and j-1, inclusive
  if (j - i) mod 2 = 0 then
    ans = ans + 1
  i = j