### Um_nik's blog

By Um_nik, history, 3 weeks ago,

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, 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 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 and not because this is the only place on the Internet where my opinion matters a little.

So, there is this thing called puzzle hunts. Basically, it's a set of puzzles, but they don't tell you the rules. And the idea is to bend the rules even if there are some. Some blog about puzzlehunts. The quote in the beginning is great:

Imagine a word search.

Now imagine you aren’t told what words to look for.

Now imagine you aren’t told it’s a word search.

Now imagine it isn’t a word search.

I'm not experienced in this at all, my first puzzle hunt was a year ago. 2023 MIT Mystery Hunt ended yesterday, and this weekend was one of the most fun experiences of my life. And I encountered the best puzzle of my life to date (which is not saying much). Spoilers for MITMH23 below.

Enter Showcase (I would not be surprised if the link will not open, the hunt just ended and I don't think the site was totally transformed into free form, so you might have to wait a bit; UPD we now have a PDF courtesy of one of the authors). Authors of this puzzle include

This is a spoiler not only to the puzzle but to the story below

This story starts around 1 pm (in my timezone) on Saturday. I open the puzzle and see 12 small grid puzzles. I love grid puzzles, I want to try and solve this one. Flavor text says

This is the last thing I'm putting under a spoiler tag, I WILL SPOIL THE SOLUTION TO THE PUZZLE

which probably means that I won't be able to solve the grid puzzles as is. But I don't understand what to do instead, so after some staring, I decide to try anyway. Surprisingly for me, the first 10 puzzles are pretty normal, they have a unique solution and some of them are interesting to solve (try E, H and I). This doesn't really help, as I still have no idea what to do next. I switched to a different puzzle.

Around 2 am in the night I thought that we should request a hint. The hint was "Read the flavor text carefully — it seems to be directing your intention to certain parts of the logic puzzles' instructions. Read those parts in order to find a cluephrase for what to do next." I did that and got... FIND ANOTHER CONTEST MIT WON RECENTLY, WATCH BROADCAST AFTER HOUR FOUR, OVERLAY LETTERS FROM FITTING ACRONYM IN SPOKEN ONE MAYBE TWO WORDS WITH TITLES.

MIT won the finals a couple of months ago... broadcast? hour four? wait, there are 12 puzzles which are numbered with letters?! Yes, this is certainly about ICPC WF. And look, this final has exactly 12 problems! I'm calling VArtem, who was one of the two not-yet-asleep members of our team, to join me.

Intrigued, I open the recording of the broadcast. They are talking about FFT, which is an acronym... but what to do with it? Rewatching several minutes around the 4-hour mark, nothing. But it is surely about the finals, and we should match 12 puzzles to 12 problems in the problemset. We look at the names of the problems, we open the problemset (I didn't want to spoil the problems to myself, but MITMH requires some sacrifices (mostly sleep)). Here it is, crystal structures (did you notice 12 phrases under the puzzles?)! But no, nothing else matches...

And then VArtem says:
- He said it! He said "writing system on them"!
- What? — I'm confused.
- One of the phrases! ecnerwala says it on stream!

Since I was rewatching several minutes around the 4-hour mark for the fifth time, I was too slow here. But the hint was to watch broadcast after hour four, not right after.

So, ecnerwala is going through the problemset and saying the phrases. We found couple more and... why is he saying weird words? People don't normally say "discrepancy" and "inconspicuous". Wait, ecnerwala. ecnerwala is from MIT. They didn't just take a video and made an ICPC-related puzzle. He is doing that on purpose!

Then we spend half an hour trying to hear phrases from the statement and writing down words. Then half an hour more for problem F. Then we just gave up. From the official solution to the puzzle: You might have encountered some difficulty finding the special phrase for Problem F — this was because the stream cut out while Andrew was covering this problem! We had to get Andrew to re-mention problem F some 30 minutes later, at timestamp 4:54:30.

Okay, we got almost all weird words and correspondence to problems, what's next? After several minutes I notice that several grid puzzle names have the same length as corresponding weird words. What was it, "OVERLAY LETTERS FROM FITTING ACRONYM IN SPOKEN ONE MAYBE TWO WORDS WITH TITLES"? We had to write down two words instead of one to get all lengths to match, but other than that it looked good. Ok, ICPC would be a fitting acronym, but... wait. Wait wait wait wait. All the weird words have a subsequence ICPC. Seriously?

Taking the corresponding letters we got ORDERPROBLEMSBYMITSO????IMETAKEFIRSTLINEOFOUTPUT. Or ORDER PROBLEMS BY MIT SOLVE TIME TAKE FIRST LINE OF OUTPUT. Output? Puzzle solutions you mean? Ok, we try, and it doesn't look good. Sample output? Doesn't look good either. After another half an hour of trying different things we decided to take another hint. Maybe we shouldn't have do it so soon, but we (well, at least I, can't say for Artem) really wanted to solve this CP-related puzzle and it was already 4:30 am.

The hint says "What does "output" mean in the context of ICPC problems? You'll need some corresponding "input", where can you find it?".

I mean... we still haven't used the puzzles. Could it be?.. We look closer at the puzzle solutions...

For the next 20 minutes me and VArtem are just sitting there and each minute one of us says some variation of "this is amazing". THEY MADE 12 GRID PUZZLES WITH DIFFERENT RULES (some of them are even good) WHOSE SOLUTIONS ARE VALID INPUTS TO ICPC WF PROBLEMS. I will repeat that and I don't think that caps is enough to emphasize what has happened.

THEY MADE 12 GRID PUZZLES WHOSE SOLUTIONS ARE VALID INPUTS TO ICPC WF PROBLEMS. ICPC WF is a serious prestigious competition. I am pretty sure that ecnerwala did not know anything about the WF problems before the contest. The problems could have had wildly different input and output formats. This is just unbelievable to me.

And don't get me wrong, the puzzle before that was also very good and very cool. ICPC subsequence is cool, and what's even more amazing about it is that ecnerwala managed to naturally mention all the words he needed as it was a normal discussion of the problems. And again, they didn't have the problemset beforehand, so they had to come up with all these natural-sounding phrases in 4 hours between the start of the contest and Andrew's amazing performance. They could have prepared some words with ICPC subsequence, sure, but to include them into a text about a problem...

But the puzzle to inputs step knocks it out of the park for me. Obviously, unlike ICPC words in the broadcast, the grid puzzles and their names were not written in 5 hours, but I couldn't do it in a lifetime. I want to show my appreciation to the authors. And I'm really happy that in our team the people who solved this puzzle could appreciate it to the full extent (I would be surprised if there was another team with 2 former ICPC world champions (actually we had 4, including tourist (see, tourist does it, it is surely the secret ingredient to being LGM))).

So, a big thank you to ecnerwala, ksun48 and other authors. I assume that you guys are a part of teammate? Probably your experience in puzzle hunts is much more valuable than mine, so it would be cool to hear from you.

And if I convinced you to look at the puzzle hunts, here is a short guide I wrote for our team. It is bad, and there are much better guides out there, but I made it, so here it is.

• +348

By Um_nik, history, 7 weeks ago,

I'm all for companies sponsoring CF rounds and getting PR from it, authors deserve the salary, and CF has to get money for those somehow (paid rounds anyone?). But can we please stick to numbering for rounds instead of putting random words in the name (or keeping the number in the brackets)?

That's what my folders for rounds look like (and I don't like it):

