You also need to be fully vaccinated (with proof of vaccination) to be able to attend World Finals in Russia.

And that is "fully vaccinated" from the perspective of Russian authorities, right? I.e. if you got Pfizer or Moderna you can turn around and fly back home?

Nobody said it should be about doing two sports at the same time — maybe a person did CP in the past.

Nobody said it is about doing two sports seriously. CP dedication isn't required.

There are many examples of people successfully doing multiple sports in parallel or one after another. See this list for some examples.

This is especially true for disciplines that are related: for example, if it is some endurance sport that is mainly about making the engine work (running, cycling, rowing etc.), it is not uncommon to be doing several in parallel or to move from one to another for some reason (e.g. due to an injury). Same story with people doing speed skating in winter and track cycling in summer.

BTW, Alan Turing was not too far from making it to Olympics as runner.

Mentioning an achievement of participating in mass events that don't have any qualification prerequisites and don't require any real fitness to complete is, in the context of this thread, at the very least disrespectful to people who are actually doing some sports seriously. Please don't do it. The next step is to list people with gym membership.

A lot of users don't care about rating, or at least don't care about it enough to put effort into improving it.

Blindly assuming that every person on your list is "very determined" is like saying that everyone who is playing online games for years must be "very determined". Everyone has their own story: some folks care but don't have enough time to practice properly, some folks care but don't really understand that they should practice at all, some folks don't care and simply enjoy participating in contests.

What was the model solution for C?

Somewhat confusing wording in I: in real world "wind direction" is usually understood as the direction from which the wind originates, and you are using the opposite of it.

As far as I can tell, we were expected to derive speed and initial shift from samples.

At least that other understanding doesn't pass samples. That was the point at which I figured out that something is wrong: coding is done, I fail first sample, OK let's actually look at the samples now...

Do you realize that by revealing this secret to your opponents you are going to make things much more competitive?..

Outside India, nobody is interested in your ratings, and there are no cheaters.

If not "cheating", what would be the right word for the intent of my incoming messages with content like "I'm a student, I want to get internship at Google/Facebook/Microsoft, I'll pay you to boost my account so that I can put it on my CV to make it more attractive"? I had such messages from people in Europe. I even had such message from a person aiming for Google specifically, sent to me at the point when I was already working at Google :)

I'm relying on assumption that under some setups catching cheaters is much easier than under some other setups, and therefore one should use those more fair setups as a more trustworthy and reliable indicator of skills and achievements.

People cheat during offline events in chess, people cheat during offline events in ICPC as well (I don't know about any really bad cases for World Finals, but I know lots of cases for different regional events, and only in some of them there was punishment involved), but it is not nearly as bad as online precisely because it is much harder to cheat.

My point isn't about "not seeing it", my point is about relying on that "harder to cheat" criterion. How much I am upset about cheating is proportional to how much I expect it to not be happening, which correlates with that "easy to catch" part. If it is an OTB chess game at some competition, my expectations would be that if somebody is clearly cheating they are going to get punished. Yes, I may get upset if that is not the case — precisely because it didn't match my expectations. If I played a game online today and then tomorrow somebody told me that I was playing against a cheater, that wouldn't be much of an upset not because I didn't see it during the actual game, but because dealing with that stuff online is expected.

I don't have expectations that there will be no cheating in online events, and I understand that there is no easy way to fight that kind of "PSA: here are solutions for free" approach, so it doesn't make difference to me if it happens in a private small group or publicly in Telegram / YouTube / Discord. It is generally disappointing when the subject is raised, but I don't see anything unexpected here.

This shouldn't be too much of a problem as long as cheating is more or less limited to online events.

I can play chess online knowing that the person on the other side may be using chess engine — and still enjoy the process. Even if I'm playing online against people who may be cheating, I can still use some relatively objective metrics (like online rating or average centipawn loss or whatever) to measure my progress. And if I eventually learn to play really well, in Wijk aan Zee or during Candidates Tournament folks playing against me are likely going to play fair.

Same holds for programming competitions. If there is any issue to solve here, it is probably about changing the perception so that recruiters don't buy into online ratings, or at least take them with a lot of scepticism. Participants have much harder time cheating during ICPC World Finals, (offline edition of) IOI, GCJ Finals etc.

Sure, seeing that people cheat is discouraging, but I think you are focusing on it too much. For a lot of people "others are better than me" is already sufficiently discouraging to stop doing whatever they tried to do.

It is actually a bit sad at the same time: a lot of those comments sound like people don't even know the rules of what they are doing and they actually do believe honestly that sharing only corner cases or pointers to relevant algorithms is not cheating. So you end up having a lot of people who cheat without even realizing that they are cheating, and probably without even intending to cheat.

Thank you for all the comments on old Project Euler problems :)

