qwerty787788's blog

By qwerty787788, history, 11 months ago, In English

A long time ago there was a competition called Deadline24, which I really enjoyed! Unfortunately, the last edition of it was in 2018. In that competition, you need to write a program, which connects to the server via TCP and plays some game. Usually, the game is turn-based, so you need to read the current state, make a move, wait for the next turn, and so on.

I like this format, so as a hobby project, I decided to write a server for a game in the same format. The game itself is very simple. You are playing as a circle, which flies around the field, and need to collect as many other circles as possible. The only hard part is that you can't change your speed instantly, you can only change acceleration.

The contest is already live! You can watch the current game in real-time: https://aicontest.dev/ and read more detailed rules of the game: https://github.com/bminaiev/aicontest.dev/blob/master/README.md

Consider writing a bot for it! In two weeks top-3 players from the "Highest Scores" (the biggest score achieved in any game) tab will get 100, 50 and 25 TON from me.

Also, I am very interested in the feedback about this game:

  • Do you like the format in general?
  • Do you like a specific game?
  • What could be improved?

UPD. The contest has finished. Congratulations to the winners:

  1. al13n — 175 points
  2. progiv-rust-main — 160 points
  3. eulersche_Zahl — 150 points

Please send me your details in DM.

Also, the server will continue working, so if you want to participate, you still can do it.

Full text and comments »

Tags bot, ai
  • Vote: I like it
  • +132
  • Vote: I do not like it

By qwerty787788, 14 months ago, In English

I really like peltorator's idea to encourage people to write blog posts about interesting ideas. I don't have new and rare stuff to share, instead, I just want to share some insights about how Simulated Annealing works.

Sorry for cross-posting, but the actual blog could be found here: https://bminaiev.github.io/simulated-annealing. It contains a lot of dynamic plots, which are hard to embed inside the CodeForces blog (and I really suggest checking the blog on the desktop, not the phone).

The blog was inspired by Psyho's Twitter thread. If you haven't seen it — check it out!

Also, I don't really have a lot of real experience with SA, so some facts or ideas in the blog could be wrong. Would be really interested to hear feedback from more experienced SA users :)

Full text and comments »

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

By qwerty787788, 18 months ago, In English

In the hardest problem of Meta HackerCup 2022 Round 3 it was needed to write an algorithm for fast points locations. Basically, you were given a lot of polygons and a lot of points. For each point, you need to find the smallest polygon, which contains it. In the hardest version of the task, points are created based on previous answers, so you can't solve it offline.

I believe everybody who solved this problem during the contest used the same algorithm with sweep-line and persistent treap (or just std::set, but it doesn't work for online version of the task).

After the contest PavelKunyavskiy told me that it is possible to solve this task with just a segment tree (but the complexity is $$$O(\log^2 n)$$$ per query). I haven't seen this algorithm before, so I wrote an explanation of it here: https://teletype.in/@bminaiev/online-point-location.

Also after a discussion with izban I think it is possible to improve the complexity of the algorithm with fractional cascading, but it is not very straightforward (and will work slower in practice).

Full text and comments »

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

By qwerty787788, 10 years ago, translation, In English
  • Vote: I like it
  • +119
  • Vote: I do not like it

By qwerty787788, 10 years ago, translation, In English

Hello!

We invite you to participate in Codeforces Round #253, which will take place on Thursday, June 19th at 19:30 MSK. The round will be held in both divisions.

It's my first Codeforces Round and I hope you will enjoy it!

Many thanks to Gerald for helping to prepare the round. Also I'd like to thank MikeMirzayanov for creating such a good platform. Also thanks to testers of this round: antonkov, Aksenov239, VArtem, subscriber, niyaznigmatul and to Delinur for translating statements.

Don't miss a chance to have fun of solving interesting problems!

UPD. Score distribution:

Div1: 500-1500-1500-2000-2500

Div2: 500-1000-1500-2500-2500

UPD2. The contest is over, thanks for participating!

Congtatulations to Div1 winners:

1) tourist

2) scott_wu

3) stevenkplus

3) gs12117

5) GlebsHP

And congratulations to Div2 winners:

1) tafit3

2) thnkndblv

3) MIT3

4) lucaslima

5) liuzhijian

My congratulations to tourist, only person who managed to solve all five problems, and only one who solved problem 442E - Gena and Second Distance!

You can find editorial here.

Full text and comments »

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