gojira's blog

By gojira, history, 2 days ago, In English

Hello friends!

I hope a few of you might still remember me. This old dinosaur participated in very early rounds of Codeforces, and before that did Topcoder for a number of years. I've been away from competitive programming for several years now, but the recently started Advent of Code rekindled the spark, and I proceeded to open Topcoder arena and participate in the recent SRM.

To my utter befuddlement, there were less than 100 participants in Div 1 in this SRM — and looking through recent match history, it seems to be a fairly standard participation rate for a while now. For comparison, back in the good days Topcoder Div 1 routinely had several hundreds of coders.

I've got to admit that seeing this saddened me considerably — I have a ton of fond memories of competing at Topcoder, like rushing those 250-pointers, taking perpetually unsuccessful stabs at 1000-pointers, the violent heartbeat as I pressed the "Challenge" button every time, the nervous fidgeting in anticipation of System Tests that would reveal who stood tall, and who was bound to fall. I have a lot of nostalgia for those days..

So, I wanted to ask y'all — what happened to Topcoder? Did most old-timers stop competing, and the new generation just does not know about it? Did the website redesign hide the Arena applet so deep that you can't find it? Is the Arena just not user friendly enough, so everyone ran towards shinier platforms (wink wink)? Are the problems not as fun anymore?

Share your story — why did YOU stop competing? :)

Read more »

  • Vote: I like it
  • +126
  • Vote: I do not like it

By gojira, 8 years ago, translation, In English

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.

Read more »

Announcement of Rockethon 2014
  • Vote: I like it
  • +75
  • Vote: I do not like it

By gojira, 8 years ago, translation, In English

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
  // 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

Read more »

Tutorial of Rockethon 2014
  • Vote: I like it
  • +101
  • Vote: I do not like it

By gojira, 8 years ago, translation, In English

337A - Puzzles

First, let's sort the numbers f[i] in ascending order. Now assume that the smallest jigsaw puzzle which the teacher purchases consists of f[k] pieces. Obviously, she should buy the smallest n puzzles which are of size f[k] or greater to minimize the difference. These are the puzzles f[k], f[k+1], ..., f[k+n-1] (this is not correct when f[i] are not distinct and f[k]=f[k-1], but such cases can be skipped). The difference between the greatest and the least size of the puzzles in such set is f[k+n-1]-f[k].

To choose the optimal f[k], we can test every k between 1 and m-n and pick the one producing the least difference. The full algorithm is as follows:

read(n, m, f[1..m])
for k = 1 to m-n
  best = min(best, f[k+n-1] - f[k])
print best

Read more »

  • Vote: I like it
  • +171
  • Vote: I do not like it

By gojira, 8 years ago, translation, In English

Hello everyone!

Codeforces Round #196 will begin in several hours (August 16, 20:00MSK).

You will mostly have to deal with Manao's problems, which this time range from watching movies and taking quizzes to treebuilding and battling evil undead.

I'd like to thank the following people for their contribution to this round's preparation: the Codeforces problem coordinator Gerald; Seyaua, who tested the problems; Delinur, who translated the problem statements into English; and Aksenov239, who proof-read the statements.

The points distribution in both divisons will be standard.

By the way, Sammarize mentioned he was probably the eldest author of a Codeforces round in the Russian version of his latest round's announcement. Since I'm even older, now I am holding the title ;)

The contest is over, I really hope that enjoyed it. The standings: Div1, Div2. Congratulations to top performers in Div1:

  1. tourist
  2. ilyakor
  3. al13n
  4. aa2985759
  5. rng_58

Congratulations to the winner of Div2, Ruthles, too!

The problem analysis is here.

Read more »

  • Vote: I like it
  • +263
  • Vote: I do not like it

By gojira, 9 years ago, translation, In English

268A - Games

With only 30 teams, the simplest solution is simulating all the matches:

for i = 1 to N
  for j = 1 to N
    if i != j and h[i] = a[j] then