Example from AtCoder

Example from Codeforces, lol, why can't we do it every time?

• +269

By Um_nik, history, 7 months ago,

I noticed that in many recent round announcements authors thank the coordinator for some kind of especially good coordination.

803
801
800
795
793

Did those coordinators do something special? If so, what exactly was so amazing about their work?

It is also interesting that they are using different words every time, which makes me think it is a meme of some sort. Is it?

• +176

By Um_nik, history, 8 months ago,

I came up with this idea when solving an AtCoder problem, but the editorial had a simpler solution. I liked the idea, so I decided to set a CodeChef problem 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

Let's generalize this a bit and say that $P$ and $Q$ are polynomials of degree at most $d$ and we want to calculate $P^k Q^{n-k} [x^k]$ for all $k$ ($d = 1$ in the problem above).

Let's apply divide-and-conquer. Let's say we want to solve the problem for $k \in [l, r]$. Then all the interesting polynomials will be divisible by $P^l Q^{n-r}$. Let's say we somehow calculated this polynomial. For given $k$ we will then have to multiply it by $P^{k-l} Q^{r-k}$. But the degree of this polynomial is $d(r-l)$, and since in the end we will be looking only at coefficients from segment $[l, r]$, right now we only care about the coefficients from segment $[l - d(r-l), r]$, all the other coefficients can't affect the answer. So, the number of coefficients we are interested in is $O(d(r-l))$. Let's write a recursive function that will take $l$, $r$ and a segment of interesting coefficients of $P^l Q^{n-r}$ and will find all the answers for $k \in [l, r]$. We'll choose $m = \frac{l+r}{2}$ and recurse to $[l, m]$ and $[m + 1, r]$. To recurse to the left, for example, we'll need to multiply $P^l Q^{n-r}$ by $Q^{r-m}$ and take a segment of coefficients. Since both polynomials have degree $O(d(r-l))$, we can multiply them in $O(d(r-l) \log (d(r-l)))$ time. To get $Q^{r-m}$ one can use binary exponentiation, it will work in $O(d(r-m) \log (d(r-m)))$ time (if $d=1$, one can use binomial theorem instead). The total complexity will be $O(nd \log^{2} n)$.

