Um_nik's blog

By Um_nik, history, 4 months ago, In English

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.

The questions that I anticipate (ask your questions in the comments if needed):

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.

Read more »

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

By Um_nik, history, 7 months ago, In English

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.

Read more »

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

By Um_nik, history, 7 months ago, In English

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.

Read more »

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

By Um_nik, history, 7 months ago, In English

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

Read more »

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

By Um_nik, history, 8 months ago, In English

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.

Read more »

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

By Um_nik, history, 8 months ago, In English

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.

Read more »

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

By Um_nik, history, 8 months ago, In English

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!

Read more »

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

By Um_nik, history, 11 months ago, In English

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

Read more »

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

By Um_nik, history, 15 months ago, In English

Time: Feb 7, 11:00 UTC+3

Link: Click (OpenCup login needed to participate)

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

Read more »

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

By Um_nik, history, 17 months ago, In English

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.

Read more »

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

By Um_nik, history, 20 months ago, In English

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

Read more »

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

By Um_nik, history, 20 months ago, In English

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?

Read more »

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

By Um_nik, history, 22 months ago, In English

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

Read more »

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

By Um_nik, history, 2 years ago, In English

I have to ask Snark about updates on OpenCup twice a week. If you are as tired and don't want to miss next Grand Prix — join this Telegram channel. I will try to post anything I was able to get from Snark. Hopefully he will come to his senses and will admin the channel himself some time in the future.

UPD: Snark has admin rights now, maybe we will get the news in time.

Read more »

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

By Um_nik, history, 2 years ago, In English

As you may know, Petrozavodsk SU holds training camps for top teams twice a year. This time we decided to try to do screencasts of our participation, you may find them here. Unfortunately due to some technical errors we lost screencast of the first contest and the last 2 hours of the second one (we are not pros in screencast area, sorry).

Please note that if you are going to participate in Izhevsk mirror or by other means participate in these contests, you may ruin the fun for yourself.

Read more »

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

By Um_nik, history, 2 years ago, In English

Any explanations why at the same time happened this to these legends? :O

Read more »

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

By Um_nik, history, 2 years ago, In English

I'm thinking about doing more videos, not only screencasts of rounds. For some time now I'm using OI Checklist by Rezwan.Arefin01 (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.
4. Despite these are OI-style problems with partial scoring I'm trying to go for a full solution, most of the time ignoring groups. Sometimes full solution of these problems are really-really hard. Should I do groups always, or only when I'm stuck for long time, or other options?
5. Do you have any suggestions about what kinds of videos I should make? Or other things I didn't think about concerning this particular kind?

You can look at my channel here

UPD
Thanks for your input! I thought a bit myself and here is my current position:
I'm willing to invest some time to learn basic video editing (yeah, didn't do anything before, just recording screencasts), I hope that I will even add some things to screencasts in post. This way I can read some problems, then solve them one-by-one, but make separate videos for each problem. Mostly I will do "blind" attempts at problems, since most of your want to see me struggle :) I will go through groups if they are interesting, but rarely will implement partial solutions.
About lectures and lower-level educational videos: don't think so at least for now because it is not interesting for me.
Because of learning basic video editing I will be slower at first, but I hope to do first video in next few days, so stay tuned! Also later today I will upload USACO Platinum screencast, so you can watch this if you are interested.

Read more »

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