If there are already enough people who got this belief from somewhere, to me it sounds very optimistic to hope that such alerts will make people change their mind.

Duplicating my suggestion from another thread:

What about developing automated checks that, instead of looking for similarities between submissions for different users, look for discrepancies and anomalies between submissions for the same user? Sure, code style changes, it changes especially often for beginners, sometimes you copy-paste code from a prewritten library with a different style etc. — but still, in a lot of cases there will be stuff that is very suspicious, and I believe modern ML magic is strong enough to highlight a lot of that. To give some random examples, I don't need to find where the code was copied from in order to be suspicious about a user who suddenly decides to use 3 different languages in the same contest. Or, for example, I'd be interested to know motivation of a contestant from, let's say, Egypt, who suddenly decides to use Polish words for variable names in one of their solutions.

I am not seriously involved in chess, so I don't know how well that stuff actually works there, but I've heard that modern online chess are already relatively good at detecting suspicious users (e.g. the ones who may be using chess engines).

Or you just say something that a lot of people find sufficiently offensive, and they all report you.

It is hard to say something for sure without actually looking at the code, so maybe you can share the code as well, and then some kind soul will be willing to look into it and try finding the root cause?

Some random guesses about what could go wrong:

• SPOJ problem has larger N, so that sounds like a higher risk to run into precision issues if your Gauss is poorly written.
• SPOJ has multitest.

102317815 runs in 0.140, and probably can be optimized further.

Initially I was getting TLE because of cin>> input straight into double instead of using much faster int :)

Nice, thank you!

Right, I stopped thinking in this direction after hitting "I don't have enough memory for N^2 bucket sort array".

How do you do "small vs small" part without introducing additional log factor to complexity? My idea was to generate all pairs of elements for each set and then find a pair that occurs more than once, but IIUC this can't be done in linear time unless we are using some hashsets.

I have a slight suspicion that if the difference between my TL solution and my AC solution is "let's optimize by discarding all unique input numbers right away", this means I didn't do the model solution :)

On the other hand, the blog post name suggests to do it as a team (in Russian), and it is a bit optimistic to expect people to put their time into reading the post itself :)

Everyone's situation is different, but I'd say most people still can put in decent hours while working full time, it is just that they don't really want to, and this is totally fine and perfectly reasonable.

I stopped actively training/practicing around my second ICPC WF attempt in 2017. Obviously from that point onward I'm consistently declining in terms of CP skills :) And I'm OK with that. I went for summer internship in summer 2017, and then I started working full time in January 2018.

Realistically I'd estimate that I could average 25 hours of practice per week with no issues at all, and more than that with some more reasonable time management and more structured approach. It is my own decision to not do that — I'm only doing a bit of competitive programming for fun, and I spend the rest of my time on various other stuff. 25+ hours per week would probably be enough to stay in a good shape and continue developing my skills, but I think that approach would've made me less happy than I am right now.

Sure, students can put even more time in, but you can practice quite a lot just as well. Unless you have one of those "Single mother who has to balance 2 jobs and taking care of her small child as well as her old parents" situations, it is mainly your own decision to not do much practice. You have 168 hours per week; if you need 9 hours/day for sleep, and 40 hours/week for work, this leaves you with 168-63-40=65 hours for everything else. Plus you have a bunch of "bonuses" on top of that because of stuff like public holidays or vacations when you don't have to work.

Set your priorities right if you want to invest time into competitive programming; but also think twice if it is worth it. Will reaching red make you any happier? Will it have more direct or indirect impact on your life satisfaction than whatever other activity (socializing, playing games, mastering new skills, watching movies, traveling) you'd have to take that time from?

To clarify, there is a bit of a difference between "Had days when I did something related to competitive programming for 12+ hours" and "Practiced for 12+ hours on average over significant period of time".

The latter was never the case for me, even during the period of time when I was quite serious about competitive programming (during my ICPC WF times). I can't recall a single person doing 70+ hour practice weeks on regular basis, and I don't even know how sustainable that is if anyone tried. From what I know about chess, strong chess players are spending less than that training — and strong chess players seem to be much better at playing chess than strong competitive programmers are at competitive programming.

People are always quick to make up some crazy stories, and it usually goes both ways:

1. Strong contestants spend 20 hours per day training, and up to 30 hours during the days when they are really dedicated to it, that's why they are red and you are not.
2. "I'm training 40 hours per week, why am I not red yet?" (while in fact it is more like 40 hours per month, and usually less than that). This one is then explained by #1 — it should be 40 hours per day, go practice some more.

