mnbvmar's blog

By mnbvmar, history, 5 years ago, In English

Hi everyone!

XX Open Cup Grand Prix of Warsaw will take place this Sunday, on September 15th 2019, at 11am Moscow time.

To enter the contest, click here (Open Cup login necessary).

The problems were created and set by Radewoosh and me. Also, thanks to the testers: Swistakk, Marcin_smu and Errichto!

The problemset was presented at this summer's Petrozavodsk camp. Thanks to everyone at AIM Tech for supporting the contest, including the tasks selection! If you want to know how to hold your own contest on Moscow Workshops in November and participate in the camp for free, look here.

If you're still unsure whether to participate and you like Pokémon, this is your lucky day! You'll be able to help quite a few of them on Sunday. Don't worry, you don't have to finish all the games and watch all the anime in order to solve the tasks! *but it's a good idea in general

Good luck!

Edit: Thanks for the participation! The editorial can be found here.

Edit 2: The contest is available at Gym. Thanks to MikeMirzayanov for helping us with uploading it!

Full text and comments »

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

By mnbvmar, 5 years 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


Full text and comments »

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

By mnbvmar, 5 years 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 cdkrot, vintage_Vlad_Makeev 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. DearMargaret
  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 praeda_est_supra
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
DearMargaret 83:10 Election Promises

Full text and comments »

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

By mnbvmar, 6 years 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?


Full text and comments »

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

By mnbvmar, 9 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

Full text and comments »

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