TL;DR: Come solve 3 spooky problems a day in October 2025 Long Challenge from October 27 through November 3, UTC 4am time.

I'm hosting a Halloween-themed contest on EldarVerse! Each day will feature three problems of increasing difficulty — from something like Codeforces Div2 A to something like Div2 E.

I want to thank asdasdqwer, JunkieDonkey, fextivity, and likithreddy949 for their help testing the problemset.

Special thanks to Golovanov399 for additional testing on a short notice <3

Hope to see you on the leaderboard!

P.S. Contest format is a mix of Meta Hacker Cup (download inputs, submit outputs) and Advent of Code (each problem is worth 100 points, each subsequent solver gets 1 less point).

Hello friends,

I'm conducting a Halloween contest on EldarVerse from October 26, and would greatly appreciate some help in testing it!

To be upfront — there will be 7x3 problems, at least 7 of which are of Div2 D+ difficulty, so I expect it to be a significant time commitment for most people. I guess Grandmasters+ can solve it as a 5-hour training contest for practice :)

What's in it for you?

• Your name will be immortalized on EldarVerse platform

• You'll get a Tester badge in your EldarVerse profile (badges coming soon)

• You'll have my gratitude

• Training practice

If interested, please DM me (the_eldar7) on Discord and specify your Codeforces handle. (Codeforces painfully rate limits low-rated users like me, so DMing here will take time.) I'll wait for a couple days and pick 2-3 testers to work with. Thanks everyone!

I'm pretty sure that something is off with the time conversion utility when you hover over a post/comment's "X minutes ago" timestamp field. Seriously, go hover over your recent comment and see what time it says you posted it.

Example:

I'm in PST timezone, and it's 2:53 pm (14:53) right now.

I created a draft blog post and hovered over its timestamp field with "a moment ago" in it. I see it claim that it's 04:53 in UTC-7 timezone:

Ahoy mateys!

Invite

TL;DR: Come solve 2 problems a day in September 2025 Long Challenge from September 1 through September 7, UTC 5am time.

Each day will feature an easy and a hard(er) problem. The harder problems are Div2 D+ level, so I imagine the contest will have something interesting for most participants. Hope to see you there!

I want to thank speedermen and wery0 for their help testing the problems and the platform. These guys have been a joy to build stuff with; if you see them somewhere, please give them a big upvote!

Meta

A couple weeks back, I posted about vibe coding a programming challenges platform. I was rather happy with the output, so I fine-tuned it further and added some more features:

• Contest message log. No pubsub notifications, just a simple table below the problem list that displays notifications directly from the database. It has automated notifications for e.g. a problem being solved for the first time, and allows me to insert arbitrary messages for e.g. problem statement changes.
• Profile page. You can now pick how you want to be displayed — your GitHub username (if you OAuthed with GitHub), your Google name (if you OAuthed with Google), or Player #1234.
• Groups. I needed some way for users to organize into custom leaderboards, and really tried to avoid copying the corresponding Advent of Code feature — but in the end, it turned out that with my leaderboard architecture it was the only viable option.

In the backend, I fixed a critical database interaction bug (I used an old-school connection pooler instead of pgBouncer, which resulted in stress-tests of any magnitude making the database unavailable for 1 minute), and added metrics through PostHog, which honestly is an amazing tool even on the free tier.

Finally, I picked the domain name — and in my apparent bout of megalomania, I named the platform EldarVerse. In all honesty, it's pretty hard to find .com domains related to puzzles/programming that somebody isn't squatting on, and I didn't want to agonize over the name any longer.

Turns out that Codeforces Talks has a strict limit on the number of unique users you can message per hour. The limit is 2 :/

