AlgorithmsThread 6: Convex Hulls

Hi everyone! I just released Episode 6 of AlgorithmsThread (now rebranded from Algorithms Dead after frodakcin's epic suggestion).

In it, I talk about:

• Getting the convex hull
• Checking if a point is in a convex hull in $$$O(log(n))$$$
• Finding the farthest point in some direction in $$$O(log(n))$$$
• The problem Trash Removal with $$$O(n^3)$$$ -> $$$O(n^2)$$$ -> $$$O(n*log(n))$$$ solutions
• The more difficult problem Troop Mobilization from ICPC South East Regionals

I hope you enjoy. Feel free to ask questions below, as usual :)

AlgorithmsThread 5: Persistent Data Structures

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:

• kth min on an l-r segment on an array in log(n)

• kth min on a path in a tree in log(n)

Harder PST problems (not covered in the episode but good practice):

• Literally just dijkstra's algorithm, but weights can be absolutely massive powers of 2

Let me know if you have any questions of suggestions for how I can improve the series!

CF Notifications

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.

How it works

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!

Updates!

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

AlgorithmsThread 4: Segment Tree Beats

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.

Other Resources

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

Viewing Past Contests

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

Possible Solutions

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.

AlgorithmsThread Episode 3: Segment Trees

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!

Update: Problem Links

• Sneetches Problem Statement

• Sneetches Solutions + data

• Round 654 Problem F, which uses a very similar idea, in case you want a good practice problem.

Algorithms Dead Episode 2: RMQ Tricks

Episode 2 of Algorithms Dead is out now! In it, I talk about:

• How to find the min in a range of an array on O(1)
• How to build an RMQ in O(n)
• How to use an RMQ to find the lowest common ancestor in a tree

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.

Further Reading

brunomont and tfg showed me their fantastic (and recently published) blog post here: https://codeforces.net/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!

Algorithms Dead Episode 1: Division Under Mod

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?

Please Stop Guaranteeing Things

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 in real problems:

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 642F

Codeforces round 633 Div1B (it's clear what the author meant, but still this type of usage)

Codeforces round 628A

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)

Codeforces round 636A

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.

Alternatives:

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”

Counter Arguments:

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

Update: Examples of how to do it the right way:

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)

LGM Sniper

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!

Don't try to DDOS Codeforces Disclaimer

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.

Update: New Features

I added a couple new features/fixes that people brought to me. Here are the ones people will likely care about most:

• I added a checkbox to only show rounds that were rated in which you beat someone who was an LGM at the time you beat them. If it is checked and you still beat someone, then you definitely earned it!
• There are now round id numbers shown on the rounds that you won. This is helpful if you want to check out the scoreboard of some contest for instance.
• I updated the blacklist of excluded contests to not include practice rounds, so it should be more accurate now.

Let me know what you think!

Last Updated:

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?