Competitive programming guides.

When somebody asks about best guides for competitive programming, my first reaction is:
* A. Shen: "Programming: theorems and problems"
* Cormen Leiserson Rivest Stein: «Introduction to Algorithms»

Web:
* max algo - static site with a lot of interesting and useful algorithms
* sirius pythonic algo courses
* sirius c++ algo courses

New for me resources:
* competitive programming chectsheet https://usaco.guide/
* demos for algorithms https://t.me/python_ready/1986

MapReduce in The Farmer Was Replaced

Code discussion. Part II.

In the previous post we discussed the code which uses map reduce approach to farm sunflowers. We reviewed the drone_map_reduce(objects, f_map, f_red) function line-by-line and realized that:
👉🏻 objects is an array of tasks descriptions
👉🏻 f_map - a factory function that creates a task from its description
👉🏻 f_red - reducer function, merges results into one big result if necessary

Today we are going to discuss how this framework applies to solving three sunflower tasks: till the entire field, plant sunflowers, harvest sunflowers with x5 bonus.

Till the field

def till_field():
 columns = []

 for x in range(get_world_size()):
  columns.append(x)

 def till_column(columns):
  def g():
   for q in columns:
    for p in range(get_world_size()):
     nav(q, p)
     till_soil()
  return g

 drone_map_reduce(columns, till_column, no_reduce)

Let's check this code. First, we prepare a list of columns to till. Then we prepare the factory function till_column, which takes a list of columns to process and returns... Attention!!! - a function to till all these columns. It uses helper functions: nav for navigation and till_soil for tilling grassland into Soil (it doesn't till it back). We use quite an interesting trick - nested function g inside the function till_column. It captures the columns variable and therefore is self-aware, it can run with no parameters. In "normal" programming it is like "partial" function which binds parameters with values. This function is called inside the spawn_drone function and determines the drone's actions and its lifetime.

Plant sunflowers

def plant_sunflowers():
  drone_jobs = []
  
  for q in range(get_world_size()):
    drone_jobs.append(q)

  def drone_job(columns):
    def g():
      heights = dict()
      for q in columns:
        for p in range(get_world_size()):
          nav(q, p)
          plant(Entities.Sunflower)
          heights[(q, p)] = measure()
      return heights
    return g

  def reduce_hights(h1, h2):
    for k in h2:
      h1[k] = h2[k]
    return h1
  
  return drone_map_reduce(drone_jobs, drone_job, reduce_hights)

The first part is quite familiar - forming a list of columns to process. The drone_job function is again a factory of functions. Again, these functions are quite similar to previous till_column. But now we have an interesting detail. Each sunflower has its own petal count and we are to use these petals to determine which sunflower to collect first. So, after planting a sunflower we call the measure() function and put its result into a dictionary:

heights[(q, p)] = measure()

Keys of this dictionary are tuples of coordinates and the values - the numbers of petals.

And last, but not least detail: reduce_heights function. It takes two dictionaries as parameters, updates the first with the values from the second and returns this first dictionary. Here the logic of the whole affair is a little bit complicated and I intentionally did it. In my first version the code was clearer: every time I created a fresh dictionary and filled it with the content of two parameters. But in this case drone suddenly stopped for a noticeably long time. It turned out that the price of clean code was quadratic complexity of the algorithm. Therefore I changed it and now you see messier, but faster code.

I'm not sure that one post can contain so much code, so let's use links to github. Starting from this line I convert a dictionary from format (x,y) -> h to h -> [(x1, y1), (x2, y2), ...]. For each height of sunflower now we have a list of cells with sunflowers of this height in these cells.

Finally , we use our map_reduce approach to collect all sunflowers in a correct order. "gather_all" is a factory function for this task.

Sunflowers. MapReduce.

P.S. While writing this post, I realized this algorithm can be improved. There’s some unnecessary work: first I build a (x, y) → h dictionary, and then I rebuild it into h → [(xi, yi), …]. We can generate the latter format from the start — that’s the first thing to try.

Second: we can water the tallest sunflowers first to reduce waiting time.

If this post gets 10 🔥 reactions, I’ll write one more article with these improvements. Otherwise — it’s homework 😄

Sine cosine machine

I’m a physicist, and for me sine and cosine are first and foremost laws of motion: the horizontal and vertical shadows of a pin on the edge of a rotating disc, cast on a wall.

Some time ago I decided to create a sine–cosine machine to demonstrate this idea. One evening of work in Blender, and here we are.

The problem was that the mechanism tended to stick. A piece of sandpaper and a bit of silicone oil pretty much solved it. The machine is lost now—though I can probably find the 3D files and print it again.

Word of the day: spendthrift

Spend means “to give away”, thrift — “to keep”.
If you know these words, spendthrift may sound like “keep your money while you can”.

And that would be totally wrong.

Spendthrift means to spend money carelessly.

Qbasic and polar coordinates

I think it's quite a controversial take. Progress gives us far more powerful computers, instruments nobody could imagine 5 years ago. And still qbasic feels like the best way to start writing small programs.