But there also seems to be a strict limit on the number of unique users you can message per day. That limit also seems to be 2, but there is some bug in its enforcement. Specifically, today I somehow managed to message 3 people, but now any message I send (both to new people and to people I've already sent a message today) gets blocked with You exceeded your daily quota of 2 distinct recipients.

Sample repro:

time X - send message to user A
time X - send message to user B
(now you're blocked from sending messages to anyone but A or B for 1 hour)
time X+1hr - send message to user C
(now you're blocked from sending messages to ANYONE AT ALL)

P.S. Apologies to anyone who sent me a message in response to my testing request and hasn't heard back — I'll (hopefully) respond tomorrow.

Codeforces,

I recently introduced HackerZone (placeholder name — would love better suggestions!) here to community's mild amusement. I plan to conduct a week-long contest in the beginning of September on this platform. Is anyone interested in helping me out by testing it?

To be upfront — with 14 problems, half of them Div2 D+ difficulty, I expect it to be a significant time commitment for most people. I guess Grandmasters+ can solve it as a 5-hour ACM contest for practice :)

What's in it for you?

• Your name will be immortalized on HackerZone platform
• You'll have my gratitude
• Training practice

DM me if you're interested! Thanks everyone.

Hello old friends!

I recently decided to run an experiment: could I build an entire programming challenges platform using nothing but an AI assistant?

This post covers how that went, what I ended up with, and a few “you can’t make this up” moments along the way. You can check it out here (and solve problems in the ongoing contest) — feedback is welcome.

Final architecture

• Next.js frontend + backend on Vercel
• Supabase Postgres for Users, Contests, Problems (including input/output files), and Submissions
• Private GitHub repo for problem development, plus a script to upsert them into the DB
• Redis cluster on Redis-Cloud for leaderboards and caching

Development anecdotes

Day 1: instant success → instant disaster

July 28. I open Cursor IDE, set it to claude-4-sonnet, and say: “Make me a programming contest site with multiple contests, output-based submissions (no code execution), scalable to hundreds of people.”

Minutes later, it spits out a seemingly working site: contest list, problem pages with download/upload buttons, and a leaderboard. I’m amazed.

Then I ask it to “clean something up” before I commit to Git. It deletes the entire source code. Not kidding — I even saw it panic in its “thoughts” log when I asked why. Too late.

Rebuild: the honeymoon’s over

I rerun the same prompt… and the site looks worse. A lot worse. Leaderboards are just static pages. Output checkers are on the client side. “Login” is literally a toggle button. To be fair, I have no idea if everything worked on the old page either. We'll never know.

This is a snapshot from the first GitHub commit:

The styling was equally cursed. It made my leaderboard name orange, then picked an almost identical color for the highlight — so my name disappeared entirely. Basically, anything it couldn’t verify with a test was suspect.

Leaderboards from hell

Cursor swore its DB was optimized for hundreds of users. Turns out its “optimization” was: whenever someone submits, delete all leaderboard data, rescore every submission, rebuild the ranking. I moved leaderboards to Redis before it could melt.

I briefly considered async updates via a queue (leaderboard can be eventually consistent), but the added complexity didn’t feel worth it. Redis updates happen inline now.

Getting Cursor to actually implement leaderboard logic was painful. Wrong-attempt counting, penalty times, optimization problem scoring — it kept getting the rules wrong. I ended up with a giant suite of unit tests that ran on every small change just to keep it from breaking things.

The Upstash facepalm

Cursor suggested Upstash (free 100K requests/month). I hooked it up… then realized:

• No persistent connections — every Redis call is a REST API call with extra latency.
• One leaderboard page load makes dozens of calls.

Yeah, no. Switched to Redis-Cloud. Still no clue why it thought Upstash was a good fit.

Security fun

Supabase’s anonymous key has to be public for client access. But production dashboard immediately warned me: without Row Level Security (RLS), this means anyone could run:

fetch(`${SUPABASE_URL}/rest/v1/submissions?id=neq.fake`, {
  method: 'DELETE',
  headers: {
    'apikey': ANON_KEY,
    'Authorization': `Bearer ${ANON_KEY}`
  }
})

...and nuke all submissions. Guess who had no RLS? :D

Final thoughts

~55 hours of Cursor time, ~ $30 in Enterprise fees, and zero frontend experience later, I’ve got a working — and maybe scalable — contest platform.

In terms of cost, the current architecture can be free, but not for long:

• Vercel allows 1M "function invocations" per month on the free tier. Any API call / SSR page load is a function invocation. So I can reasonably expect a user to make hundreds of these during a contest. To scale beyond 1M calls, you gotta pay $20 per month + $0.6 per additional 1M calls.
• Redis-Cloud offers a tiny instance (30MB RAM/dataset size) for free; a 1GB RAM instance costs something like $5/month
• Supabase offers 500MB database for free; for $25/month you get 8GB and other perks

So running this architecture at scale would cost over $50/month (and if it really took off, it would be prohibitively expensive because of all these pay-for-what-you-use providers).

Future

Assuming there is interest, I plan to host some contests on the platform — e.g., replay Google Code Jam rounds, bring problems from some old obscure contests most of you have never seen, and maybe even host an original round. Surely it can't get too popular :P

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

Привет, Codeforces!

От лица компании Rocket Fuel Inc. я рад анонсировать соревнование по программированию "Rockethon", которое состоится на Codeforces. Контест подготовлен сотрудниками Rocket Fuel в составе Джон Дерриберри, Александр Рафф и я, Эльдар Богданов. Мы надеемся, что вы получите не меньше удовольствия от решения задач, чем мы от их подготовки. Лучшие участники получат призы и футболки. Кроме того, Rocket Fuel заинтересованы в рекрутинге сильнейших из вас, поэтому позвольте рассказать немного о нашей компании и почему надо у нас работать.

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), 700K 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 - Генная инженерия

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 - Пазлы

В первую очередь, упорядочим числа f[i] по возрастанию. Теперь допустим, что самый маленький пазл, который приобретет учительница, состоит из f[k] фрагментов. Понятно, что в таком случае для минимизации разницы она должна приобрести наименьшие n пазлов, равных или превосходящих f[k] по размеру, то есть пазлы размеров f[k], f[k+1], ..., f[k+n-1] (это не совсем правильно, если среди f[i] встречаются повторяющиеся числа и выполняется f[k]=f[k-1], но такие случаи можно не рассматривать). Разница между наибольшим и наименьшим количествами фрагментов в таком наборе равняется f[k+n-1]-f[k].

Чтобы выбрать оптимальное f[k], переберем значение k от 1 до m-n и выберем наименьшую возможную разницу. Таким образом, весь алгоритм выглядит следующим образом:

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

Всем привет!

Через несколько часов (16 августа, 20:00MSK) начнется Codeforces Round #196.

Главным образом вам снова придется помогать Манао, задачи которого на этот раз варьируют от просмотра фильмов и участия в викторинах до древостроения и борьбы с нечистью.

Хочу поблагодарить за помощь в подготовке раунда координатора задач Gerald; Seyaua, который тестировал задачи; Delinur, которая переводила условия на английский язык; и Aksenov239, который вычитывал условия.

Разбалловка в обоих дивизионах будет стандартная.

Также добавлю, что я даже старше, чем Sammarize, поэтому перехватываю титул самого старого автора Codeforces-раунда до появления следующего претендента ;)

