mnbvmar's blog

By mnbvmar, 7 weeks ago, In English,

This is the preliminary version of editorial. Expect bugs. Some changes might happen!

1150A. Stock Arbitraging


1150B. Tiling Challenge


1150C / 1149A. Prefix Sum Primes


1150D / 1149B. Three Religions


1150E / 1149C. Tree Generator™


1149D. Abandoning Roads


1149E. Election Promises


Read more »

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

By mnbvmar, 7 weeks ago, In English,

Hi Codeforces!

I'm so happy to invite you to Codeforces Round #556 (Div. 1) and Codeforces Round #556 (Div. 2)! The rounds will be held on Apr/29/2019 17:35 (Moscow time). The round will be rated for both divisions. (At least that's what I've been told!)

The problems were written and prepared by me. Thanks to 300iq for the round coordination, and to Radewoosh for his invaluable help with choosing the problemset and testing the problems! Also, I want to give a shout-out to MikeMirzayanov for his amazing Codeforces and Polygon platforms!

My browser's tab bar, right now.

You'll work on 5 problems, and you will have 2 hours to solve them. The scoring distribution will be revealed closer to the round.

def get_end_remark():
    return random.choice([
        "Wish everyone high ratings!",
        "Good luck!",
        "Have fun!",
        "Please, read all the problems!"])

UPD 1: The scoring distribution time!

Div 2: 500 — 1000 — 1500 — 2250 — 2750

Div 1: 500 — 1250 — 1750 — 2500 — 2750

Also, thanks to _kun_, V--gLaSsH0ldEr593--V and qwertyland who contributed to the round testing!

UPD 2: The round is over! Sorry for misbalancing the difficulties in Div2, it was totally unexpected for us. Meanwhile, you can have a look at the editorial!

UPD 3: We finished the system tests. Congratulations to the winners!

Div 1:

  1. Um_nik
  2. Vn_nV
  3. maroonrk
  4. Reyna
  5. LHiC

Div 2:

  1. jiangly
  2. Simplicity
  3. Netherdrake
  4. C137
  5. kobor

Also, a shout-out to the first solvers of each task!

Div 1 Div 1 Task Div 2 Div 2
Stock Arbitraging 1:57 Ahmad
Tiling Challenge 3:43 Nazarbek_Baltabaev
Petr 2:06 Prefix Sum Primes 4:20 JamesWilson
ko_osaga 16:27 Three Religions 48:20 jiangly
ainta 28:45 Tree Generator™ 109:53 lzoilxy
Petr 53:52 Abandoning Roads
Vn_nV 83:10 Election Promises

Read more »

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

By mnbvmar, 6 months ago, In English,

Hi folks,

I was just trying to change my handle to a handle of another user. I believe that the user is inactive: they registered back in 2015 and were active for a couple of hours only (as confirmed by Codeforces API). The user didn't submit anything to the judge and didn't write any blog/comment/contest/etc. However, I'm still unable to change the nickname as the server states that the handle is currently in use.

So here comes my question: did anyone successfully change their handle to an already used one? Also, if you managed to do it, did the previous handle owner register in 2015 or was it earlier than 2015?


Read more »

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

By mnbvmar, 4 years ago, In English,

Hey, CF community!

I have a newbie question about the square-root decomposition method on arrays. You probably know the trick — assume we have to do a sequence of queries on the array of size n. We divide it into pieces of size . Then when any query (do something on interval) comes up, there are pieces covered by the interval (which we can somehow process quickly) and elements outside these pieces (which we can brute-force). Thus we arrive into something like or per query.

Now my question comes — many people here name such a technique; its name is Mo's algorithm. However, my searches in Google and arXiv gave no information on the origins of the name. However, it seems to be widely used on Codeforces and we-love-algorithms-blogs. I'm quite interested in:

  1. Who was the first to use this name for the technique? When was it?
  2. Which Mo (I guess many of them contribute to computer science, at least arXiv says so) does the name refer to?

Thanks in advance for your answers.

A funny sidenote: I had also another question in my mind before — it was about BITs (binary indexed trees). I thought that it must be connected with bit manipulations. It got really weird when people kept discussing about Fenwick trees there. I was explaining to myself that we use bit operations to move in the tree more efficiently. It took me like a year to realize how stupid I had been... :D

Read more »

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