I know a lot of people who spend 12+ hours per day in front of their computer, it doesn't mean they are practicing competitive programming 12+ hours per day :)

Now "can continuous code for 4 hours" is a different story — it is perfectly reasonable, as in some ICPC setups participants may actually have to write code / work with code more or less continuously for 5 hours.

according to codeforces problem setting guidelines

Are these guidelines publicly available? Knowing what to expect during a round would be beneficial to participants as well, even if they don't prepare any problems themselves — but I didn't manage to quickly find any post on that.

It seems like the expectations changed a lot over the last several years: 5+ years ago integer overflow not being covered by pretests would've been totally OK, and nowadays most of contestants see it as something utterly wrong and unfair.

I wonder what is the actual worst case here? Skimming through the system tests, it looks like 29 is the largest answer?

Can somebody show how to get more strict upper bound of log instead of 2*log?

I've interviewed hundreds of candidates at my time at Google

How many interviews per week do you usually conduct? This "hundreds" sounds like a surprisingly large number based on how long you've been working at Google.

where I post a typical, but unique, interview question, along with follow ups

Out of curiosity — where do you take them from? Are you coming up with the problems by yourself, or do you take some already leaked&banned questions from real Google interviews, or do you use some other source?

Quoted text.

Can also be achieved by using blockquote tag directly:

<blockquote> Quoted text. </blockquote>

As it has been pointed out already, there is analysis available so you may check it for details and proof, but tl;dr is "After sorting, instead of taking median of X[i], take median of X[i]+i".

An example to show why your current approach doesn't work is:

1 1 3

Optimal solution is to do 1->2 to get 1 2 3 in a single move, however by fixing median 1 and trying to achieve 0 1 2 you'll get 2 moves.

We did segment tree + hashes: to check that two substrings are equal you need to check that:

• Their first character is the same.
• The sequence of value differences between adjacent characters starting from the second one is the same.

First part can be maintained in a segment tree by doing segment updates & point queries. Second part is doable by segment tree over the array of differences: since each update changes differences for only 2 positions, you can do point updates & segment queries.

Yeah, I'd say calling a problem "a question" isn't providing nearly as much of a reliable signal as saying "taking a test" instead of "participating in a contest" :)

My classmates directly called me selfish when I refused to show them my answers in exam

Oh, my sweet summer child... There are places in the world where the outcome will be physical abuse and not just being called selfish.

We are already more or less in the area where the theoretical lower bound for potential Wall-Sun-Sun primes is getting high enough to make them irrelevant for the version of the problem that you may face in competitive programming.

Also, like Kaban-5 pointed above, not relying on this property only adds a bit of complexity to the solution, but doesn't really make things change drastically.

There is https://www.spoj.com/problems/PISANO/, which is solvable by simply implementing what's written in "Properties" section in Wikipedia.

I call two vertices "adjacent" if they are next to each other in the list sorted by x or by y (so for each vertex you have a total of at most 4 adjacent vertices — 2 by x and 2 by y).

I wrote in my comment above why this works. You may visualize it with 1D version of the problem where the claim will be more intuitive.

Oh, I didn't think about that. I'd say this fact doesn't make the problem any nicer, although others may have a different taste.

System testing results on E are such a massacre that it probably would've been too much even for good old days when having CF problems that allow hacks wasn't frowned upon :)

It should be clear why running Dijkstra on complete graph is correct. To prove that running it on this "pruned" graph is sufficient it is enough to show that any "non-adjacent" edge can be represented as a sequence of "adjacent" edges, e.g. if you want to get from vertex A to vertex B and the optimal move is to go over coordinate x, you can as well consider all vertices sorted by x and sequentially go through all vertices that are between A and B in this sorted list.

Is "write a DP" elegant enough?

My DP state is

[processed prefix length][# of blocks of removed digits so far][did we remove the last digit?]=(sum of possible numbers, count of possible numbers)

Transition is to consider two options: to remove the current digit or to keep it. Code: 94671611.

Am I missing some simpler solution, or was online part of problem F simply "take offline solution with a segment tree, add persistency on top of that to make it online"?

So now after seeing the actual problem set, where do you draw the line for "easy tasks" for today? A-G? Or do you see it differently?

And what do you think about the problem set in general?

A bit different idea for C, so that you can do it similar to solution 2, but avoiding complicated part with the last segment being reached at different moments from different sides... Or maybe just a different way to approach the same idea.

Generate events "one of the cars reaches some flag" and sort them by time. Now you can say that every time the event happens total speed of two cars increases by 1, so you can proceed events one by one while maintaining current distance between the cars. Once you reach the point at which next event results in negative distance, you know that the cars met between previous and this event, and you know that their speed during that time period was constant, so finding the exact answer is easy. Possible implementation in 94309676.

I found the video from D rather interesting.

87911622 for F is mincut/maxflow, does that count as algorithm?

aabb
xyxy

I still have no idea how to solve that problem, although something did pass pretests eventually. Had to move to more trivial problems like E instead :)