Контест окончен, я очень надеюсь что он вам понравился. Результаты: Див1, Див2. Мои поздравления лучшей пятерке первого дивизиона:

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

Также поздавляю победителя второго дивизиона Ruthles!

Разбор задач можно найти здесь.

268A - Матчи

При ограничении в 30 команд самое простое решение заключается в симуляции всех поединков:

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

Существует также решение, работающее за O(N + M), где M — длина диапазона номеров цветов (то есть 100 при данных ограничениях). Для начала нужно посчитать для каждого цвета i количество команд cntH[i], у которых домашняя форма цвета i, и количество команд cntA[i] с выездной формой цвета i. Ответ задачи — сумма произведений этих количеств для каждого отдельного цвета, то есть сумма cntH[i] * cntA[i] по всем i.

268B - Кнопки

Для начала озвучим наихудший сценарий. Более-менее очевидно, что в худшем случае при угадывании i-ой (1 <= i <= n) по счёту кнопки Манао должен допустить n-i ошибок, потому что после этого становится понятно, какая кнопка правильная.

Посчитаем, сколько в сумме нажатий потребуется Манао прежде, чем он поймёт, какая именно последовательность кнопок правильная. При угадывании первой кнопки он допускает n-1 ошибку, но "цена ошибки", то есть на сколько кнопок нужно нажать чтобы её допустить, равна 1 нажатию. При угадывании второй кнопки цена ошибки уже 2 нажатия, потому что каждый раз приходится набирать первую (уже известную) кнопку. Продолжая в том же духе, получается что при угадывании i-ой по счёту кнопки Манао сделает (n-i) * i нажатий.

После того, как Манао понял правильную последовательность, ему остаётся её один раз ввести, что требует ещё n нажатий.

Отсюда получается алгоритм за O(n): просуммировать (n-i)*i для i=1, ..., n-1, и добавить к полученному числу n.