To make the video I used this web page .

Vibe-coding version:
* prompt
* c++ code

Algorithm Flood

In comments you can bring interesting programming tasks and discuss it

De Morgan's rule

One of the subscribers brought me a problem. Roughly, it sounds like this:
“Read standard input and count strings. Stop counting when the user enters конец or КОНЕЦ.”
The question was how to write the loop condition.

It looks trivial, but I think I can easily write a post (or two) around this question.

First, let’s try the straightforward approach with an exit condition:

n = 0
while True:
    s = input()
    if s == "конец" or s == "КОНЕЦ":
        break
    n += 1
print(n)

Here we use the break keyword, which exits the loop and skips the rest of the loop body.
So we know that we reach n += 1 only if s differs from the end-of-input marker.

Personally, I don’t like these break and continue guys — they always look like goto in disguise.

Let’s try to remove the if … break construction and move the condition into the while.

To do this, we need to invert the exit condition and write down the continuation condition instead.

Formally, the exit condition is:

s == "конец" or s == "КОНЕЦ"

So the continuation condition is:

not (s == "конец" or s == "КОНЕЦ")

And here comes De Morgan’s rule.

Let’s look at our comic strip with almost Rescue Rangers trying to find a brilliant. They know that Fat Cat hid it inside one of Nimnul’s robots — the one that is round and green. But finding such a robot in a crowded laboratory is hard.

So Gadget uses her invention and reverses the polarity. Now the diamond is inside all robots except the round and green one.

The team plays it safe and reasons like this:
if a robot is either not green or not round, we grab it.

As you can see, they find the diamond — using De Morgan’s rule.

This is important because when you write programs, you constantly switch between:

👉exit conditions
👉continuation conditions

The practical rule is simple (for basic cases):

To negate a logical expression, negate each term and swap or ↔️ and.

Let’s apply it to our example.

n = 0
s = input()
while s != "конец" and s != "КОНЕЦ":
    n += 1
    s = input()

Everything has its price.
Now we have to write s = input() twice.

But at least we got rid of break.

Walrus operator

To finalize previous post.

n = 0
while (s := input()).lower() != "конец":
    n += 1
print(n)

I think, it's the most elegant approach. But it uses "walrus operator" which appeared only in python 3.8.

Chat for discussions

Feel free to discuss things there

invitation link

Cannabis curve

There is a special page on Wolfram MathWorld dedicated to a very specific equation in polar coordinates.

r(θ) = a·[1 + 9/10·cos(8θ)]·[1 + 1/10·cos(24θ)]·[9/10 + 1/10·cos(200θ)]·(1 + sin θ)

I started wondering: is there something similar for a Christmas tree in polar coordinates?

English joke of the day

Vegetarian eats vegetables.
Guess what’s for the humanitarian.

2025 in a nutshell. Kinda...


As the owner of this channel and its promoter, I hang out in a lot of Telegram channels. Now there are many posts with promises for the next year. I definitely don’t want to make the gods laugh, so no promises. The tones vary from very proud (old school) to overly humble (an attempt to follow trends and be original). Unfortunately, all this started a process in my brain, and here we are.

Picture. Activity per week on vocabulary.com in terms of “mastered words”. It doesn’t mean I know all these words already, but at least my brain was exposed to them. It’s my longest streak on the platform, and I hope to finish the first epoch by summer 2026.

I taught a two-semester ML course at Russian-Armenian University (RAU) and expelled one student from it. Two students from my group asked me to be their thesis supervisor → +2 defended graduates under my supervision. A similar story with the School of Data Analysis: two students from MIPT → +2 graduated students with “excellent” marks. Quite rare for MIPT.
Overall: 5 graduated students → 9. +80%.

Probably because my focus drifted from my main work toward educational activities, I was thrown out of the Yandex Education department. Nevertheless, the project on metrics for educational projects was completed. In three months, I came up with quality metrics and orchestrated the work of six people.

I landed on my feet in another department after four months of an undefined state. Now I can proudly say: “I work at Yandex Delivery.”

That’s it for my solo part. My wife and I successfully found a position for her as a prompt engineer. A pinch of luck and a year of hard work.

And this channel. I started it as an exercise in English. But the more I think about it, the more it looks like an attempt to build a community. There are no random people here. Now we have 81 souls who like computers, programming, math, and education. Thank you very much for being here. Feel free to communicate — I’ve opened a chat connected to the channel.

I don’t think the coming year will be easy, but I hope it will be interesting. And I hope we can all support each other with our knowledge and total awesomeness.

Water jets

In my childhood library there were many DIY books. One of them, written for young pioneers, described a small setup that demonstrates how jet velocity depends on pressure.

At some point I managed to find three tin cans, cut off their lids, and weld them into a single tube. But for some reason the project never went any further. I can’t recall the exact cause. Most likely I failed to make the seams perfectly watertight, and the perfectionist inside me didn’t allow the experiment to be finished. Which is a pity — now I understand that the setup was literally one step away from completion, and the seams didn’t need to be completely watertight in the first place.