I'd say a lot of people asking for help actually manage to convince me that they weren't aware that asking others to share some links or tell the name of the algorithm while not asking for the detailed solution / code is still considered cheating. Obviously I can't really tell how much of that is honest :)

You shouldn't mix cin & scanf if you are using cin.tie(0);. See this post.

Don't you think that the interviewers/coworkers will recognize that you aren't skilled enough to have mentioned rating?

As an interviewer I see that there is loose correlation between rating and interview performance. People with rating 2000 may perform worse than people with rating 1400, and often it feels like their rating likely isn't achieved by cheating, and they simply can't apply their CP knowledge to anything that isn't CP.

For actual job you will most likely not need any of the CP stuff. I don't need it, for example. My coworkers can't tell if I'm good at CP because A) It is not used for the job; B) most of them don't even have any real CP experience.

It may work differently for different companies in different countries, but on a high level the point of that comment is fair: typically people are doing this in order to get interview calls, and then hopefully get a job — and not because they believe that they will become smarter & better software engineers.

Also, CM can be hardly ever be achieved with cheating. I guess the good fix is that all companies would hire from CM+.

CM+ is easily achievable with cheating, as long as it is the right kind of cheating. There are multiple yellow & red CF accounts that got boosted by strong contestants. While some of that is "I did it for a friend" or "Now somebody can show off and feel good about it", in a lot of cases this is done with the sole intention of putting boosted account on CV and getting interview calls for that.

If companies would actually interview each person instead of choosing by ranks on CF

It is likely infeasible, because it is way too expensive, so they have to use some proxy methods — judge based on university you graduated from, previous work experience you have on your CV, you competitive programming results, papers you published, open source contribution, whatever other methods they have. It is true that such methods are unfair to people who are left out, but they help filtering the pool of candidates down to the ones who are much more likely to be valuable&skilled enough. As a result cost of hiring goes down, because you waste much less resources on candidates who aren't going to make it.

"I'm trying to solve as many problems as I can" is a good approach.

"In order to solve as many problems as I can, I'm intentionally picking trivial problems that don't teach me anything new" is a bad one.

Honestly, I don't know. I think CP contest would be a bad idea; but it is not like I have some much better solution in mind.

I've already interviewed quite a lot of people, and I should say that in some cases I get much better impression about somebody who has zero competitive programming experience and very low chance to do well in a competition of such format — compared to some random dude with 1900 CF rating who can really only solve competitive programming problems they memorized, and don't even have a clue about how to apply algorithms they know to something that isn't competitive programming, leave aside using common sense and those abstract "problem solving" skills that you are trying to test by CP. In other words, I can recall many examples where somebody who would've been discarded by CP test looked like much more bright & clever person than somebody who's already well above average at stuff like CP or LeetCode. I think this is precisely why large companies have huge number of different recruiting channels working in parallel — because limiting it to a single one, like "they should do well in CP" or "they should be from great university" or "they should have awesome GitHub", would leave too many valuable candidates outside.

To be fair, even if "excitement" is not the best word there, your comment doesn't really challenge underlying idea. You were unhappy at the moments where you were not "living your present with excitement" (due to losing). The point is precisely about enjoying something about the process in a way that doesn't make you rely on having CF rating increase or win in an online game in order to be happy or excited. Nowadays there are multiple things that I'm doing on my free time such that I'm quite bad at them (including competitive programming), and I enjoy them a lot precisely because I don't care about the fact that I'm quite bad there.

The smart thing to do is to test all candidates based on something common they have. That common skill is logical thinking and problem solving skill.

I think it is far from true to say that such events (FHC, GCJ, GKS etc.) are testing some abstract generic "logical thinking and problem solving skills". Generalizing it this far is like saying that playing snooker is testing not your snooker playing skills, but your general fitness conditions.

It is also not true that they test "all candidates based on something common". It is simply used as one of many ways to find candidates who have high probability to be sufficiently skilled, because apparently there is sufficient correlation between expected value of the candidate and their good performance in such competition.

If things were the way you described, the companies would've stopped to waste their resources on other recruiting channels. Moreover, they probably would've taken another step and stopped wasting massive amount of resources on interviews. Let's simply substitute them with automated tests similar to competitive programming.