При значениях n, которые не выходят за диапазон 32-битных целых чисел, можно решать задачу и за O(1)*. Раскроем сумму (n-i)*i = n*i - i*i. Сумма первых слагаемых — это n*(1+...+n-1), где нам поможет сумма арифметической прогрессии. Сумма вторых слагаемых — это сумма квадратов от 1 до n-1, что вычисляется с помощью кубического полинома: http://pirate.shu.edu/~wachsmut/ira/infinity/answers/sm_sq_cb.html

*Единственная проблема — что ответ при больших n не умещается даже в 64-битный целый тип данных, но можно например вычислять его остаток при делении на что-нибудь.

268C - Красивые множества точек

Очевидно, что когда в множестве есть некоторая точка (x', y'), в нём не может быть никакой другой точки с x=x' или y=y', потому что тогда между этими двумя точками обязательно было бы целое расстояние. Есть всего n+1 различных x-координат и m+1 различных y-координат. Соответственно, размер искомого множества не может превосходить min(n, m) + 1.

Без условия x+y>0 нам бы подошло множество из точек (i, i) (0 <= i <= min(n, m)). Расстояние между точками (i, i) и (j, j) равно |i-j|*sqrt(2) и может быть целым только при i=j. С другой стороны, таких точек min(n, m) + 1, а мы уже знаем, что больше взять невозможно.

Раз точку (0, 0) использовать нельзя, сменим "диагональ": будем использовать точки (i, min(n, m) - i).

268D - Шведская стенка

Те, кто хорошо знаком с динамическим программированием, могут скроллить сразу вниз до "Итогового решения". Те, у кого есть некоторый опыт в этой теме, могут почитать мою попытку объяснить, как дойти до итогового решения. У кого опыта нету, тем наверное большого смысла это читать нету :)

Представим себе решение, которое перебирает все возможные дизайны, постепенно добавляя ступеньки снизу вверх. Например, допустим что оно уже выбрало направления для первых 10 ступенек и они вот такие: 2123412413 (то есть первая палка торчит в направлении 2, вторая — в направлении 1 и так далее). Теперь есть четыре варианта продолжить эту последовательность, приписав к ней '1', '2', '3' или '4'. Для каждой из 4^n стенок-строк нам нужно проверить, что для хотя бы одного символа выполняется следующее условие: первое его вхождение в строку не дальше позиции h, каждое следующее отстоит от предыдущего не более чем на h позиций, а последнее далее позиции n-h.

Естественно, такое решение при больших значениях n за разумное время не работает, но от него можно оттолкнуться в поисках лучшего подхода. Заметим, что проверку строки можно делать при добавлении каждого нового символа: если оказалось, что где-то посередине строки для всех четырех символов нужные условия уже не выполняются, то не имеет смысла перебирать её до конца. Также заметим, что нам не нужна вся строка для того, чтобы проверять при добавлении символа выполнение условий. Достаточно лишь знать, когда в последний раз встретился каждый из символов '1', '2', '3' и '4', и выполнялись ли для них условия до сих пор. Но тогда получается, что два префикса, у которых [каждый из символов в последний раз встретился на одних и тех же позициях] и [для каждого из символов выполнение/невыполнение условий совпадает], абсолютно эквивалентны с точки зрения дальнейшей работы такого перебора. То есть например при h=4 следующие два префикса можно окончить (то есть дополнить их до любой длины n) равным количеством способов:

44123424132
12424224132

Последний раз каждый из символов встретился на одной и той же позиции, символы '1' и '3' для обеих строк уже "потеряны", то есть условия для них уже не выполняются, а символы '2' и '4' ещё могут обратить строку в удовлетворительную.

На основе сделанных наблюдений уже можно построить полиномиальный алгоритм, основанный на принципе динамического программирования. Пусть ways[curN][i][j][k][l][ii][jj][kk][ll] будет количеством дизайнов стенки, в которых есть curN штук ступенек, последняя ступенька, торчащая в направлении 1, была на высоте i, в направлении 2 — на высоте j и так далее; ii, jj, kk, ll — boolean переменные, обозначающие, выполняются ли до сих пор условия для ступенек в соответствующих направлениях. Направив ступеньку на высоте curN+1 в одном из направлений, мы получим дизайн с curN+1 ступеньками, где эта последняя ступенька будет на высоте curN+1, а другие останутся на своих местах. Выполнение условий тоже можно и нужно пересчитать. Учитывая, что curN всегда равен одному из {i, j, k, l}, можно получить алгоритм со сложностью O(n^4). Так как это слишком медленно, подробно его разбирать не стану.