• +277

By Um_nik, history, 13 months ago,

CP is about solving problems fast. And as absurd as it may sound, I believe that SOLVE and FAST are very different and almost independent parts, and you need to practice them separately.

Let’s look at some contest, 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.

Graph 1

On the moment of a contest you have some ability to solve problems. If we assign each problem with numeric difficulty, it is reasonable to say that your problem solving ability is also a number on the same scale. But it doesn’t mean that you can solve all the problems below your level and can’t solve anything above your level... it’s more like “probability distribution”, or maybe how much time you need to solve the problem of given difficulty:

Graph 2

The issue is this probability distribution is something close to sigmoid: You can surely solve the problems that are much lower than your level and you solve them almost instantly after reading; on the other hand, you need too much time, maybe even infinite time, to solve problems way above your level. And that interval of difficulties which is not too easy while not too hard for you is rather small. Let’s call this interval interesting.

Since one contest has only a few problems and should cover a wide range of difficulties, there is usually one problem in your interesting interval, rarely there are two, sometimes there are none. These are the situations to which some participants refer to as speedforces: your result in the contest depends on how fast you solve easy problems. I don’t want to disappoint you, but almost every contest is a speedforces contest in a sense that your result is mostly determined by your speed and accuracy on easy for you problems or, how I call them, problems that you already know how to solve. In a contest, you don’t have time to come up with something completely new and original. Yes, you need to get what is the problem about, unravel some layers of reductions and implement the solution, but in a nutshell you know how to do every small part of the problems you will solve in the contest before the contest even starts.

What I’m trying to convey is that in a contest your goal is to solve the problem that you already know how to solve fast. By doing X you learn how to do X, so by participating in contests you learn how to solve problems fast. But then where do you learn how to solve problems?

To learn how to solve problems you need to solve problems, solve problems that you don’t yet know how to solve, but that are possible for you to come up with, maybe using a lot of time. These are the problems from the interesting interval, slightly above (or below in some cases) your current level, but not too much above because otherwise you can’t solve them yet. So we need to somehow find a lot of problems near your level, how to do that? The answer is rather simple: go to a place that has a lot of problems of various difficulties and doesn’t have a time limit. It is not a contest, it is an archive.

Graph 3

Just by having a lot of problems archives can almost always provide a problem of needed difficulty. And you don’t really need to do anything special to achieve that: sort the problems in the archive by difficulty and solve them. After the first period when the problems are too easy for you you will always be at a level where the next problems are the right difficulty for you because after solving a hundred problems your level will rise a bit, but so will the difficulty of the next problems.

I notice that nowadays many people start from CodeForces contests, and I think it is bad and it is the underlying reason for many frustrations. Some things that come to my mind:

• Newbies are ok with repeating problems in contests, problemsetters shouldn’t be so worried about problems being fresh — you should solve old problems in archives, learn classic techniques there and then use them in contests, contest problems need to be fresh.
• Where will we learn stuff if in contests there are no problems on classical techniques — again, learn the techniques themselves in archives, then you will see that there actually are problems that use classical techniques in contests, and obviously, there should be no problems that just are classical in contests.
• It is hard to make a training regime out of contests — it is, and you shouldn’t do this, contests should be only a part of training regime.
• Contests allow that self-deception thing: you can solve a lot of problems in contests, but they are the problems you already know how to solve and that doesn’t increase your level.

Q: How long do I try to solve the problem in the archive before reading the editorial? Like, 30 minutes?
A: You don’t read the editorial. The best option is to choose an archive that doesn’t have editorials at all, so you don’t have to fight the urge to look at the solution.

Q: Ugh, and what should I do if I can’t solve the problem?
A: Abandon it, for now, switch to a different problem, return to it after a month or so. My usual approach was to open 10-15 problems, read them carefully, think a bit, choose the one I want to try and solve now, try for some time. If I don’t feel like I’m getting anywhere, switch to another problem.

Q: Month?!
A: Maybe even more. You need time to acquire new skills and discover new ways to look at this problem (by solving other problems). It doesn’t make sense to return in less than a month because you will only run through the same ideas you did before.

Q: Ok, but how do I learn new techniques if I don’t read editorials? I’m not supposed to invent everything on my own, am I?
A: Most of the time you don’t need to learn any advanced stuff to solve the problem, you can’t solve it because you are not trying hard enough or not paying attention to details or just being stupid. My experience even says that most Russian schoolchildren who do CP know too many algorithms.

Q: But there are problems that require some standard things!
A: OK, yes. The best option, in my opinion, is to have some person around who solves the same archive and is better than you. In case you are stuck on a problem for a long time (that’s not an hour, that’s several months) you should ask them “Do I have to know some standard technique to solve this?” Pay attention: not ask how to solve, or for a hint, just a yes/no question. Most of the time the answer will be “No”. In the case of a positive answer, they will be able to send you a link to an article or what to google to learn about the technique. After that, you still will have to apply this technique to the problem, and you are more likely to actually remember how to use it and why did you need it in the first place, which tremendously increases your chances to use it successfully in the future.

Q: OK, which archive should I use?
A: It is not that important, but you should use one and stick to it. I have used Timus because I’m from Ural region, there are numerous others: UVa, SPOJ, Codeforces archive (has editorials and too many problems, thus a warning) etc.

To sum it up:

In archives you learn how to solve problems, in contests you learn how to do it fast. I’m not saying that contests are not needed: speed is also very important, and it is good to keep you in competitive shape. Also participating in contests is just fun, that’s also very important.

Acknowledging this and separating learning how to solve from contests can lead to better training, I believe.

How to split the time between archives and contests? Well, contests are held in some fixed time, so when there is a contest that fits into your schedule, you shouldn’t miss it. Turn to archive when you want to practice and solve something which should be often, otherwise CP is probably not for you.

• +1117

By Um_nik, history, 16 months ago,

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 lot of community effort. But I thought that it might be an interesting project for someone and I really hope that it will be done by some amazing person.

Just a database of problems from different sources with any kind of full-text search would also be nice.

I think I'm ready to pay some reasonable money (\$1000? I understand that it's small money for a high-level ML person, but I'm not rich) for a well-done job, and maybe we can crowdfund it even more.

• +470

By Um_nik, history, 16 months ago,

Hello Codeforces!