In reality, majority of engineers at companies like Google or Facebook don't have competitive programming experience. A lot of them don't even know what competitive programming is.

So essentially you are claiming that all the other physical factors are genetic, but human brain either functions outside of the physical world, or is exactly the same (size, structure, whatever) for everyone / has exactly the same plasticity and general adaptation capability for everyone. That's an interesting perspective :)

Myelination(the process by which brain insulates neural pathways to improve cognitive function) is a complicated, tedious and slow process but it surely exists in everyone.

Capillary growth and muscle growth are also complicated, just like pretty much any other biological process, and we can also say that they exist in everyone, yet you claimed above that for them talent is something that matters.

My emotions during the round:

• Good news: I can still solve it with relative ease, so I'm not too rusty for div2 A yet.
• Bad news: I'm trying hard yet I can't figure out simple solution here, so I'm already too rusty for div2 A intended solutions.

The first problem is that you are counting same pairs of numbers multiple times. For example, any way to select two numbers with 4 bits in their OR will be counted 7 times — once for every possible choice of the 5th enabled bit. Inclusion–exclusion principle is our friend here in case we want more accurate estimate.

The second issue is that you are allowing using the same number twice, which is also skewing things a bit — although not nearly as much as the first part. There are 22 ways to select 2 numbers with 1 bit in OR, and half of them are about selecting the same number twice — but luckily this is not making much difference as you move to more bits enabled.

It all has been answered in other comments already, and I have just a small thing to add:

I mean how can you leave competitive programming when you are so good at?

Contestants who are at the level that you described often tend to have a bit different view on what is "good" in competitive programming.

Maybe somebody can take a bunch of past rounds and analyze them with different values of upper and lower caps to see the actual effect?

I think the idea of Div4 is not bad, it is just that there is no good way to fit it into the existing framework without ugly side effects, and the way it has been implemented isn't even the "least bad" one.

What exactly is wrong with Div4? One way to look at it is "Somewhat easier div3", where the "somewhat easier" part justifies "somewhat lower rated bound". It is not like everyone is solving everything in div3. Maybe the naming isn't perfect, but on a high level I see nothing wrong with setters being like "We estimate that our contest is too easy for participants with rating X or above, so it is unrated for them".

I recall how in the past it wasn't unheard of to have your TopCoder rating increased after scoring 0 :)

While the situation that you described may not sound right intuitively, I don't see a good solution that wouldn't add unnecessary complexity to the system.

Talk to your future manager, they'll know better. Random suggestions from online strangers being like "learn this and that" have a high chance to cover something completely unrelated and useless for your future role and project.

You are definitely not expected to start working before your first day. Depending on the perspective, "Learn frameworks X and Y, and languages A, B, C" may be considered part of your job. Most likely there will be not much you can learn in advance, as you won't have access to internal stack and tooling — but this depends on what team you are on.

It is OK for people joining at L3 to have little clue at the beginning. I was in a situation similar to yours — not working anywhere prior to Google, and not doing any projects or stuff like that on my own. It is all good, and it will be made clear to you from the very first day that it is all good. If you want to work on anything, you may look into things related to self-esteem issues, your insecurities etc. You probably don't want to deal with impostor syndrome, and I guess there is such risk in case you are already asking questions like this before you even started to work.

Solution to your problem: your rating is a random number on random site, and pretty much nobody cares about it.

At the same time you care about it too much — this is what you need to solve, not the problem of how to increase the number.

If your goal is to become better competitive programmer, you should see that rating as a lousy indicator of your performance, not as a single key metric that you need to gamble somehow, e.g. by only participating in contests that you are already good at, which sounds like an opposite of how to actually improve.

If you goal is to have fun and get the most enjoyment from the time you put into competitive programming, dealing with some stuff that upsets you every second round is not a great way to maximize the enjoyment either.

That sounds like yet another counterproductive workaround for "I care about my rating too much" problem.

What you are suggesting is to take an action that is going to lead to a worse performance (not using standings to get information that helps you to solve problems), while ignoring the underlying issue of being worried about random number on random site.

High level approach: solve it the same as any other problem, except that when you want to discard any idea because it is not going to solve some of the tests, you should first think about what are the properties of the tests that break your idea, and how likely are they to be generated randomly.

You may look around and find some problems of this kind for practice, so that you'll learn the most common observations about random tests (e.g. "randomly generated permutation will have relatively short LIS" or "randomly generated tree will have relatively small depth").