Сделаем следующее наблюдение: если мы сейчас рассматриваем палку на высоте curN, а последняя палка в некотором направлении была раньше чем curN-h палок назад, то нас не интересует, на какой конкретно высоте она была — это направление уже непригодно. Получается, что количество состояний в нашем алгоритме можно сделать порядка O(n*h^3). Более того, параметры, отвечающие за выполнение условий в каждом из направлений, коррелируют с высотами последних ступенек в этих направлениях, так что при желании от них можно (почти) избавиться, уменьшая количество состояний ещё в несколько раз.

На основе сделанных наблюдений можно наверное построить в некоторой степени разные решения, я расскажу своё.

Итоговое решение

Как ни странно, давайте заведём пятимерную динамику :) Пусть ways[curN][alive][last1][last2][last3] будет количеством таких дизайнов, где:

• Ровно curN ступенек

• Если то направление, в котором торчит последняя ступенька, всё ещё "живое", то alive = 1, в противном случае 0. Живое направление — это в котором первая ступенька была не выше h, а каждая следующая была не больше чем на h над предыдущей.

• last1, last2 и last3 содержат информацию об остальных трех направлениях. Направления никак не пронумерованы. lasti = 0 в двух случаях: если в соответствующем направлении ступенек не было вообще, или если последняя была более чем h ступенек назад. В остальных случаях в lasti записано, сколько ступенек назад была ступенька в этом направлении, то есть разница между curN и высотой последней ступеньки в данном направлении.

В целях оптимизации можно иметь last1<=last2<=last3, что уменьшает количество состояний примерно в 6 раз. Тем не менее, это усложняет код и в этой конкретной задаче особого выигрыша не давало (потому что обработка переходов стала более долгой). Переходы я буду рассматривать без учета данной оптимизации.

Теперь рассмотрим обработку переходов из конкретного [curN][alive][last1][last2][last3]. Обрабатывать состояния мы будем в порядке от curN = 1 до curN = n-1. ways[1][1][0][0][0] (то есть поставлена лишь первая ступенька) положим равным четырем, как базисный случай. Так вот:

• Если следующей мы ставим ступеньку в том же направлении, что и последняя (та, что на высоте curN), то мы грубо говоря получаем состояние [curN+1][alive][last1+1][last2+1][last3+1]: curN увеличилось на 1; направление, в котором поставили последнюю ступеньку, если было "живое", то определенно так и осталось и не могло "ожить" если не было; все lasti увеличились на один. Тут надо уточнить, что если lasti было равно 0, то его увеличивать нельзя (этой ступеньки или не была, или была но слишком давно). Также надо уточнить, что при lasti=h-1 оно превращается в 0 (последняя ступенька уже слишком низко).

• Если следующей мы ставим ступеньку в направлении, где последней была ступенька на высоте last1, то получаем состояние [curN+1][last1 > 0 || curN < h][alive][last2+1][last3+1]. Расшифровка: если last1>0, тогда это направление "живое". Также last1 может быть 0, но количество имеющихся ступенек быть меньше h — тогда это может быть лишь первой ступенькой и поставив её, мы будем иметь "живое" направление. На месте направления, за которое отвечал параметр last1, теперь то, в котором смотрела последняя ступенька. Соответственно, она была 1 ступеньку назад и надо написать там [1]. Но возможно, что это направление уже было мертвое и тогда надо написать [0]. Получается, что оно совпадает со старым значением alive. last2 и last3 меняются как и в прошлом пункте.

• Направления last2 и last3 обрабатываюся аналогично направлению last1.

Когда мы переходим по переходу этой динамики, новому состоянию добавляется количество вариантов, которым получалось старое. Итоговый ответ — сумма по всем [n][1][a][b][c], где 0<=a,b,c<h, плюс сумма по всем [n][0][a][b][c], где хотя бы одно из a, b, c ненулевое. Таким образом, у нас есть алгоритм со сложностью O(n*h^3), которому нужно асимпотически столько же памяти. Если его неаккуратно реализовывать (особенно на Java), то он словит ML. Лечится это дело несложно: так как для вычисления значений [i][][][][] нужны лишь значения [i-1][][][][], можно в любой конкретный момент запоминать лишь O(h^3) состояний.

