Things I don't know I'm just in a mood to shitpost. Don't take it too seriously. Things that I have heard of, but don't know (imagine how many things I haven't even heard of): - Li-Chao Segment Tree - Segment Tree Beats - RMQ in $O(n)$/$O(1)$ - Any self-balancing tree except treap - Link-cut tree - Wavelet tree - Mergesort tree - Binomial heap - Fibonacci heap - Leftist heap - Dominator tree - 3-connected components in $O(n)$ - $k$-th shortest path - Matching in general graph - Weighted matching in general graph - Preflow-push - MCMF in $O(poly(V, E))$ - Minimum arborescence (directed MST) in $O(E \log V)$ - Suffix tree - Online convex hull in 2D - Convex hull in 3D - Halfplane intersection - Voronoi diagram / Delaunay triangulation - Operation on formal power series (exp, log, sqrt, ...) (I know the general idea of Newton method) - How to actually use generating functions to solve problems - Lagrange Inversion formula - [...

Полный текст и комментарии »

Unimportant Um_nik Update Hello Codeforces! I have some big news. I am trying to fight depression and live a fuller life. That includes some self-realization, maybe even (I don't even want to think about it) a job. I love cp, and I love teaching, and I know I already tried that, but I believe that this is the way. With the help of my wife, I started to work on some related projects, and today we want to share them with the world. All of them are in the early stages, but we set a hard deadline for March 1, so... Um ================== Um... I am starting a series of educational YouTube videos / selected problems. Every episode of Um is focused on one problem. I will explain how to solve this problem and talk about some related concepts. The idea is to show off some cool concepts using real problems. The kicker: the problem is made public at least a week before the episode airs. So you can use Um as a source of problems. I will try to choose nice problems that highlight some ideas, and problems ...

Полный текст и комментарии »

Pro Tips - get them while they are free More tips to use while studying under my tutoring [here](https://um-nik.notion.site/Pro-Tips-8b923b0dc7c94770824bdf4184afc43c). ## Stop caring about the rating Unless there are prizes involved, your position in the standings makes no difference. I can feel awful after winning a contest if I know that I could solve one more problem. Or I can feel OK losing a bunch of rating points knowing that I solved everything I could.  Because rating is just a number. It is highly volatile and it depends on other people, not only on your skill. But solving problems is totally up to you. And you should evaluate yourself not based on some random metric, but on your honest feeling whether you performed up to your expectations. Your sense of self should be under your control, don't get hung up on some imaginary value, you cannot reduce your progress to a single number. ## Don't use more than one account Rating is just a number. Do not be afraid to lose your colour. You’ll get it back in no t...

Полный текст и комментарии »

How to practice Competitive Programming [Um_nik version] CP is about solving problems fast. And as absurd as it may sound, I believe that <span style="color:blue">SOLVE</span> and <span style="color:red">FAST</span> are very different and almost independent parts, and you need to practice them separately. Let’s look at some <span style="color:red">contest</span>, like a CodeForces round. For the sake of simplicity let’s assume that every problem has some *difficulty*, which is a numerical value denoting how hard it is, bigger values correspond to harder problems (it is not true, but it is an ok-ish approximation, at least if we consider subjective difficulty for a fixed person). Contests are made for a wide range of participants, and problemsetters strive to make contests interesting for a wide range of participants, which means having a *smooth difficulty gradient*. Well... as smooth as it is possible with 5-6 problems. <spoiler summary="Graph 1"> ![ ](https://s3.us-west-2.amazonaws.com/secure.notion-static.com/677e0ae2-a8df-4874-aff...

Полный текст и комментарии »

On AI ruining "solving math problems with computer" You all went crazy. Instead of arguing with every opinion separately, I just want to ask one question: Why are you doing competitive programming? Is it to get to 1600 rating and put it on the resume? If so, please use AI, cheat, and do everything possible to get to 1600 as soon as possible and get the f**k out of this platform. And if you are (not) a normal person and do competitive programming because it is fun to solve problems, do you think it is fun to copy the problem statement into an AI model prompt and then copy the code it spews to submit? And why do you assume that everyone else will do that if there will be such an opportunity? The same goes for cheaters. Yes, some people do not do this as a sport, for fun. Why do you care? I do think that AI is ruining competitive programming. By proxy. And that proxy is all of you who are running around yelling "We will all die, somebody do something about AI". I have seen a couple of comments saying "authors/coordinators must make s...

Полный текст и комментарии »

Support Anton Trygub Since [user:antontrygubO_o,2020-07-12] has became CF coordinator he is trying hard to make rounds which meet his standards for quality and (more importantly) beauty. I think he is doing a great job. For some time there is a very vocal group of people who dislike his view on things. I feel like it will be hard for Anton to maintain his work if he would think that majority of people doesn't approve. But I don't really think that this is a majority. If you enjoy rounds prepared or coordinated by Anton, please comment here with some positive feedback. `#AdHocProblemsMatter`

Полный текст и комментарии »

New contest format?! Stream feat. tourist, Um_nik Hey all! We've created a new 1v1 programming contest format: **Lockout**. Like in most contests, each round has a set of problems and contestants work to solve them as quickly as they can. In Lockout, however, contestants compete head-to-head and only the first contestant to solve each problem gets the points. Contestants can work on problems in any order, so speed and strategy are crucial to avoid getting sniped! The head-to-head action also makes the contest much more exciting for viewers. We ran the first edition of Lockout at TCO Finals last month as a double-elimination bracket [tournament](https://challonge.com/lockout0). All of the finalists who were available competed (and even some of the problem writers) and we got to see a lot of exciting back-and-forth matches! As you can see though, there's still one set left to play. So we'll be streaming **Grand Finals of Lockout 0 featuring [user:tourist,2019-12-28] vs. [user:Um_nik,2019-12-28]** at [9:30 AM PST](https://www.timea...

Полный текст и комментарии »

Hacking (as a CF feature) does not fit modern competitive programming 1. How does hacking work with the new feature of unrated registration? I have seen this question raised in the comments to the announcement several times, but there is no answer still and I think it's weird that Mike hasn't thought about it before announcing. 2. I was working recently on a div.2 Codeforces round (still might happen in the future) and I was told by my coordinator that pretests should be equal to systests in all the problems. From this I can conclude that it is a Codeforces policy and intentionally weak pretests do not happen. It doesn't mean that it is impossible to hack anybody, but it doesn't sound like a viable strategy. I find it weird that this information is not public, it's like I'm getting bonus information about all other Codeforces rounds by setting a round myself. I have done exactly zero research on the matter, but my feeling is that 99% of hacks (I'm talking about during-the-round-hacking here, not open hacking of education rounds and such) happen in ...

Полный текст и комментарии »

On AI ruining "solving math problems with computer" [a year later] I guess you were right in the part "a year from now LLMs will solve problems on your level". You were also saying something along the lines of "you'll change your mind when it starts affecting you". In this part, you were wrong. Cheaters always existed, and they always will. LLMs make it easier to cheat, true. There is no way of completely preventing LLM cheating (or any other kind of cheating) in online competitions. I just coordinated the round everyone is buzzing about, so I can with confidence say that in the CF rules for coordinators and authors, there isn't anything about making problems LLM-proof. Not for easy problems, not for hard problems, nothing. And I doubt any such rules will appear. LLMs are forbidden by the rules, that's that. So we, as honest participants (yes, I will assume that you are an honest participant, otherwise this blog is not applicable to you and I don't care about you), will have to accept that some problems in the future rounds will be LLM-able, ...

Полный текст и комментарии »

Changes in CodeChef Problemsetting Hello Codeforces! For the last half a year I have been working on CodeChef and was proposing ideas on how to change the problemsetting practices (hopefully, for the best). For some time the changes were in brainstorming phase, but as of now many of them are implemented. Today we are ready to share the information with you. But first I would like to approach people who are going to close this blog without reading: If you are not interested in CodeChef contests at all, I think you should change your mind. Monthly short contests (Cook-Off and Lunchtime) have interesting quality problems, on par with Codeforces in my opinion (not AtCoder level yet, but who are?). Long and Starters are more targeted to newbie participants, with more classical educational problems. If you are interested in setting problems for regular contests, you might want to do it on CodeChef. Some reasons: - You don't have to set the whole round, as we work on per problem basis. - This may be especially...

Полный текст и комментарии »

Codeforces Round #485 (div.1+div.2) Hello! I'm glad to invite you all to Round 485 which will take place on [Tuesday, May 29 at 18:35 UTC+3](https://www.timeanddate.com/worldclock/fixedtime.html?msg=Codeforces+Round+%23485&iso=20180529T1835&p1=166&ah=2). There will be 6 problems in each division, 3 of them are shared between divisions. 2 of div.2 problems created by [user:KAN,2018-05-28], 7 others created by me. The contest duration is 2 hours. My problems were originally used in HSE Championship. I would like to thank [user:Merkurev,2018-05-28] and [user:GlebsHP,2018-05-28] with whom I discussed the problems, [user:I_love_Tanya_Romanova,2018-05-28] for testing, [user:KAN,2018-05-28] for round coordination and Codeforces and Polygon team for these beautiful platforms. I would also like to thank HSE for organizing the event. Oh, and [user:kb.,2018-05-28] for writing great legend for one of the problems (he will be surprised). For those who for some reason like to know score distribution in advance: div.2: 5...

Полный текст и комментарии »

One-letter variables Complete shitpost, don't take it seriously. We were discussing `#define int long long` and I suggested defining it to one letter if you want to save on typing so desperately. [user:jeroenodb,2025-10-11] said that those are reserved for variables, which prompted me to think, "Is there a letter I don't standardly use for some particular purpose?" Then I compiled the following list, and then I thought, "Well, I already wrote it, let's put it on cf", so here we are. ~~~~~ a - array, but also all sorts of stuff b - second array c - third array / count d - delta / divisor e - event / edge f - flag g - graph / second flag h - third iterator / third flag / height i - iterator j - second iterator k - third input size / some parameter (i know, those are all parameters, but for some reason k is parameter) l - left m - number of edges / second input size n - input size o - ??? p - permutation / position q - number of queries / query / second permutation / second position r - r...

Полный текст и комментарии »

Hooray! Binary Search Episode! Just a reminder that [Um](https://mirror.codeforces.com/blog/entry/113418) still exists and I just posted [Episode 9](https://youtu.be/kHxaTXQfu9E). And it is just 0:54 long, no reason not to watch. Magic words to attract attention: Um_nik does binary search, $O(\log N)$ per query online solution to [Stamp Rally](https://atcoder.jp/contests/agc002/tasks/agc002_d). I switched to the "1 video every 2 days" schedule, it seems manageable. The [list](https://um-nik.notion.site/cff90514c6174afcb4ab8ff5dbb5b9a3?v=88948840b1494f18aea5535a6329a914) now contains 15 problems. Also, there are slides for the problems for which videos are already posted. [Checklist](https://um-checklist.aryanc403.com/) by aryanc403 for tracking your progress on Um problems, [Playlist](https://www.youtube.com/watch?v=oZfoiVr0OWs&list=PL_2SIhFoM1-sAlY5JENWxFi3IiXD8WB-M) with all Um episodes, [My YouTube channel](https://www.youtube.com/@umnik_team), [Discord](https://discord.gg/HPjyarXvsN), [Um_nik World](https://bi...

Полный текст и комментарии »

Эксклюзивный клуб по интересам от Умника В начале июля я провёл [онлайн школу](https://mirror.codeforces.com/blog/entry/78785), и судя по отзывам всё прошло хорошо. Было много пожеланий продолжить занятия, поэтому сейчас я предлагаю более долгосрочный формат обучения под моим руководством. Я верю, что чтобы качаться, нужно решать много задач. Причём нужно действительно долго работать над сложными задачами, пытаться придумать решения самому, не подглядывая в разбор. С другой стороны, есть много разных идей, наблюдений и приёмов, которыми нужно делиться и которым стоит учить. Поэтому я предлагаю следующий формат: Раз в неделю я выдаю список задач, которые я считаю полезными. В конце недели я разбираю часть этих задач, другие задачи остаются на более длительное обдумывание. По каким-то из этих задач я буду добавлять подсказки. Раз в месяц я буду доразбирать большую часть оставшихся задач. Иногда я буду проводить лекции и немного смещать выборку задач в сторону лекции, но не стоит ожидать традиционных тематических контестов. ...

Полный текст и комментарии »

Codeforces Round #614 *"Can you hear me?"* *"Vanessa...?"*  Hello Codeforces! We are here to invite you to Codeforces Round #614 (Div. 1) and Codeforces Round #614 (Div. 2), which will take place at [contest_time:1292]. The round is rated for both divisions. This is our first round including Div.1 parts, hopefully you'll find the problems interesting. ;) This round is themed based on the Rayark Inc.'s rhythm game, [_"Cytus II"_](https://www.rayark.com/g/cytus2/). You are about to help our characters in various problems, whether inside or outside of the virtual Internet! Also, feel free to listen to the music tracks I've chosen from the game for each problem (and later, editorial!). ;) Each division will be given **6** problems to solve in **2 hours.** The round's problems were prepared by Xuan-Quang ~xuanquang1999,2020-01-12 D. Nguyen, Duy-Bach ~Akikaze,2020-01-12 Le and Tuan-Dung ~low_,2020-01-12 To. Interactive problem(s) might be found in this ...

Полный текст и комментарии »

How to read problem statements But [user:Um_nik,2018-10-26], we all know how to read, we have our whooping 2 month of experience! Oh, my sweet summer child, my experiments show that many people with kinda cool achievements like medals on ROI don't know how to read statements. But don't worry, I'll teach you. Well, probably you won't understand anything, because you didn't try to understand anything in your life, you expect all hard work to be done for you by someone else. Let's start! Basic rules ================== - The result of reading the statement is usually pure math model. If story helps to build correct understanding, you can keep it, but still try to discard as many unnecessary details as possible. - Imagine you want to tell the problem to someone else. What parts you want to tell? (According to my PM, this rule won't help you). - Shorter = better. - Simpler = better. - Limitations are part of problem statement. Especially small limitations, because for small data you can try all the possib...

Полный текст и комментарии »

F.A.Q. (in PM) Q1: I'm a newbie. What should I do to become great coder? A1: <s>Stop doing competetive programming</s> Solve problems. Q2: I'm doing CP for two months and I'm still <s>not red</s> green. What should I do? A2: <s>You are lazy and impatient</s> Solve more problems. Q3: You became a red in less than two years, it is unbelievable! A3: No, it isn't. <s>You can do it too if you will solve fucking problems.</s> Q4: You became a red blah-blah-blah such a huge fan blah-blah. Oh, and what should I do to become as great as you? A4: ... right. You already know the answer. Solve problems. <s>I hate you.</s> Q5: I'm not good at DP [or something]. What can you suggest? A5. Maybe you should try to <s>stop asking stupid questions and</s> solve some problems on DP? Or read some blogs and editorials. Q6: I can't solve a problem / understand your code. Can you help me? (Well, it is not a bad question in general. It is a good (if you really want me to explain something not...

Полный текст и комментарии »

Bin search and relative error Suppose we want to solve a problem by doing binary search on answer. Then the answer will be checked against jury's answer by absolute or relative error (one of them should be smaller then $\epsilon$). For simplicity we will assume that our answer is always greater than $1$ and smaller than $B$. Because of that, we will always use relative error rather than absolute. Suppose we have made $n$ iterations of our binary search &mdash; what information do we have now? I state that we know that real answer is lying in some segment $[x_{i}, x_{i+1}]$, where $1 = x_{0} < x_{1} < \ldots < x_{i} < \ldots < x_{2^{n}} = B$. And what is great &mdash; we can choose all $x_{i}$ except for $x_{0}$ and $x_{2^{n}}$. Now, for simplicity, we will also assume that we will answer $x_{i+1}$ for segment $[x_{i}, x_{i+1}]$ and the real answer was $x_{i}$ &mdash; it is the worst case for us. It is obvious that we will not do that in real life, any other answer would be better, but you will get the idea. ...

Полный текст и комментарии »

MIT Mystery Hunt Disclaimer: This blog is not about competitive programming; you probably will not learn anything about algorithms and data structures. In other words, it doesn't qualify for [this initiative](https://mirror.codeforces.com/blog/entry/110840), but I want to give a link to it anyways because I think it's cool. I love solving problems. No, seriously. I LOVE it. The mindset described in [this blog](https://mirror.codeforces.com/blog/entry/91114) is 100% how I feel. But it is not constrained to competitive programming problems. I loved math problems for a much longer time, and physics was somewhere there. But I also love solving puzzles. And playing puzzle games on the computer (well, on consoles). And participating in intellectual games. I am not as good in them as in cp, but it was never about being good for me, I just love the process. And I think that there might be some people with a similar love for puzzles among competitive programmers, this is why I decided to write this blog on CF <s>and no...

Полный текст и комментарии »

Osijek Competitive Programming Camp, Fall 2023 Hi everyone! <center><a href="https://ocpc.mathos.unios.hr"><img src="https://ocpc.mathos.unios.hr/images/ocpc.svg" height="100px"></a> <a href="https://icpc.foundation/"><img src="https://ocpc.mathos.unios.hr/images/ICPC.svg" height="100px"></a></center> <center> <b>Sponsored by</b><br> <a href="https://www.janestreet.com/join-jane-street/open-roles/?type=students-and-new-grads&location=london"> <img src="/predownloaded/ee/f2/eef26616a3661c658d1545f18ed21fabb14d5871.svg" height="50px" style="margin: 5px 5px 5px 5px;"> </a> <a href="https://pinely.com/"> <img src="/predownloaded/0a/0f/0a0f3f67435d1f6e467bc7203d4a2090ba8f92cc.svg" height="50px" style="margin: 5px 5px 5px 5px;"> </a> </center> After a successful camp last February ([announcement](https://mirror.codeforces.com/blog/entry/110945), [wrap-up](https://mirror.codeforces.com/blog/entry/113438)), we are happy to announce that Osijek camp will be returning on **16.-24. September 2023** &mdash; just in time to prepare for th...

Полный текст и комментарии »

Codeforces Round #800 Editorial ###[problem:1694A] Idea: [user:AmShZ,2022-06-16] <spoiler summary="Solution"> [tutorial:1694A] </spoiler> <spoiler summary="Implementation"> ~~~~~ # include <bits/stdc++.h> using namespace std; int t, A, B; int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> t; while (t --){ cin >> A >> B; for (int i = 0; i < min(A, B); ++ i) cout << "01"; for (int i = 0; i < abs(A - B); ++ i) cout << (A < B ? 1 : 0); cout << '\n'; } return 0; } ~~~~~ </spoiler> ###[problem:1694B] Idea: [user:AmShZ,2022-06-16] <spoiler summary="Solution"> [tutorial:1694B] </spoiler> <spoiler summary="Implementation"> ~~~~~ # include <bits/stdc++.h> using namespace std; int t, n; string S; long long ans; int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> t; while (t --){ cin >> n >> S, ans = n; for (int i = 1; i < n; ++ i) if (S[i] != S[i - 1]) ans += i; cout << ans << '\n'; ...

Полный текст и комментарии »

Petition to make (onsite part of) ICPC WF 2020 1-computer In case you haven't heard: ICPC announced that in the Championship (onsite in Moscow) Division of ICPC World Finals 2020 teams will use 3 computers (one per participant). And they did that less than 40 days before the contest itself. I think this is ridiculous and this is not the competition we have been preparing for all these years. If you think the same, please comment under this blog in a format you deem reasonable (you can follow my format or not). Moreover, there was a suggestion from [user:Alex_2oo8,2021-09-09] to ignore ICPC and self-impose the rule to use one computer at a time. If you want to do that (in case ICPC will go with 3 computers per team), you can add such a statement to your comment too.

Полный текст и комментарии »

Invitation to CodeChef December Lunchtime 2020 We invite you to participate in CodeChef’s [December Lunchtime](http://bit.ly/LTIME91-Codeforces), this **Saturday, 26th December**, from [9:30 pm to 12:30 am IST](https://www.timeanddate.com/worldclock/fixedtime.html?msg=December+2020+Lunchtime&iso=20201226T2130&p1=44&ah=3). **Note the unusual time.** It starts at 9:30pm instead of the usual 7:30pm You will be given a total of **8 problems** (6 in Div2, 6 in Div1) to solve in a duration of **3 hours**. Joining us on the problem setting panel are: - Setters: Sahil [user:sahi1422,2020-12-25] Chimnani, Venkata [user:Nikhil_Medam,2020-12-25] Nikhil Medam, Áron [user:mraron,2020-12-25] Noszály, Nishant [user:nishant403,2020-12-25] Shah, Yogesh [user:SeismicToss,2020-12-25] Sharma, Hriday [user:the_hyp0cr1t3,2020-12-25], Divyam [user:divyamsingal01,2020-12-25] Singal, Bhavyesh [user:bhvdsi,2020-12-25] Desai - Tester: Rahul [user:amnesiac_dusk,2020-12-25] Dugar - Editorialist: Taranpreet [user:taran_1407,2020-12-25] Singh ...

Полный текст и комментарии »

Зимний интенсив от Умника Всем привет. Я продолжаю свои попытки в онлайн обучение спортивному программированию (предыдущие итерации: [раз](https://mirror.codeforces.com/blog/entry/78785) [два](https://mirror.codeforces.com/blog/entry/81129)). Ученики говорят, что им очень нравится, почему бы и вам не приобщиться к прекрасному? ## Что я предлагаю - 5 личных контестов на 4-5 часов, в каждом контесте около 16 задач. - Все задачи со старых раундов Codeforces, но подбираю я их с любовью и прицелом на то, что я смогу интересного сказать на разборе по этому поводу. Задачи сложные. - Соответственно, платформа для проведения (с задачной точки зрения) — закрытая группа на Codeforces. Thanks to MikeMirzayanov после прошлого моего интенсива там прокачали монитор дорешки, теперь все еще более красиво. - <font style="color:red">[New]</font> Рабочий процесс по одному контесту выглядит так: в один день вы пишите виртуалку, на следующий день я провожу разбор. Разборы у меня очень длинные, подробные, с частыми лирическими от...

Полный текст и комментарии »

More videos? I'm thinking about doing more videos, not only screencasts of rounds. For some time now I'm using [OI Checklist](https://oichecklist.pythonanywhere.com/) by [user:Rezwan.Arefin01,2019-12-15] (cannot recommend enough, especially if you are preparing for hard IOI-style contests) as an archive, so I'm thinking about doing videos with editorials (more like my thinking process) for some old POI problems. So, here are some questions for you: 1. Is this interesting? 2. Should I read (and think about) problems beforehand? Pros: I will have more structured thoughts about problem, I will know for sure if I will be able to solve this problem in a short time, ??? Cons: It is kinda unfair, it may look like I'm crushing it when in reality it could take hours for me to solve, ??? 3. Should I do one-problem length videos? The problem is that I prefer to open some (3-6) problems, read all of them, and then think about each problem for some time, probably starting with the one I liked more. ...

Полный текст и комментарии »

AtCoder World Tour Finals 2024 Announcement (with Unrated Mirror) We will hold AtCoder World Tour Finals 2024. List of Finalists: <table border="1"> <tr align="center"><td>AtCoder ID</td><td>Codeforces ID</td></tr> <tr align="center"><td>[zhoukangyang](https://atcoder.jp/users/zhoukangyang)</td><td>[user:zhoukangyang,2024-07-11]</td></tr> <tr align="center"><td>[Stonefeang](https://atcoder.jp/users/Stonefeang)</td><td>[user:Radewoosh,2024-07-11]</td></tr> <tr align="center"><td>[ecnerwala](https://atcoder.jp/users/ecnerwala)</td><td>[user:ecnerwala,2024-07-11]</td></tr> <tr align="center"><td>[tourist](https://atcoder.jp/users/tourist)</td><td>[user:tourist,2024-07-11]</td></tr> <tr align="center"><td>[heno239](https://atcoder.jp/users/heno239)</td><td>[user:heno239,2024-07-11]</td></tr> <tr align="center"><td>[ksun48](https://atcoder.jp/users/ksun48)</td><td>[user:ksun48,2024-07-11]</td></tr> <tr align="center"><td>[jiangly](https://atcoder.jp/users/jiangly)</td><td>[user:jiangly,2024-07-11]</td></tr> <tr align="center"><td>[apiad](http...

Полный текст и комментарии »

An unexpected D&C with FFT I came up with this idea when solving [an AtCoder problem](https://atcoder.jp/contests/arc140/tasks/arc140_f), but the editorial had a simpler solution. I liked the idea, so I decided to set [a CodeChef problem](https://www.codechef.com/COOK142A/problems/BOXES) using this idea. Since most of you guys don't participate in CodeChef contests, which is a big mistake, I'll write a short blog explaining the idea. Consider this a spoiler warning for these two problems and a CodeChef promotion. ### Combinatorial problem For given $a$ and $n \le 10^5$ calculate $A_k = \sum_{i=0}^{k} \binom{k}{i} \binom{n-k}{k-i} a^{i}$ for each $k$ from $0$ to $n$. (Use the two links above to see why anybody would like to do that) ### Reformulation with polynomials It is easy to see that $A_k$ is $((1+ax)^{k}(1+x)^{n-k})[x^k]$ (coefficient of $x^k$ in polynomial $(1+ax)^{k}(1+x)^{n-k}$). But since the polynomials are different for different $k$ this doesn't seem very helpful... ### Solution ...

Полный текст и комментарии »

Most annoying person on CF It is this time of year! Many people trying to summarize all the things happened during the year. And since I love to hate people, I want to make a vote for most annoying person on CF in 2018. I know that I'm in top contributors list for too long, so to vote for given person you should **downvote** the comment with this person's handle(s). Due to the nature of voting through comments on CF, you can vote for many people, and you can also upvote comments if you find given person's comments helpful/funny/positive. If you care for your contribution but want to nominate a candidate, you can PM me their handle(s), then I will write a comment to vote. Note that I **will** write that it was you who nominated this person, so it saves your contribution but not relationships with the nominee. I will ignore messages from people without rating. If you hate someone already nominated so much that you want them to know, you can also PM me so I'll add you to list of people who nominated given ...

Полный текст и комментарии »

Q&A/AMA stream on Tuesday Hello Codeforces! I will hold a Q&A/AMA stream on [Twitch](https://www.twitch.tv/um_nik22) on [Tuesday, 21 MSK (UTC+3)](https://www.timeanddate.com/worldclock/fixedtime.html?msg=Um_nik+Q%26A%2FAMA+session&iso=20211012T21&p1=2008). You can write your questions in chat during the stream, or send them in this [form](https://forms.gle/UyfLdfcMHHHtu5rj6) beforehand (for example, if you can't attend the stream in person). Recording will be uploaded on [YouTube](https://www.youtube.com/channel/UC3-pkjZ8-D4aW8QfaExuMjw) afterwards. Questions written in Russian will be answered in Russian, questions written in English &mdash; in English, questions written in other languages won't be answered because I can't understand them. I won't answer a question if I don't want to. Hopefully, the multilingual nature of the stream will be resolved afterwards by interested people who will add subtitles. Questions can be about anything, but once again, I won't answer a question if I don't want to. ...

Полный текст и комментарии »

How not to read problem statements I wanted to write super-harsh blog but then I decided to split it into educational part and whining part. This is whining part. To read some cool stuff go [here](https://mirror.codeforces.com/blog/entry/62730). This one will also be educational on a slightly different topic. And there will be A LOT of harsh stuff. I'm not saying that I'm perfect. That round had some really bad problemsetting issues. Problem E was googleable, problem D had very weak tests against very stupid solution (so stupid that none of the authors and testers come up with it, moreover, it is so counter-intuitive that I don't know how so many people independently did it). In two constructive problems participants could look at jury's output, the feature of which I didn't know. And I'm sorry for these issues. BUT. [This comment](https://mirror.codeforces.com/blog/entry/62614#comment-466588) has very negative rating despite being so true. And no one are here to back me up. So I want to speak my truth as I always do. Let me ac...

Полный текст и комментарии »

Я написал квалификацию Yandex.Cup... Она все еще идет, но я буду постить непубличную информацию, потому что мне плевать. Если [user:Yandex,2020-10-19] захотят запретить мне участвовать в этом замечательном соревновании &mdash; да будет так. 1 Монитор выглядит так: <spoiler summary="Spoiler">  </spoiler> Notable problems: - Для меня от начала соревнования прошло 50 минут, но мне почему-то видны попытки других участников, которые совершены после этого времени. Интересно, что этой проблемы не было на пробном туре. - Получается, скриншотом этого монитора я даже не спойлерю вам ничего, ведь вы увидите такой монитор как только запустите виртуальное участие. - В мониторе написано, что задачу E сдали 27 человек из 31 попытавшегося. Вот только на этом же мониторе видно, что её сдали 3 человека, у всех кто ниже должно быть не больше 2 баллов в сумме, в то время как сдача задачи E приносит 4 балла. Вам придется поверить мне на слово, что в этой задаче не предусмотрено частичных...

Полный текст и комментарии »

Codeforces Round #612 Всем привет! Сейчас проходит зимняя смена ЛКШ (Летней Компьютерной Школы), и мы в составе параллели А*+ с ее преподавателями подготовили полноценный <a href="/contests/1286,1287" style="color:#03A89E !important; font-weight:bold">Codeforces Round</a>. Раунд состоится в [contest_time:1286] и продлится 2 часа. В каждом дивизионе будет предложено по 6 задач. Задачи раунда были придуманы и подготовлены [user:ismagilov.code,2020-01-04], [user:devid,2020-01-04], [user:Volkov_Ivan,2017-05-29], [user:Jatana,2020-01-04], [user:karasek,2020-01-04], [user:polinarria,2020-01-04], [user:cookiedoth,2020-01-04], [user:AlesyaIvanova,2020-01-04], [user:doktorkrab,2020-01-04], [user:AliceG,2020-01-04], [user:D.Pavlenko,2018-01-04], [user:VFeafanov,2020-01-04], [user:LordVoidebug,2020-01-04], [user:forestryks,2020-01-04], [user:Ilistratov,2020-01-04], [user:seiko.iwasawa,2020-01-04], [user:DeadInsideOnTest993,2020-01-04], [user:Drozd_off,2020-01-04] под руководством преподавателей [user:PavelKun...

Полный текст и комментарии »

Problem Database - Idea for a CP-related project I can sometimes see people doing some CP-related projects for their courses/portfolio/community, and I want to suggest an idea of such a project that would benefit me as a CodeChef Admin and all the problemsetters, I believe. Issue: There are a lot of problems on different platforms, and it is really hard to check if some problem was already used somewhere or not. Sometimes googling works, but most of the time I have to rely on my own experience and memory, which are far from perfect. It's hard to search for problems, because they usually have some kind of story, and the same problem can be formulated in a lot of different ways. Proposed solution: Create some kind of smart database, that will collect the problems from all known sources and will have some very smart search engine that would focus on the internal meaning of the problem, instead of how it is formulated. I have no idea how to do any of that :) I would assume that it would require some kind of very smart ML and a l...

Полный текст и комментарии »

The 1st Universal Cup. Stage 13: Iberia Hello Codeforces! The 13th Stage of the 1st Universal Cup is coming. It will be held from April 22nd to 23rd. This contest was first used in the Petrozavodsk Programming Camp Winter 2023, and also appeared in the 2023 ICPC Training Camp powered by Huawei and the Hello Muscat 2023 Bootcamp. If you participated in any of those, you should not participate in this stage of the Universal Cup. All the problems were authored and prepared by [user:998batrr,2023-04-21], [user:244mhq,2023-04-21], [user:353cerega,2023-04-21] (Harbour.Space [P+P+P](https://mirror.codeforces.com/team/102621), Barcelona, Spain) and [user:Um_nik,2023-04-21] (Lisbon, Portugal). We want to thank the Universal Cup Committee for staying true to the spirit of 5h/3person/1pc contests and for providing the opportunity to share our contest with a wider audience. As usual, we have three time windows for participating. You can participate in the contest in the following three time windows: [Time Window 1: April 22nd 13...

Полный текст и комментарии »

THE OPTIMAL PRACTICE STRATEGY (**NOT CLICKBAIT**) Spoiler: it's clickbait. Sorry. Titles like those are fun. ...but, it's the same style of clickbait as my [roadmap](https://www.youtube.com/watch?v=bSdp2WeyuJY) [spoiler 2: if you haven't seen that, it markets itself as a standard roadmap (y'know, soulless and devoid of purpose), but then a few minutes in, says "ok but roadmaps are stupid and here's the advice that you really need" and completely changes the direction of the video]. That's my style of clickbait, and that's the vibe this blog goes for. [cut] <br><br> So... hear me out, please. The start ------------------ First, a couple meta-notes. I will likely exaggerate my tone a bit here for dramatic effect. Don't take it personally, please. Also, **this applies to almost all ratings**. At the very least, I recommend you process the main point of this blog and see whether or not you already do something similar (for most people... probably not?) The problem ------------------ I'm sure if you've looked at the...

Полный текст и комментарии »

Codeforces Round 968 (Div. 2) (After 3 months) Hello again, Codeforces! We are glad to invite you to participate in [contest: 2003], which will start on [contest_time: 2003]. You will be given **6 problems** and **2 hours** to solve them. Two problems are divided into two subtasks. This round will be **rated** for participants whose rating is **below 2100**. Participants with higher rating can participate unofficially. The problems were authored and prepared by me. I would like to thank: - [user: 244mhq, 2024-8-23] for perfect coordination. - [user: A_G, 2024-8-23], [user: wutongchun, 2024-8-23], [user: yeminghan, 2024-8-23] for red testing. - [user: DisconnectedGraph, 2024-8-23], [user: small_peter, 2024-8-23], [user: JWRuixi, 2024-8-23] for orange testing. - [user: yinhee, 2024-8-23], [user: QwQwf, 2024-8-23], [user: Jryno1, 2024-8-23], [user:sinsop90,2024-08-23] for purple testing. - [user: dieselhuang, 2024-8-23], [user: WRuperD, 2024-8-23], [user: CSQ31, 2024-8-23], [user: gdf_yhm, 2024-8-23...

Полный текст и комментарии »

Umdate The first episode of [Um](https://mirror.codeforces.com/blog/entry/113418) airs tomorrow, here is the [link](https://www.youtube.com/watch?v=G0HzqzOZ5hY). I hope you'll enjoy it! I added three more problems to the [list](https://um-nik.notion.site/cff90514c6174afcb4ab8ff5dbb5b9a3?v=88948840b1494f18aea5535a6329a914). After the episode is released I will add the slides I used. [user:aryanc403,2023-03-08] made a nice [checklist](https://um-checklist.aryanc403.com/) for tracking your progress on Um problems. [My YouTube channel](https://www.youtube.com/@umnik_team), [Discord](https://discord.gg/HPjyarXvsN), [Um_nik World](https://bit.ly/Um_nik), [Tutoring](https://bit.ly/Umnik_tutoring). I will not do a CF blog each time something is released in the future, so join [Discord](https://discord.gg/HPjyarXvsN) if you want to follow the news.

Полный текст и комментарии »

Codeforces Round #315 Editorial [problem:569A] Suppose we have downloaded $S$ seconds of the song and press the 'play' button. Let's find how many seconds will be downloaded when we will be forced to play the song once more. $\frac{x}{q} = \frac{x-S}{q-1}$. Hence $x=qS$. Solution: let's multiply $S$ by $q$ while $S<T$. The answer is the amount of operations. Complexity &mdash; $O(\log T)$ [problem:569B] Let's look at the problem from another side: how many numbers can we leave unchanged to get permutation? It is obvious: these numbers must be from $1$ to $n$ and they are must be pairwise distinct. This condition is necessary and sufficient. This problem can be solved with greedy algorithm. If me meet the number we have never met before and this number is between $1$ and $n$, we will leave this number unchanged. To implement this we can use array where we will mark used numbers. After that we will look over the array again and allocate numbers that weren't used. Complexity &mdash; $O(n)$. ...

Полный текст и комментарии »