I know quite a few people who went to their last ICPC World Finals with "I'm so glad I can finally stop training afterwards" mindset. I wonder how they are going to feel about this great opportunity to improve their skills for another year :)

Maybe they are planning to follow up on every 2h virtual contest with additional 4 hours of upsolving on the same day, it should be all good then :)

Could you maybe share the code/formulas as well?

Unlike things like cheating detection algorithms, it doesn't seem to be something that could be abused.

I guess it will be beneficial both for answering all kinds of "how does it work?" questions and for getting input from participants about potential improvements.

Reading actual real life scenarios that inspired specific problem is great. I'm totally fine with it, and it is often even interesting to know where the problem comes from or what stays behind it.

Reading random "Little Johnny got an array as a present for his birthday" crap is a totally different story.

Yeah, it took me some years of practice to achieve such outcome with deterministic solution :)

You're saying "let's check the element that is closest to the middle point", and then you are making an assumption that the closest element will always be on the "higher" side.

See 76904729. Further simplifying it by removing unnecessary code duplication: 76904943.

In some cases blindly looking for counterexamples isn't unreasonable idea. You may stress test the solution and figure out what's wrong with your logic by looking at counterexample that breaks it.

Sometimes it comes as a surprise when random greedy garbage turns out being correct solution :)

What you are doing in the code doesn't match your description of the algorithm. Just in case: lower_bound gives you the first element that is larger or equal, upper_bound gives you the first element that is strictly larger. You don't have any handling for the "the last element that is smaller or equal" part.

Sorry for confusion, I was replying to the comment by Um_nik regarding him being upset, but the reply thread there is so long that it is not obvious at first glance :)

I don't have any issues with what you are doing :) And it is not like I care much.

I'd say it may even be good if you actually manage to generate entertaining content related to competitive programming, and help developing community this way.

I would have a different opinion about it if you were using this hype to exploit gullible folks, e.g. by selling some crappy "How to become red" tutorials for $$$, but as long as you are only doing harmless stuff — keep it up. And if somebody is finding your videos useful — again, this is a good sign.

One of the major benefits that you get there is observing how people actually solve problems.

It is not something that is typically covered in editorials and online discussions. And even when people solve some practice problems on live stream, they are often doing it significantly differently from how they behave in actual contest.

There are lots and lots of various small things, like how people read statement and samples, what tests they use, how they debug their code, what they do after WA, how they write stress-tests, and so on. You can come up with all of that by yourself, but it is often more time-consuming than learning from others.

Obviously if you are watching the video mainly for entertainment purposes, you don't really care about it. When I'm watching sports events, I'm usually not thinking about how to get better at particular sport :)

Also, like we both agree here, for beginners it is often not something to worry about too much, as they have more important pieces to figure out first.

How would you life become any different once your videos start getting 200k views?

It doesn't sound like you are planning to do it for living.

Most likely it will only make you deal with more "Sir how can I become red" comments and messages, which is probably not what you are looking for.

Or do you see these views as a proxy of people being able to distinguish high quality content from low quality content?

Most people watching competitive programming videos are doing that for reasons other than actually trying to develop their skills.

Because screencasts are neither interesting nor educational.

They are both interesting and educational, but only for a relatively small set of participants.

If you take the most recent div3 round with 25k+ participants, it is not only true that most of them will pick "How to become red?" video that tells them to practice over some random boring screencast, it is also true that most of them will benefit more from "Go practice" video.

I think there is some sort of balance point in the middle. Both extremes are less than perfect. On the one hand, being top 100 in the world right now is likely harder than it was 10 years ago, because there are more people doing it more seriously and over longer time span. On the other hand, being in top 1% in the world is likely easier now, because "I've been told that I need to do this to get a job" / "I will try this out of curiosity now when there are so many cool sites with cool competitions" kind of growth is likely even faster than the growth in number of people who take it seriously.

Both these statements can be proven.

That's what I'm always saying when I can't figure out any nice way to prove it :)

It is not obvious to me if red_users/all_users is in fact the right metric to go for.

If I ask my grandma to register at Codeforces, will it make my skills more impressive?

Random boring comment: while this $$$O(n^{1/3})$$$ bound may be reasonable in practice for given constraints, it is worth keeping in mind that the function we are talking about is subpolinomial: see wiki.

So it is a bit like saying "We implemented $$$n^2$$$ here, optimized it with bitsets to $$$\frac{n^2}{32}$$$, and since $$$n=1000$$$, our solution is $$$O(n\sqrt{n})$$$"

Solve for each bit separately, multiply results.

To solve for one bit, I did a linear DP setting 0s from left to right and counting ways to do so.

Essentially you only have two restrictions to deal with:

• First of all, for given position P you can't put 0 there if it is a part of some 1-segment.
• In case you decide to put 0 there, the previous 0 can't be too far to the left so you don't have some 0-segment being completely between those two 0s.

Take 4 people who cooperate and parallelize work by first solving harder problems as a team (if necessary) and then coding on 4 machines in parallel and submitting everything under the same account.

This way you can get result in top-X with zero people who have top-X skill level involved.

The real lesson would've been to not have this covered by pretests.

Thanks for the interesting stats!

Out of curiosity: what countries are in the lead by YOY growth?

Most people don't really see much difference between interview questions and competitive programming problems, as it is all about some fancy smart algorithms and CS stuff, so they believe that it is all the same and CP is actually optimal way of preparation.

Yet it is also true that doing CP does improve your interview performance as a side effect.

And some companies seem to be doing online tests as a cheap way of initial screening — they ask you to solve something at HackerEarth or HackerRank, and that stuff may indeed be typical entry level competitive programming (e.g. because re-using existing competitive programming problems is cheap). CP will be a good preparation to an online test that is about doing CP :) This "hiring tests" thing is so common that you can see multiple stackoverflow/quora/cf questions like "how do I perform well in Codeforces tests", because people just call all contests "tests" afterwards.

Additional note on top of default (and correct, I believe) "practice" suggestion: keep in mind that most top contestants have significant ICPC experience, and even a single season of reasonable preparation could potentially mean 100 or more team contests.

I would say it is much more standard: one may skip problem statement and only read constraints, and that would be enough to guess that we are asked to do some sqrt decomposition.

Both D and E are in ad hoc land :) I wouldn't go as far as saying that they are harder than F, but they are much less standard to me.

I wonder if there is a way to prove that they are always going to work by demonstrating some nice lower bound on success probability; alternatively, what would be the test to break random_shuffle.

(I also tried my best thinking about holes and pigeons, but didn't succeed on recalling how this one is supposed to be solved, so I ended up doing random shuffle too)

I would expect that specific problem from SO to be known to most of div1 contestants.

However, I would say there is a long way to go from that problem to solving and proving div1 B.

I somewhat fit this profile, though in my case a bunch of things are still different.

I stopped doing any kind of structured training in May 2017, around the time I finished participating in ICPC. Unsurprisingly competitive programming works similarly to other sports/skills, and you are getting "rusty, slow and dumb" if you decide to stop practicing. Here are some random thoughts:

you are really good in understanding the head of your partners in code and can fix their bugs by just clearing their heads and helping them out.

I've never observed this; I'm clearly worse at software engineering than people with significantly more software engineering experience. I don't see how competitive programming skills are useful for software development, and I don't see how you can magically get software development skills without doing software development.

But that's just you lowering the bar and getting used to the software development life unconsciously.

I haven't observed this either; I find most of my day-to-day job really challenging; it can't be directly compared to competitive programming, but still — I may be dealing with some problem for months only to eventually prove that it is not solvable. You don't have stuff like this in competitive programming. My first thought on this line was "well, you should find a better job then".

And that's normal, the software industry is more focused on developing a scalable, fast and reliable product instead of targeting a new problem every day.

Similarly to what I said above, I'm somehow managing to get more than enough challenging interesting problems to deal with while doing my everyday job. Of course, they are usually not like theoretic CS kind of problems, but that doesn't matter here.

But your heart is the same, right? The competitive flame inside you is still burning.

Today I'm a different person than I was in 2017. And even more different than I was during my first World Finals in 2015. And even more different than I was back when I registered at this site ~9 years ago. Competitive programming memories and experience will always be there, but maturing/evolving/changing is a natural process.

You want to still be able to solve those questions with the same (or maybe close to) speed of thought as you once had.

Do I? I understand that in order to maintain that skill I need to constantly invest time into it, and I will naturally get worse without it. It is my choice to spend that time on something else that I want/enjoy more.

And fitting practice time as we did in the past is totally impracticable. You just don't have the time for it.

Again, as I said above — I do have time for it. It is my choice to use that time for something else. I would be able to change my routine in such a way that I regularly get 20+ hours of practice per week. I would likely get better at competitive programming by doing so. But I would also get much less happy about my life.

please share your everyday habits on how to still practice and maintain your sharpness from competitive days

I'm not trying to maintain my sharpness. I prefer optimizing enjoyment rather than performance. I solve random problems online once in a while, I participate in some competitions here and there, I take part in internal rounds of Google events (Code Jam, Kick Start etc.), I'm back to taking part in some OpenCup rounds this year, I read various discussions and editorials. I'm still doing something related to competitive programming every week. This is actually even better experience now — I have enough knowledge and experience to be able to enjoy nice ideas and tricks, I also enjoy the process itself, and at the same time I don't have any pressure on me regarding the performance — it doesn't upset you when you perform poorly in case you didn't expert to perform well anyway; I also have a clear understanding that my performance and my skills have little value — they don't really change anything in my life; my income, my health or health of people around me don't depend on my CF rating. Most of my coworkers don't even know what competitive programming is :) Yes, it is one of many random hobbies adults have. Great way to spend time for sure.

How these habits changed your work code?

I don't think they changed my work code in any significant way, as it is clear to me that my work code is totally different from competitive programming code, and it has different purpose and different expectations. Back when I was an intern I had a great experience when I optimized one small piece using random idea from competitive programming — I've been told that I should use slower version instead, because we cared about code health and not about code performance. That was a really good insight, and I can't really recall having any CP-related situations for code at my day-to-day job.

Back in a day TopCoder was the most popular platform in the world, and they had events that were <2 hours long, with ony 75 minutes were for coding. People were fine with that :)