An O(N + M) solution is also possible, where M is the length of colors' range (i.e. 100 under the given constraints). First, you need to count for each color i the number of teams cntH[i] which have the home uniform of color i and the number of teams cntA[i] which have the away uniform of color i. The answer is the sum of products of these quantities for each color, i.e. sum of cntH[i] * cntA[i] over all i.

268B - Buttons

Let us first detect the worst case scenario. It is more or less apparent that when Manao tries to guess the i-th (1 <= i <= n) button in order, he will make n-i mistakes in the worst case. After that the correct button is evident.

Now let's count the total number of presses Manao might need before he guesses the whole sequence. When he is guessing the first button he makes n-1 mistakes, but the "mistake cost", i.e. the number of presses before the mistake is made, is equal to 1. When Manao goes for the second button, the mistake cost becomes 2, because each time Manao needs to press the first (already guessed) button. Continuing like this, we obtain that when Manao tries to guess the i-th button in order, he will perform (n-i) * i button presses.

After Manao guessed the correct sequence, he needs to enter it once, which is another n presses.

So we already have an O(n) algorithm: sum up (n-i)*i for i=1, ..., n-1 and add n to the sum obtained.

When n is anything that fits in 32-bit integer type, the task is solvable in O(1)*. The sum (n-i)*i is two separate sums: the sum of n*i and the sum of i*i. The first sum is n*(1+...+n-1), which can be computed with the sum of arithmetic progression. The second sum is the sum of squares from 1 to n-1, which can be evaluated with a polynom of degree 3: http://pirate.shu.edu/~wachsmut/ira/infinity/answers/sm_sq_cb.html

*The only problem is that the answer for large n-s does not fit even in 64-bit integer type, but at least we can compute its remainder from division by anything.

268C - Beautiful Sets of Points

Obviously, if a set contains a point (x', y'), it can not contain any other point with x=x' or y=y', because these two points would be an integer distance apart. There are only n+1 distinct x-coordinates and m+1 distinct y-coordinates. Therefore, the size of the set sought can not exceed min(n, m) + 1.

If the constraint x+y>0 was not present, the set of points (i, i) (0 <= i <= min(n, m)) would do nicely. The distance between two points (i, i) and (j, j) is equal to |i-j|*sqrt(2) and can only be integer when i=j. On the other hand, there are min(n, m) + 1 points and we already know that we can't take more than that.

Since point (0, 0) is restricted, we can take the other "diagonal", i.e. use points (i, min(n, m) - i).

268D - Wall Bars

Those who are well experienced at dynamic programming can scroll down to "Overall solution" right away. Those who have some experience in DPs can read my attempt to explain how you can come up with that solution. Those with no experience probably shouldn't read this at all :)

Imagine a solution which considers all possible designs, adding the bar-steps one by one. Consider any sequence, like 2123412413. There are 4 ways to continue this sequence by appending '1', '2', '3' or '4' to it. For each of the 4^n wall bars / strings we need to check that for at least one of {'1', '2', '3', '4'} character the following is true: its first entry in the string is at position no more than h, each next one differs from the previous by no more than h and the last one is beyond position n-h.

Surely, such a solution won't work for large n-s in any reasonable time, but we can start from it in the search of a better approach. First, let's note that we can check the feasibility of the string after each character addition: if somewhere in the middle of string we noticed that for each of the characters the necessary conditions are broken, there is no reason to complete the string. Also, note that we don't need the whole prefix to check the validity of the conditions after each character addition. All we need to know is when each of the '1', '2', '3' and '4' characters occured last, and whether the conditions for each of the characters have been fulfilled up to this point. It turns out that two prefixes in which [each of the characters last occured at the same position] and [the validity of the conditions for each character are equal], are absolutely equivalent for the brute force algorithm's further operation. That is, for example for h=4 these two prefixes can be completed (up to length n) in the same number of ways:


The last time each of the characters have occured at the same positions, characters '1' and '3' are already "lost" (the conditions are already broken for them), characters '2' and '4' can still turn the string into a valid one.

With the help of the observations made, we can already build a polynomial-time algorithm based on dynamic programming principle. Let ways[curN][i][j][k][l][ii][jj][kk][ll] be the number of designs of height curN, where the last step in direction 1 was at height i, the last step in direction 2 — at height j and so on; ii, jj, kk, ll are boolean parameters which indicate whether the conditions are valid in the corresponding direction. When we choose the direction for the step at height curN+1, we obtain a design with curN+1 steps, the last step in the direction we chose is now at height curN+1 and rest stay where they were. Conditions validity can also be reassessed. Since curN is always one of {i, j, k, l}, we can obtain a O(n^4) algorithm. However, this is still too slow.

Another observation: if we are looking at a bar at height curN and the last step in this direction was earlier than curN-h steps ago, we don't really care which height was it exactly at, since this direction is not valid any more. Therefore, the number of states in our algorithm can be only O(n*h^3). Moreover, those ii,jj,kk,ll parameters correlate with the heights of the latest steps in the corresponding directions, so we can (almost) get rid of them, thus reducing the number of states in a number of times.

On the base of these observations we can probably build different solutions. I will tell mine.

Overall solution

We will keep a 5-dimensional DP :) Let ways[curN][alive][last1][last2][last3] be the number of designs where:

  • There are exactly curN steps.

  • If the direction of the latest step if still "alive", then alive = 1, otherwise it's equal to 0. A direction is alive if its first step was not higher than h and each subsequent one was higher than the previous by at most distance h.

  • last1, last2 and last3 keep the information about the other directions in any order. lasti can be zero in two cases: if there were no steps in the corresponding direction, or if the latest one was earlier than h steps before. Otherwise, lasti is the number of steps between the current step and the latest step in the corresponding direction.

We can optimize by keeping last1<=last2<=last3, which reduces the number of states in roughly 6 times. However, this complicates the code and doesn't have a significant effect (since the transitions processing becomes costly). Thus I will not consider it at all.

What transitions can be made from state [curN][alive][last1][last2][last3]? We shall process the states in order from curN=1 to curN=N-1. ways[1][1][0][0][0] (i.e. a single step) is equal to 4 as a base case. So we have:

  • If we add a step in the same direction as the latest (i.e. the one at height curN), then we obtain state [curN+1][alive][last1+1][last2+1][last3+1] (roughly): curN has increased by 1; the "livingness" of the direction of the last step could not change; all the lasti-s have increased by 1. However, note that for lasti=0 it should not be incremented (the corresponding step either does not exist at all, or is way below). Also, for lasti=h-1 it turns to zero (the last step is now too low).

  • If we put the step in the same direction as the one which was at height last1, we obtain state [curN+1][last1 > 0 || curN < h][alive][last2+1][last3+1]. This decyphers in the following way: if last1>0, then this condition is alive. last1 could also be 0, but the number of already built steps less than h — in which case this is the first step and the direction becomes alive by putting it. The direction denoted by last1 has been replaced (in the state parameters) by the one in which the curN-th step was sticked out. Therefore, it was 1 step ago and we should write [1] there. On the other hand, that direction could already be dead and we would need to write [0]. It turns out that the value coincides with value of alive. last2 and last3 change in the same way as in the previous case.

  • Directions last2 and last3 are treated in the same way as last1.

When we process a transition, the number of designs corresponding to the new state increments by ways[curN][alive][last1][last2][last3]. So the overall answer is sum of all [n][1][a][b][c], where 0<=a,b,c<h plus sum of all [n][0][a][b][c], where at least one of a, b, c is non-zero. So we have an algorithm of O(n*h^3) complexity which needs asymptotically the same amount of memory. Its implementation could catch ML (especially on Java). This can be handled through the following observation: since we only need values [i-1][][][][] to compute [i][][][][]-s, only O(h^3) states need to be kept at any given moment.

