| # | User | Rating |
|---|---|---|
| 1 | jiangly | 3810 |
| 2 | Benq | 3676 |
| 3 | Kevin114514 | 3655 |
| 4 | maroonrk | 3463 |
| 5 | strapple | 3447 |
| 6 | Um_nik | 3387 |
| 7 | heuristica | 3322 |
| 8 | turmax | 3317 |
| 9 | tourist | 3307 |
| 10 | jiangbowen | 3291 |
| # | User | Contrib. |
|---|---|---|
| 1 | Qingyu | 156 |
| 2 | nik_exists | 150 |
| 2 | maspy | 150 |
| 4 | Um_nik | 142 |
| 5 | Errichto | 139 |
| 6 | adamant | 137 |
| 7 | AmShZ | 135 |
| 8 | BledDest | 132 |
| 8 | maroonrk | 132 |
| 10 | qwexd | 129 |
Good morning everyone! Errichto and I each just released new videos in which we discuss some cool problems:
On his channel, we discuss a very neat problem which he wrote called Parades
On mine, we talk about the 2006 IOI problem Joining Points, which has a quite beautiful solution, as well as the more general version of it
Please check them out and let us know what you think. More will be coming soon!
Episode 8 of Algorithms Thread comes out in <90 minutes! This one is a bit more beginner-friendly and covers the following ideas:
Also, to make sure you have actually learned that stuff, I made a custom Gym set on CodeForces that will last two weeks that hopefully is really good practice for making sure you have learned this stuff. Here is a link to the gym set; it will be available 45 minutes after the video comes out so that people have time to watch the video before starting the set, if they are interested in penalty points. All of the problems in the gym are original to this set (in their flavortext at least, some are simple enough that I'm sure they have appeared in other contests before).
The new gym integration was heavily inspired by Errichto's Matrix Expo set format. Let me know whether it's helpful. I think it might be, but also it's a pretty big time commitment to make it, so whether I keep doing them depends on how helpful they are to people.
If you have any questions or suggestions, feel free to leave them below. I hope you enjoy the problem statements, and I'll leave you all with this:
Update:
Announcement of AlgorithmsThread Tree Basics Contest
Hi everyone!
TLDR: Speedrunnable contest here, bad solution videos + original standings here.
Last week I learned how to use Polygon, so I uploaded and regenerated data/solutions to the first contest I ever wrote, and uploaded it to the gym. The final score of the original contest is available here. In the original contest, the last problem was only unlocked after solving everything else (which no teams did). Originally this was a set for high school students in Wiscosin, but I thought some people here might enjoy speedrunning it.
Solution videos are also available here. They aren't very good because I was a young child when I made them, but they should at least convey the main ideas pretty well. The one interesting thing to mention is:
For problem LAST Robotics:
I hope you enjoy! Let me know if there are any technical issues, because those may indicate that I've set something up incorrectly, which was kind of the main thing I was trying to avoid here.
Announcement of Brookfield Computer Programming Challenge 1
TLDR: Stream at this time! See you there!
Hi everyone! I very recently reached 1<<12 subscribers on Youtube! To celebrate, I'm going to be doing my first ever livestream! I'll be on Youtube only this time (maybe I'll do both youtube and twitch later if there's demand for it). The stream will include looking at and trying to solve Code Jam Finals problems, which will be going on at the same time. In general, live-streaming participation in a contest is considered cheating and is very bad. Do not do this for any public contests!
To be careful not to leak solutions or anything:
That way, this isn't any more revealing than the ICPC NAC Livestreams which present solution sketches to easy and medium problems on the stream and expect the small number of participants to be honorable. Besides, if a finalist actually wanted to be a bad sport, there are much better ways than trying to get some tiny amount of info from me. (I won't give ideas here, but I'm sure you can think of some)
Cool, hopefully I'm morally redeemed! I'll also be doing some other stuff, unrelated to Code-jam, like upsolving problems from the Div2, answering random questions if people have them, and maybe even setting up some stuff for a super-cool open source project that I know Codeforces will be hyped about!
I'll start streaming at whatever this time is for you on my Youtube channel SecondThread. Hope to see some of you there!
Update: Tech check went well, see everyone soon!
Recently there have been an obscene number of unrated accounts showing up. Several of them have inappropriate names, so I won't give examples because I want to keep this post clean, but I'm sure you have seen them in the comments. They are likely all by the same individual, possibly with a few copy-cat troublemakers as well.
Recently, certain ones have begun to spam useless comments on old posts to clog up the recent actions, effectively hiding all relevant conversations except on the blog posts they spam on. For whatever reason, these are overwhelmingly on Errichto's old blog posts. Occasionally there are also a flood of obscene blog posts made by the user themselves.
Here's an example of what I mean: 
The current solution clearly doesn't work. As soon as they get banned or muted or whatever, they can just make another throw-away account and continue spamming tomorrow.
A slightly less extreme problem is that lots of new users have created alt accounts in order to ask fairly meaningless 'How do I get better', 'please solve this problem for me', et cetera type of questions.
Make it so that users who haven't competed in any contests don't have permissions to post blogs or comments. At the very least, this should deter a lot of these fake accounts from being created.
I know there are a few accounts used by companies/media which are used for public announcements, for instance: NercNews. In cases like this, if it is actually a legitimate news source, we can 'trust' these users with the GM 'trust this user' feature. As far as I know, there aren't really that many accounts like this that are run by large companies/media organizations. I think each of them should be able to find at least one GM who is either a part of the organization or can verify that the organization is trustworthy enough to not intentionally spam Codeforces.
Do you agree? If so, can you please tag some people who would have the ability to fix this so that this post actually gets noticed within the haystack of worthless spam?
Hi everyone! I just published Episode 7 of AlgorithmsThread, which talks about processing all pairs of points, while keeping the rest of the points sorted in a helpful way. I talk about the following problems in it:
I find this to be a really helpful trick that isn't super well known, so feel free to check it out if any of these sound like things you want to learn!
Feel free to post any questions below!
Recently I have noticed several of my comments end up deleted. I don't think my comments were unhelpful, spammy, or otherwise something that shouldn't be seen. In fact, I'm quite confident that the reason they aren't there anymore is because the are children in the reply tree to some comment that was deleted earlier up the chain (and it was that comment that was unhelpful or could otherwise be deemed inappropriate).
Here are two examples:
This comment was a reply to someone thanking me for making a video. The comment it was in reply to was also deleted. I suppose that comment didn't add anything to the discussion.
This comment was on why CF rounds need to have problems that are shorter to code compared to IOI. I think it was deleted because it was part of a blog written by rotavirus that was somehow deleted, which is apparently a running theme.
There are some other examples as well of similar nature.
Who is making these decisions, and on what criteria? To me it isn't obvious. Are there just some special users who have the ability to delete other people's stuff? Is that an IGM/LGM privilege that I just haven't earned yet? Is Mike manually deleting rows in some SQL database every time this happens?
In lots of these cases, I remember interesting and valid things being said by myself and others that are no longer visible. Is it intentional to delete the entire subtree of comments rather than just the egregious one(s)? I suppose for the case of deleting blogs it may be a different story; I can imagine technical difficulties that would arise when trying to hide a blog, but not its comments. But what about comment subtrees?
Hi everyone! I just released Episode 6 of AlgorithmsThread (now rebranded from Algorithms Dead after frodakcin's epic suggestion).
In it, I talk about:
I hope you enjoy. Feel free to ask questions below, as usual :)
Hello everyone! I just uploaded Episode 5 of Algorithms Dead in which I talk about persistent data structures. I talk about the ASC problem involving a persistent queue, describe how persistent segment trees work, and provide some interesting problems that can be solved and then optimized with persistent segment trees.
Some problems discussed in this video if you are interested in solving them yourself:
Harder PST problems (not covered in the episode but good practice):
Let me know if you have any questions of suggestions for how I can improve the series!
Want an easy-to-use tool to notify you when you get a problem correct? Looking for an inspirational jingle to celebrate when you AC? Wish you could just move on to problem B immediately after submitting A and had someone to let you know in case you got it wrong? Now you can!
CFNotifications.com is a simple website that does this for you. All you have to do is type in your handle and click login.
It works on all CF rounds, and also other submissions if you are upsolving, practicing, or running a VP on your own. Personally, I just leave it on a second computer with the volume turned up and then I don't have to worry about it ever.
It rechecks Codeforces every 4 seconds for new submissions, or every 1 second if you have a submission that is judging. It uses the CF API and I did my best to make sure it is as low-impact to the servers as possible while still giving results pretty much instantly.
Let me know what you think!
Per request, I added the ability to play a custom sound on AC (or play no sound at all). The changes are live now, so you should be able to see, but basically now you can enter 'none' if you just want the notification that you got the problem right and no 'distracting' inspirational sound effect, or something like 'https://www.youtube.com/watch?v=dZLfasMPOU4' if you want to hear 3 minutes of Stacy's Mom every time you solve a problem!
I also made it save your handle (and the custom sound if you choose to use one) as a cookie, so it should be even easier to use. If you have been there before, everything will auto-fill so you can literally just click the button and it's working.
Segment Tree Beats are a really cool, and fairly advanced, modification you can make to segment trees in order to handle range-min-with queries. I talk about what they are and why they work in Episode 4 of AlgorithmsThread.
Feel free to comment any questions about what I covered in the comments of this blog, and I'll answer them as soon as I get a chance to.
The original CF blog post about ST Beats posted by jiry_2 is very good, although it took me quite a while to fully understand.
Errichto also has a video on ST Beats that he made a while ago on his second channel.
It would be really nice to be able to see past CF contests in the Contests tab. Usually they show up below the upcoming contests, but since the ICPC Practice is running for like 2 days straight, we can't see them.
For me it is just an annoying inconvenience because I can get there through my submission history. But if I wanted to VP a previous round for instance, there isn't really a good way of doing that without a link (or if there is a good way, I don't think it is very clear what that way is).
For long contests (ICPC Challenge, Microsoft Q#..., et cetera), it would be nice to still be able to see old contests in the contests list. I can understand if it would be too much of a server load for CF rounds, but these contests likely have much lower participation and are less demanding.
Hi everyone, I just made Episode 3 of AlgorithmsThread. This one is a bit easier than usual and covers Segment Trees. At the end of the video, I talk about an interesting and difficult Segment Tree problem called Sneetches, that might be worth reviewing if you already know your segment trees quite well.
This video is a bit easier because the next two will be about some hard segment tree topics, and this should help prevent people who don't know segment trees yet from getting completely lost.
If you have any questions on stuff I covered, the comments below is a great place for them!
Round 654 Problem F, which uses a very similar idea, in case you want a good practice problem.
Episode 2 of Algorithms Dead is out now! In it, I talk about:
If you're new to these ideas, or looking for a refresher, it might be worth checking out. If you have questions, feel free to post them below instead of DMing me, so that other people with the same questions can see the answers.
brunomont and tfg showed me their fantastic (and recently published) blog post here: https://codeforces.me/blog/entry/78931. This didn't influence this episode or anything (my stuff was based on jcg's comment on this post from 7 months ago), but brunomont does a great job benchmarking this against segtrees, so definitely go upvote his post for his hard work!
Do you blindly do operations under mod without knowing why they work? Does it scare you when a problem asks you do print something mod a big number? If so, you should watch Episode 1 of Algorithms Dead!
In it, I talk about why mod operations (addition/subtraction/multiplication) are allowed, why mod inverses work, and what things are safe to do when you store fractions as $$$p*q^{-1}$$$.
Episode 0 of Algorithms Dead is out now! It covers the Hungarian algorithm and how to do dijkstra's in just v^2 instead of e*log(e). Usually e*log(e) is fine, but v^2 is obviously faster on a complete or nearly-complete graph.
Other than recording where my mouse is so you can see what I am pointing to, if you have any suggestions for the future, feel free to let me know!
Currently on codeforces comments, you can see whether you up/downvoted by looking at the up/down arrows next to the comment rating. If you upvoted the comment, the up arrow will be green, and if you downvoted it, the down arrow will be red.
However, for blog posts, the only way to tell is to try to vote a second time and see if an error toast appears at the bottom of your screen. A side effect of this is that you can’t ever undo a vote for a blog post or change it from a downvote to an upvote, for instance, even though you can do these things for comments.
Is there any reason for this behavior? It seems to me like being able to see what you voted for and change your vote if you like is much better than the blog post system. If there isn’t any reason for it, would it be difficult to change the blog system to match the comment system?
There are two common meanings for something being “guaranteed”, and often it is up to the reader to guess the author’s intended meaning. This is annoying and creates unnecessary barriers to entry.
Meaning #1: The thing we are guaranteeing is provably true for the given input. The thing we are guaranteeing is simply true. We don’t want to provide a proof since it would be long, unnecessary, and annoying to read, and might spoil the solution, but you have our word that an answer always exists.
Example: We give you two positive integers A and B (1 <= A, B <= 100). Find some positive integer C (1 <= C <= 200) such that C < A + B. It is guaranteed that some C exists.
Meaning #2: The only input that is legal is input for which this is true. The thing we are guaranteeing might not always be true without this guarantee. Thankfully, we are providing this guarantee so that you only need to concern yourself with solving the problem for inputs in which this is true.
Example: We give you two integers A and B (1<=A, B <= 100). Find some integer C such that (A-C) * (B-C) is negative. It is guaranteed that some C exists.
Examples where 'guarenteed' means that “It can be proven that for all inputs following the constraints, X”
Code Jam 2020 Round 1A, problem B
Codeforces round 633 Div1B (it's clear what the author meant, but still this type of usage)
Examples meaning “The only inputs that are valid inputs are inputs for which X”:
Code Jam 2020 Round 2, problem B (An incorrect interpretation of this could have resulted in failing the large test set)
There are tons of guarantees in the input section for things like: all edges are distinct, the graph is a tree, the array is a permutation, the sum of array sizes across all test cases is reasonable, the total number of queries is reasonable, the input is sorted, et cetera. I didn’t include them because it is clear what they mean. The important part is that this is a completely different type of ‘guarantee’ from the first one. We shouldn't be making contestants figure out what the author means; people want to solve interesting problems, not read novels.
Meaning 1: Make it clear that the ‘guarantee’ is just to make the problem more understandable, not an additional constraint on input.
“It can be proven that X”/“Under the given constraints, X is always true”
“Notice that some X always exists”.
In the example above: “It can be shown that some C always exists.”
Meaning 2: Make it clear that this ‘guarantee’ is an additional constraint on the input.
Input is only allowed if X.
In the example above: “Only input for which some C exists is legal input.”
Just don’t provide the ‘guarantee’ at all and make it a red herring
“If no solution exists, print -1”
In the examples above: “If there is no suitable integer C in the valid range, print ‘no’ instead”
"Red herrings don’t work. 99% of the time if there isn’t an impossible case in samples, and the impossible case isn’t super obvious like n=1, then an impossible case just doesn’t exist.”
That’s probably true. One option is to have really weak samples to disguise that, but maybe that is undesirable for other reasons. A second option is to write more problems where there is a nontrivial impossible case, but not put it in samples so people stop thinking this way (definitely keep it in pretests though!). Even without either of these things, there are still some quite nice problems with red herrings for which the contestant proving that it is always possible is helpful. Perhaps you can make the guess that it is always possible and have a slight advantage, but finding why it is always possible is usually a nice head start on the problem too. 2019 China Collegiate Programming Contest Final Problem I is a great example of this. A red herring doesn’t have to trip people up to ‘work’ either; if it makes it clear that it is your job to figure out whether something might happen, that’s okay too.
"You just suck at reading problems. Use samples. Reread the statement. This is a skill, you have to improve it.”
Okay, Um_nik, you got me.
Problem G from Educational Round 89 is a model solution to this issue. It does an fantastic job of entirely avoiding all ambiguity and confusing guarantees. It is crystal clear that the additional constraint is an additional constraint, and it is worded in a succinct, easy to interpret way. Problem authors/coordinators orz
(My reaction to first reading this problem at 54:13 is pretty funny and might cheer you up if you wrote the problem)
I just created a cool CF tool called LGM Sniper. It looks at scoreboard data from every Div1 and Div1+Div2 round ever and tells you which LGM's you have beaten, how many times you have beaten them, and which rounds you beat them in. You can also compare yourself to your friends to see which one of you wins more! If you want to compare yourself with some friends, check the 'show ex-lgms' box and enter the friend you want to compare to as Handle #2, and they will show up on the bottom.
You can try it out for yourself at lgmsniper.com, or in the competative programming section of Wumbo Games, if you would prefer. Tooltips show the name of the rounds you won in (hover your mouse over the checkmark).
If you find any interesting facts or have suggestions for how I could improve the tool, let me know in the comments!
All data is stored locally on my server. So although these queries are computationally expensive you can't DDOS Codeforces to make a round unrated using this tool because it doesn't actually query Codeforces except for when I update the data, which I obviously won't do during a round. Please don't try to abuse it, you'll just make LGM Sniper slower for other people who might want to get inspired by learning that the beat an LGM and you'll annoy me.
I added a couple new features/fixes that people brought to me. Here are the ones people will likely care about most:
Let me know what you think!
Includes data from competitions up to and including Round 700 Div1/Div2.
I'm somewhat familiar with how Link Cut Trees work. I have watched Erik Demaine's lecture on them from MIT Open Courseware, solved a couple problems that use them with my team's (very copy-pasteable) book code, and read about them a bit, so I have an idea of how they work in general.
The code I have used supports range path update, path query, link, cut, and checkConnected queries. I read on Wikipedia that Euler Tour Trees are better for subtree queries and link cut trees are better for path queries. However, I looked through ko_osaga's code for fully dynamic connectivity and it looks like he is using a splay tree or link-cut tree of some sort. Link-cut trees use splay trees to store preferred paths, so the size of a splay tree node's subtree doesn't really mean anything, right? But for the dynamic connectivity problem he was trying to solve, I'm pretty sure you need to check, after cutting an edge, which of the trees you created is smaller. That sure doesn't seem like a path operation to me.
So is it possible to do subtree-like operations on LCT's?
According to Wikipedia, an RMQ can be built with $$$O(n)$$$ memory and time precomp that can answer queries in $$$O(1)$$$. The idea is to divide the array into $$$log(n)/4$$$ blocks and then build an RMQ/sparse table normally on each of the blocks using $$$O(nBlocks*log(nBlocks))$$$ time and memory. In this case, $$$nBlocks$$$ is roughly $$$n/log(n)$$$ so the memory and time used to precomp everything is linear. By doing this, we can find the min of all completely covered blocks. That part sounds easy.
The hard part is dealing with the blocks that a query starts and ends in. Wikipedia says that I need to map each block to its corresponding Cartesian tree, and then I can precompute all the answers for every Cartesian tree. I see how, if I could do that, it would be easy to answer queries in $$$O(1)$$$. As I understand it, I could just store which index for a given Cartesian tree contains the relevant min for all pairs of queries within that subarray in $$$O(blockSize^2 * nCartesianTrees)$$$.
But how do I go about quickly (and hopefully cleanly) mapping a subarray to its corresponding Cartesian tree?
Side question: Are there even performance gains to be made here, or am I just wasting my time trying to get rid of this log factor?