Thanks for sharing your thoughts and opinions; after reading your blog I got an impression that what you basically did was saying "I prefer 3h contests over 2h contests", without proper reasoning on why it would objectively be better.

I personally like 2h contests more; I'm not going to try to prove that they are "better" either :) But for me the main drawback is about ensuring that I have time for 3h contest, which is much harder than doing same for 2h contest. For similar reasons I haven't done any long contests in a while — even though they provide sufficient flexibility, I'm not nearly as serious about competitive programming as I'd have to be in order to find sufficient amount of time.

Maybe it is possible to make everyone happy by having some contests that are shorter and some contests that are slightly longer :)

Random rant from my side: I am not happy at all when contest organizers can't figure out contest duration; like when you have different numbers in upcoming contests and in the announcement because the announcement was mistakenly copied from a previous round, or when AtCoder admins decide on round duration in the morning before the contest...

They aren't self made as "they never get any help from others". Typical strong contestant regularly interacts with other contestants, likely attends some training camps etc., probably has ICPC teammates to learn from, and so on.

They are self made as "they have to work on building their skills". From this perspective the statement is right, as you aren't going to get far with the approach like "Please give me exact list of problems to solve, ordered, and also exact list of algorithms to learn, and also explain all that stuff to me as well since figuring it out by myself is hard".

I don't think you necessarily did something wrong or bad, and what you did during your first year shouldn't be the main motivation for your choices on what to do later on.

And "I am not good/meant for CP" stuff is just harmful attitude in general.

Well, the biggest problem I have is that I'm not good at math, also I'm not gifted and I don't think I have any features.

This always works handy as an excuse. It is very reassuring to think that people doing well in competitive programming are doing well because they have talent or gift or whatever.

Can I read about it somewhere in more detail? I'm now curious, because my knowledge matches what never_giveup said — there are no such schools in my region (Ukraine, Russia, Poland etc.), unless we have very different views on what "intense and systematical training" means (based on how strong Chinese contestants are, I wouldn't think so).

While I agree with the overall idea of the comment above, I should add that the context I'm mentioned there is highly misleading: I've never done consistent training/preparation at the "15+ hours per day" level, and I don't even think it is sustainable. Moreover, trying to do something like that would most likely be counterproductive, and dangerous to your physical and mental health.

I do believe that I would've performed significantly better if I've practiced more :)

So that if one wants to move to a higher rank, all they need to do is to bring sufficient number of new contestants to Codeforces? ;)

There is generally an effort on ensuring that leaked questions aren't used, and "The most popular interview preparation platform in the world says that this question is used at Google" is a strong enough signal to ban the problem.

It's not like everything works 100% perfectly... But generally you should expect that questions marked as "Google interview questions" around the Internet are unlikely to actually be asked during your interview. Though I still think it is a good idea to practice them, to get the skills and knowledge which you can then apply to (a different) question during the real interview.

Do you see better scoring solution under assumption that subtasks are there?

I agree that it sounds questionable when you look at it from this perspective, but it all kinda makes sense. Proper solution gives you E1+E2, for which 3000 is reasonable. During the contest I spent 25-30 minutes thinking on E2 before abandoning it — and the case work that I had at that point was more complicated and messy than the editorial.

Yes, E1 is straightforward coding which requires even less thinking than D — but it is, by div2 standard, quite a lot of tedious coding. I don't think it would be fair to say that 58306483 is worth less than solving D. Is it really that wrong to look at it like "either you just code the trivial part and get 2000 for it, or you solve a full problem for 3000"?