I will hold a Q&A/AMA stream on Twitch on Tuesday, 21 MSK (UTC+3).
You can write your questions in chat during the stream, or send them in this form beforehand (for example, if you can't attend the stream in person). Recording will be uploaded on YouTube afterwards.
Questions written in Russian will be answered in Russian, questions written in English — 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.

Huge thanks to lperovskaya who has agreed to help with this.

UPD: I won't answer questions like "how to become red", "how to become better at topic X", "how to win icpc wf". Answer

UPD2: Thanks to those who have come to watch this clownfest, here is the recording, including the last part during which my internet has died.

• +273

By Um_nik, history, 16 months ago,

I'm not allowed to bring my phone into contest area, but I can live-codeforces this ICPC Challenge

• +243

By Um_nik, history, 17 months ago,

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 interesting for proposers of hard problems — you don't have to come up with easy problems. You can also propose a lot of problems on your favourite topics, as we won't put all of them in one contest.
• Your problem will be reviewed by me, discussed with me and then maybe enhanced. You might have different views on my persona, but it is hard to deny that I'm pretty good at this stuff.
• In normal circumstances your problem will be reviewed less than a week since submitting proposal. (You might have to wait for it to be used in contest though)
• We are pretty low on harder problems, so if you propose a (good) Medium+ problem you can expect it to be used soon.
• We pay more. I know, I know, we do it not for the money. But it is a nice bonus, isn't it?

With that sorted, let's take a closer look at what have we changed.

Some of the changes are internal and it's hard to show them, but hopefully those changes will simplify the life of contest admins and they will have more time and energy to work with problemsetters and oversee the contest preparation.

• We have separated reviewing problem proposals and admin-ing (coordinating) contests. Now we have a special person, whose job is to review proposals and try to improve them. That person is me right now, although I hope that this system will outlive me, as it is more fair and leads to better problems. Yes, better problems, as my job is not only reviewing the proposals, but also thinking on ways how to make them better. Most of the short contests in 2021 had at least one hard problem significantly improved during the review.
• Making problems better requires collaboration with setters, which starts from communication. We used emails before, and it was... not ideal. Now we have created a dedicated Discord server, where we create private channels for me to communicate with setters. On the same Discord server we create channels with all the setters for a particular contest, where they will be able to talk with admin, tester, and generally people working on the contest. Moreover, if there is an issue that requires some managing help (like providing access) it will be easy to ping managers. I will not put a link to the server here, and I ask setters who has it to not do it too: we want only people who are interested in problemsetting there.
• Many people hate Campus (the system which was used for preparing problems on CodeChef), and rightfully so. We don't like it either. That's why we have gotten rid of the entire UI and have built a new problemsetting portal from scratch. We have implemented many essential features which were previously lacking (bulk uploading of test files, bulk editing of time limits, and judges, statement history versions, copyable sample IO, etc), and are working on adding the missing features as well. We know we still aren't as good as Polygon, but we are working towards it. We ask setters to prepare the problem on Polygon, and then port them to CodeChef.
• This is an internal thing, but I'm very proud of it. In general, we have a big waiting list of problems that are approved but not yet used for contests. When we need to make the next contest, an Admin is assigned, and he then chooses the problem from the waiting list. This waiting list was stored in a Google Sheet, it was hard to maintain and even harder to choose problems from it, and mostly we had to rely on our memory to choose problemsets. Now the waiting list will be stored in Notion. We will have to migrate the waiting list manually, and this work is far from done, but the future of stuck-in-the-waiting-list problems looks a bit brighter now, as we will be able to actually consider them while choosing problemsets.
• The CodeChef problem setting portal is still not a very user friendly system. And to use it you have to somehow learn how to do it. There is a guide for it... accessible only by a link you have to somehow get. Also this guide is written several years ago. Yeah. Actually, there are more different guides, sometimes contradicting each other. But it's not much of a problem, you have close to 0 chance to find them. Well, this had to stop. Either by CodeChef dying out because the link to the guide was lost and now nobody knows how to upload problems, or by us making an effort. We have chosen the second way, and it's Notion to the rescue again. Introducing CodeChef Public Guides. It's very new, but at least there are links to all the old guides I could find. We are planning to write more articles on all things related to CodeChef problemsetting, and maintain them in relevant state. Right now there are articles on step-by-step process of setting a problem and what (not) to do when proposing a problem. I'm planning to write an article on good practices when working with Polygon next.
• We have increased our judge server capacity and have not had a queue issue in a long while. We are in the process of scaling it 4x (and more) in the coming months, which will allow our setters to not have to worry about keeping the testfiles to a minimum.

In case I have managed to convince you to become a problem setter on CodeChef, here is the link. But please read this first.

What changes would you like to see on CodeChef, either in problemsetting or in general? Please help us make CodeChef better by filling this form.

• +632

By Um_nik, history, 17 months ago,

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 Alex_2oo8 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.

• +914

By Um_nik, history, 17 months ago,

Big thanks to KAN who uploaded these two contests with ghosts and everything and even tuned up TLs a bit for CF.

2019-2020 Winter Petrozavodsk Camp, Day 8: Almost Algorithmic Contest

2020-2021 Winter Petrozavodsk Camp, Day 5: Almost Retired Dandelion Contest (XXI Open Cup, Grand Prix of Nizhny Novgorod)

The second contest was used as an OpenCup stage last season, while the first one was not published anywhere (except some secret Chinese servers I assume).

Selfpromotion: I really think that these two contests are amazing. The difficulty is comparable to ICPC WF or harder regional finals (but with a smaller number of easy problems, who needs them anyway).

I was the author of more than half problems from both contests, with additional problems contributed by KAN, vepifanov, I_Remember_Olya_ashmelev, kristevalex, Merkurev and WYOCMWYH. I also want to mention the authors of three original problems that were improved and reused in the second contest: Ferume, fake123 and dario2994.

Enjoy!

• +216

By Um_nik, history, 19 months ago,

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
• 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
• That derivative magic by Elegia
• That new subset convolution derivative magic by Elegia
• How Elegia's mind works
• Sweepline Mo
• Matroid intersection

If you know at least 3 of these things and you are not red — you are doing it wrong. Stop learning useless algorithms, go and solve some problems, learn how to use binary search.

• +1965

By Um_nik, history, 2 years ago,

Time: Feb 7, 11:00 UTC+3

Authors: Um_nik, Merkurev, KAN, WYOCMWYH with help from I_Remember_Olya_ashmelev, Ferume, fake123 and dario2994.

The contest was used for Petrozavodsk training camp and ICPC training camp.

Editorial

• +272

By Um_nik, history, 2 years ago,

We invite you to participate in CodeChef’s December Lunchtime, this Saturday, 26th December, from 9:30 pm to 12:30 am IST.
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:

Problem Submission: If you have original problem ideas, and you’re interested in them being used in CodeChef's contests, you can share them here.

Prizes: Top 10 Indian and top 10 Global school students from ranklist will receive certificates and CodeChef laddus, with which they can claim cool CodeChef goodies. Know more here.

The video editorials of the problems will be available on our YouTube Channel as soon as the contest ends. Subscribe to get notifications about our new editorials.

Good luck and have fun!

As this is my first contest as CodeChef admin, I wanted to add few words from myself. Please do consider setting problems on CodeChef, we need your help to create great contests! One of the advantages of setting problems on CodeChef is that you don't have to create whole problemset by yourself (though it is certainly possible, you can write directly to admins to contest.admin2@codechef.com for LunchTimes and to contest.admin3@codechef.com for Cook-Offs). Many new authors can't create whole problemset without experience, and that's totally understandable! Sending problems for review allows you to get feedback for our admins (Um_nik, 300iq, jtnydv25, Ashishgup and Morphy), and if your problem is good, you will get the invaluable experience of setting a problem for thousands of participants worldwide while working side-by-side with some of the best minds in competitive programming. Some of the best problems in this contest are set by first-time problemsetters, at least on such a level, and they did a great job, I'm looking forward to working with them again.

Apologies to SeismicToss for messing up the announcement :)

The contest is unrated due to queue and server issues.

• +350

By Um_nik, history, 2 years ago,

I have resumed screencasts with commentary, you can find them here

• +130

By Um_nik, history, 2 years ago,

In yesterdays ACL1 I got WA on problem B. It turns out that compiler ignored the function call inside assert, the same code with function call not in assert works fine. Moreover, Merkurev explained that the reason for that is -DNDEBUG flag, and my submission works on GCC.

I don't understand computers, I just memorized some stuff that's enough for solving puzzles. I want to ask why the -DNDEBUG flag used in Clang, but not in GCC. rng_58?

• +170

By Um_nik, history, 3 years ago,

Since antontrygubO_o 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

• +1794