Well, before writing this analysis I didn't realize it was so huge :)

You can check SteamTurbine's solution at 3027309 for a very compact implementation of a similar idea.

268E - Playlist

Let us first find the answer for a fixed sequence of songs. Consider any two songs which are at positions i and j (i < j) in the playlist. If Manao liked song i and disliked song j, then song i will be listened to again. Therefore, with probability p[i]*(1-p[j]) the process length will increase by L[i]. The sum of L[i]*p[i]*(1-p[j]) over all pairs (plus the length of all songs since Manao listens to them at least once) is the expected length for the fixed sequence.

So we have that if there are two songs (l1, p1) and (l2, p2), the first one should be placed earlier in the playlist if l1*p1*(1-p2)>l2*p2*(1-p1) and later otherwise. This is obviously true if there are only two songs. But suppose that we have more and you ask, why can't there be another song (l3, p3) such that the above inequality rules out that the first song should be after this one and the second song should be before it? Then it's unclear which of the orders results in the maximum expected value. Consider this case in details:


(this is not quite true if any pi is equal to 0 or 1, but that's not important here)

We have a contradicting system of inequations, so such a case is impossible.

Next, let's consider some order of songs (l[1], p[1]), ..., (l[n], p[n]), in which there is a pair of neighbouring songs i and i+1, for which the condition l[i] * p[i] * (1 - p[i + 1]) >= l[i + 1] * p[i + 1] * (1 - p[i]) does not hold, and assume that this order is optimal. Evidently, if we interchange songs i and i+1, the answer will only change by the value contributed by this pair (i.e. l[i] * p[i] * (1 - p[i + 1])). The rest of the songs keep their order towards song i and song i+1. But l[i] * p[i] * (1 - p[i + 1]) < l[i + 1] * p[i + 1] * (1 - p[i]), therefore if we put song i+1 before song i, we obtain a larger value. So we have a contradiction — the order chosen is not optimal.

So it turns out that the permutation with maximum possible expected value is obtained when sorting the songs in decreasing order of l[i]*p[i]/(1-p[i]). But we still have a problem of computing the answer for a fixed permutation: we only learned how to do this in O(n^2), which is too slow with n=50000. We can use an idea which is probably a yet another dynamic programming example. Suppose we have fixed j and are counting the contribution of song j towards the answer if Manao dislikes it. This value is (l1*p1 + l2*p2 + ... + l[j-1]*p[j-1]). For j+1, the corresponding value will be (l1*p1+...+l[j-1]*p[j-1]+l[j]*p[j]). It turns out that these values differ in only a single summand, so we can compute each of them in O(1) if we consider j-th one by one in increasing order. This idea can be expressed as follows:

lovedLenExp = 0.
answerExp = 0.
for j = 1 to N
  answerExp += l[j]
  answerExp += lovedLenExp * (1 - p[j])
  lovedLenExp += l[j] * p[j]

That's all :)

Read more »

  • Vote: I like it
  • +150
  • Vote: I do not like it

By gojira, 9 years ago, translation, In English

Hello everyone!

The Codeforces Round #164 for Div.2 participants will start in several hours. Traditionally, the other participants can take part out of competition.

The hero of today's problems is Manao, which has been straining Georgian fellow programmers' minds for several years already. He made it to Codeforces pages thanks to Gerald and Delinur, who have assisted me in round preparation. The problems were also tested by Seyaua, sdya and Aksenov239.

The scoring system will be a little unusual: 500-1000-1500-2500-2500.

Good luck :)

UPD: The contest is over, congratulations to the winners:

  1. first_love

  2. dianbei_10

  3. yefllower

  4. dpij

  5. cenbo

You can find the tutorial here.

Read more »

  • Vote: I like it
  • +189
  • Vote: I do not like it