The column survived for decades, but after many moves — including our recent relocation to Yerevan — it was lost for good. Now, with a 3D printer at hand, I want to recreate this toy. So far, however, there are no real photos of the device.

The picture at the beginning of this article is pure neuroslop. What exactly is wrong with it? Share your thoughts in the comments.

Pouring-out velocity

When solving physics problems at school, I used a standard formula for the velocity of a jet pouring out of a hole, given the pressure inside the liquid and its density. But for a long time I couldn’t really derive this expression myself. And now I understand why.

The picture was inconsistent.

The equations themselves are trivial. On one hand, one can write energy as 𝑝𝑉. On the other hand, kinetic energy is ½ m v². So one writes pV = ½ m v². Using ρ=m/V, we immediately get a nice expression for the jet velocity (the whole thing is in the picture).

The problem is conceptual. There is no such volume whose one side is under pressure 𝑝, whose other side is under pressure 0, and which simultaneously accelerates from 𝑣=0 to v=v0. In school and even at university I felt this discrepancy intuitively, and because of that the derivation always felt like a trick rather than understanding.

Twenty-five years later, something suddenly clicked. It seems, I got it. An illusion, of course. Let me share it.

First: the streamtube.

A streamtube is an imaginary tube with an inlet, an outlet, and walls. The walls are formed by streamlines — curves tangent to the velocity of the fluid at every point. This construction is powerful because it lets us write an energy balance between inlet and outlet.

Crucially, there is no work done on the walls: pressure forces are perpendicular to the walls, motion is tangent to them, and the dot product of perpendicular vectors is zero.

So what is really going on?

Deep inside the liquid, the fluid is almost at rest and the pressure is maximal: 𝑣=0, 𝑝=𝑝0. At the center of the hole, the pressure is zero and the fluid has some non-zero velocity 𝑣, which we want to find.

One quantity smoothly transforms into the other as we move from the bulk of the liquid toward the hole. Let’s consider a streamtube that goes from the center of the liquid volume to the hole. Now everything makes sense.

The inlet of the streamtube is much wider than the outlet. That automatically gives us (almost) zero velocity at the inlet and a finite velocity at the outlet. We are no longer talking about a tiny abstract volume — we are considering the entire volume of liquid inside the streamtube.

This volume accelerates under the action of pressure gradients. It plays two roles at once:

◦it is a body that accelerates under force, and
◦it is a lever that multiplies liquid velocity by the ratio of inlet to outlet cross-section.

The resulting picture is a bit crazy: a mushroom-like shape, with many tubes narrowing from the “hat” to the “leg.” Liquid accelerates along these tubes; work done at the beginning is exactly balanced by work at the end of each tube. Complex — but internally consistent.

Basically, we have followed the university-level route that usually leads to the Bernoulli integral — but done it at a school level. And now we have a “magic-free” derivation of the pouring-out jet velocity.

And this is just moving liquid. In the simplest possible case: liquid pouring out of a hole.
But then come vortices. Plasma. Mass transfer coupled with electromagnetic fields…

Yummy craziness.

Not exponential. This time.

Guys, there’s always an exponential lurking somewhere. When the rate is proportional to the amount, the amount decays exponentially: a capacitor discharging through a resistor, detergent washing out of your sweater, foul odor leaving the room when you open a window.

But not this time.

In the previous post we derived the velocity of a jet flowing out of a hole given the pressure and the liquid density. And instead of the usual “velocity is proportional to the quantity” we get a small correction: it’s proportional to the square root of the quantity. A tiny change — and the whole solution behaves differently. Now Achilles can finally reach the tortoise in a finite time.

It always fascinated me that exponential decay is kind of contradictory. It’s blazingly fast (geometric progression!), and at the same time infinitely slow — because it never reaches exactly zero.

Here, when the outflow isn’t limited by viscosity but by inertia, the exponential law turns into a parabola — and the liquid leaves the vessel in finite time.

In the picture you can see the full derivation.

I totally forgot this funny fact from university physics. Thank you, Nikita, for bringing up this question in our conversation!

New school level physics problem

There is an old physics problem: two holes in the wall of a jar with liquid. The depth of the first hole is x, the second is y. You are to find: the horizontal distance from the jar wall to the point where the two jets intersect, and the vertical distance from the liquid surface to that intersection point.

It’s an ancient problem — you can find versions of it already in Torricelli’s works, where he derived the expression for jet velocity.

But if you slightly extend it — add one more hole at depth z, assume all holes have the same cross-section, say that the two jets merge after they meet, and then ask for the intersection point of the merged jet with the third one — hurray! You get a new physics problem, one that (as far as I know) isn’t in schoolbooks yet.

The answer to this new problem is not as simple and elegant as in the original one, but it’s still totally doable. And it’s also a nice excuse to discuss which conservation laws you can apply to the “merging” process — and which ones you can’t, and why.