What's up y'all.

These past few years I spend an odd week here and there making roguelike-adjacent games. Most of them are mediocre (maybe outright terrible), although I did have one title that had relative success.

Recently, I (re)released my most recent creation — Wizard Chess 2. It's a combination of an encounter-based roguelite (think Slay the Spire) and a tactical battle (think Heroes of Might and Magic). Now look, I know the visuals and UX are, ahem, lacking, but the game has a lot of complexity of the kind that you, fellow competitive programmers, might find appealing. So I thought to invite you to give it a try :)

An imaginary conversation with you:

-Eldar, your css skills are shit
-I know

-And your UX is terrible, I can't figure out what's going on
-Very true. That said, you can watch my shitty tutorial and read the in-game help menus for _some_ info

-What was that about $$$ prizes?
-I'm glad you asked! I'm giving away Amazon gift cards for certain achievements: https://itch.io/t/2392425/-prizes. I swear they are achievable.

-Wait, I have to record a video to prove my results? Don't you already have a high score server?
-Unfortunately, because this is a browser-based game, it's not hard to cheat it in various ways, so a full video of the run is the only cheater prevention I could think of.

-Hey I just got to the first bossfight and the music turned into some demonic howling, wtf?
-Oh I forgot to warn you that I'm a big metalhead, so almost every bossfight has a metal soundtrack. In fact, the idea of playing Septic Flesh's "Pyramid God" during a bossfight compelled me to make this game in the first place.

-Okay you're weird
-I know

If you do give the game try and have a question, or something nice or constructive to say, please drop a note here or in the game's discussion forums. Love y'all <3

Hello friends!

As I've recollected in a previous post, I am an old competitor who hadn't really participated since ~2014, and recently got a bout of nostalgia to return to Competitive Programming. So, I did a couple Topcoder SRMs, suffered through some SNWS rounds, participated in three regional 5hr competitions on three consecutive days, and dozed off at every Codeforces contest I tried to wake up for.

A lot of things are still the same as 8 years ago: tourist is still at the top, grey coders still ask for how many minutes to solve a problem before reading the editorial, Russian university teams continue winning ACM ICPC, and Snarknews never gives up on his alternate competition formats. But in this post, I want to focus on the new patterns that emerged since my last time around.

#1: Codeforces rounds timing

Did you know that there used to be a time when not ALL the freaking CF rounds were held at 5:35pm MSK? Back in the day, no matter what timezone you were in, there would be an occasional round you could compete in without having to interrupt your sleep (or your work).

I'm personally pretty salty because 5:35pm MSK is like 6:35am in my timezone, and my brain simply refuses to operate for 2 consecutive hours this early in the day. And while a quick check of Ratings shows that most users are congregated in between Moscow and Japan timezones, I do wish we had rounds in more varied time slots.

#2: Petr and Java

Did you know that Petr used to write all contests in Java? Imagine you were looking for an intelligible implementation of any contest problem. You would sail through the ocean of C++ submissions filled with FOR0(n) and #define int long longs, and spot the safe haven of Petr's delightful Java solutions that read like a page from Dostoyevsky's masterpieces. His variable names alone could teach you more about solving this problem than the editorial itself. In fact, I was under an impression that Petr did not use prewritten code, and created each of his beautiful algorithms from scratch every time.

Well folks, those days are gone. Checking Petr's recent submissions, I noticed that he turned to the dark side and the values in his Lang column for over 2 years now show... this:

#3: The AtCoder library and the Codeforces Catalog

There is another curious pattern in the submissions of some top contestants: namespace atcoder and a myriad of data structures and algorithms that magically pop out of this namespace, like a rabbit from a magician's top hat. The source of all this sorcery seem to be the AtCoder library. I mean, come on, red and nutella coders, can't you even write your own min-cost max-flow over a network generated by lazy propagation segment tree with 2-SAT FFT butterflies stored in each node? Meh!

More generally, I can see there is a whole catalog here on CF, with links to tons of educational materials. And, in all seriousness, that's awesome — there was but a fraction of this available back when I was a student!

#4: The new MOD to rule them all

A lot of programming contest problems request to find some value modulo a large prime. The most common reason for this is that we are counting the number of ways to do something, but this quantity is extremely large. By requesting the answer modulo a large prime, we keep the calculations in a datatype that fits into machine word, thereby letting the solver focus on the "interesting" part of the problem.

10 years ago, the most common moduli used in contest problems were 1,000,000,007 and 1,000,000,009. These are nice, easy to remember big primes whose sum fits into a signed 32-bit datatype, making them perfect for the scenario above. Or maybe they were not, because fast-forward to today, I saw like 10 different problems requesting the answer modulo...

998244353

I mean, seriously, what the fuck is this? This is one ugly-ass forgettable prime and you should be ashamed for using it in your problems!

P.S. I found Petr's blog post discussing the properties of this number. And it seems like the problem where it was introduced at the time actually relied on these properties, but not every problem does! Also, this post is from 2014 — are y'all telling me you've been using nine-nine-eight-two-four-four-three-five-three in contest problems since 2014!?

#5: Probabilities modulo MOD

One of my favorite topics in programming contests was always probabilities and expectations. You can just feel the blood coursing through your veins when your dynamic programming solution prints out a sexy 0.07574094401. But y'all had to ruin this as well by introducing... probabilities modulo a prime!? o_O

Most probability theory-related problems I've seen in the past months request the answer modulo, you guessed it, 998244353, and proceed to add a note explaining that the answer can be represented as p/q where q is not a multiple of the given modulo. So essentially now to solve any problem with probabilities you have to also throw in some number theory and probably even more combinatorics. And you can't even receive a 0.07574094401 as an answer!

Can anyone explain how this new fad started?

#6: Li-Chao Segment Trees

Saving the best for last! A couple weeks back, I was delightfully reading Um_nik's list of things he allegedly does not know, and it was heralded by a data structure called a Li-Chao Segment Tree. I initially thought that this was a joke, but a quick google search revealed that people write tutorials on this thing.

Then I told myself that surely nobody would bring a problem utilizing a Li-Chao Segment Tree on Codeforces, but the very next Codeforces round editorial made sure to prove me wrong by mentioning a Li-Chao tree (I didn't dig into details, but you get the point!).

Come on guys, was Heavy-Light Decomposition not an obscure enough data structure to bring to contests? Someone has to stop this madness!

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? :)

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

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])
sort(f[1..m])
best = INFINITY
for k = 1 to m-n
  best = min(best, f[k+n-1] - f[k])
print best

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.

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
      ++ans

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:

44123424132
12424224132

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:

l1*p1*(1-p2)>l2*p2*(1-p1)
l1*p1*(1-p3)<l3*p3*(1-p1)
l2*p2*(1-p3)>l3*p3*(1-p2)
<=>
l1*p1/(1-p1)>l2*p2/(1-p2)
l1*p1/(1-p1)<l3*p3/(1-p3)
l2*p2/(1-p2)>l3*p3/(1-p3)

(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 :)

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.