Да уж, до написания разбора она мне такой громоздкой не казалась :)

Можете посмотреть решение пользователя SteamTurbine: 3027309, там довольно компактная реализация похожей идеи.

268E - Плейлист

Для начала давайте найдём ответ для фиксированной последовательности песен. Рассмотрим любые две песни, которые стоят в плейлисте на местах i и j, i < j. Если Манао понравилась песня i и не понравилась j, то произойдёт повторное прослушивание песни i. Соответственно, длина процесса с вероятностью p[i]*(1-p[j]) увеличится на L[i]. Сумма L[i]*p[i]*(1-p[j]) по всем парам (плюс сумма всех длин песен, потому что Манао их один раз послушает точно) и есть мат. ожидание для фиксированного порядка.

Получается, что из двух песен (l1, p1) и (l2, p2) следует поставить раньше первую, если l1*p1*(1-p2)>l2*p2*(1-p1), и вторую в противном случае. Если у нас всего две песни, то это очевидно. Если у нас есть ещё песни, то можно сказать — а вдруг, несмотря на то что это неравенство выполняется, есть ещё третья песня (l3, p3), для которой с первой песней неравенство определит, что надо её ставить до этой первой, а для второй — что после второй? Тогда было бы непонятно, какой из порядков даёт максимальное мат.ожидание. Посмотрим на этот случай пристально:

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)

(Тут я закрыл глаза на факт, что p[i] могут быть равны 0 или 1, но это не важно)

Что за фигня, у нас противоречие! Видимо таких случаев не бывает :)

Далее, рассмотрим некоторый порядок песен (l[1], p[1]), ..., (l[n], p[n]), где существует пара соседних песен i и i+1, для которых не выполняется l[i] * p[i] * (1 - p[i + 1]) >= l[i + 1] * p[i + 1] * (1 - p[i]), и допустим, что этот порядок оптимален. Очевидно, что при замене местами песни i и i+1, ответ изменится на ту величину, которую в него вносила именно эта пара песен (имеется в виду величина l[i] * p[i] * (1 - p[i + 1])). Все остальные песни остались относительно каждой из песен i и i+1 в том же порядке. Но мы имеем l[i] * p[i] * (1 - p[i + 1]) < l[i + 1] * p[i + 1] * (1 - p[i]), значит, поставив песню i+1 перед песней i, мы получим большую величину. Таким образом, получаем противоречие — изначальный порядок был неоптимален.

Получается, что надо всего лишь упорядочить песни по убыванию l[i]*p[i]/(1-p[i]) для достижения перестановки с максимальным мат.ожиданием. Осталась проблема вычисления ответа для конкретной перестановки: до сих пор мы это умели делать только за квадрат, что при n=50000 многовато. Тут можно использовать идею, которая наверное тоже в какой-то мере является примером динамического программирования. Допустим, мы зафиксировали j и считаем, сколько песня j добавляет к ответу, если Манао она не понравится. Это величина (l1*p1 + l2*p2 + ... + l[j-1]*p[j-1]). Для j+1 аналогичная величина будет иметь вид (l1*p1+...+l[j-1]*p[j-1]+l[j]*p[j]). Раз эти величины отличаются на 1 слагаемое, можно их пересчитывать за O(1), если рассматривать j один за другим по возрастанию. Идею вычисления ответа для фиксированной перестановки можно выразить вот так:

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

Вот в принципе и всё :)

Всем привет!

Через несколько часов начнется Codeforces Round #164 для участников Div.2, но традиционно остальные могут поучаствовать вне конкурса.

Главным героем в задачах будет Манао, немало лет напрягавший умы грузинских участников. Добраться до страничек Codeforces ему помогли Gerald, помогавший мне в подготовке раунда, и Delinur, которая перевела условия на английский, за что им отдельное спасибо. Также задачи тестировали Seyaua, sdya и Aksenov239.

Распределение баллов по задачам немного нестандартное: 500-1000-1500-2500-2500.

Удачи :)

UPD: Соревнование завершено, поздравляем победителей:

1. first_love

2. dianbei_10

3. yefllower

4. dpij

5. cenbo

Разбор задач можно найти здесь.