ICPC World Finals 2024 is happening right now, and I’m planning to upload a vlog every day. The internet speed here is a bit questionable, so it might take some time for the videos to go up.

By the way, the first video (day 0 and 1) is already uploaded, and day 2 will be up soon. You can also check out the pictures below!

This blog will be updated.

Hello Codeforces,

ICPC WF 2024 is happening next week, and we’re heading to Kazakhstan on Friday night.

As I’ve done plenty of interviews and AMAs, but I’ve never been the one answering questions, and as tomorrow will be our final training session, we’re planning to have an AUA afterward.

Sam (sam571128), Colin (galen_colin), and I (Shayan) will be there to talk about our goals for ICPC, how we’ve been preparing lately, and answer your questions. It’s going to be fun!

Here is the link: https://www.youtube.com/watch?v=UD4plaiJ4bc

(Since it’ll be late night in the US and not an appropriate time pretty much anywhere in the world, it will be recorded as well.)

Btw, the most important question of this blog post is, what’s your favorite team in ICPC this year? (UMD White, right?)

Hello Codeforces,

It’s been a long time since we announced my interview with Reyna.

One question that always comes up is: what comes after learning and excelling in competitive programming? Is it really possible to land a well-paid job after reaching a high level in CP? In this interview, Arash tries to answer this question.

Arash owns a Gold and a Silver medal in IOI. He has also participated in a lot of onsite competitions. In this interview, he talks about his thoughts on competitive programming, his journey, and how he learned competitive programming.

Right now, Arash works as a quantitative researcher and earns more than $500,000 per year. He believes that this field is one of the most suitable fields for top competitive programmers, and having a great CP background helps a lot to land a job in the field. He talks about his job, how he got into the field, how others might land a job in this field, and how well-paid this field is. He also shares his recent investment in an AI startup.

More interestingly, Arash and I attended the same school. He was our upperclassman and later became our teacher after winning a national gold medal. We share a lot of memories together, and we talk about some funny ones in the interview!

I hope you find this interview enjoyable. You can find the trailer of the interview below.

And here is the full interview:

PS: As always, feel free to suggest who you’d like me to interview in the comments below.​

Hi,

We had a problem-solving session on graph algorithms today. I selected problems that don’t require many prerequisites and are focused on generating ideas. I hope you find it enjoyable and educational.

This video is for people from starter to expert level.

330B — Road Construction

In this problem, we use a constraint on m that helps us solve it easily.

The link to the problem: https://codeforces.me/problemset/problem/330/B

687A — NP-Hard Problem

In this problem, you’ll get familiar with the concept of a vertex cover, and we’ll apply what we’ve learned about bipartite graphs.

The link to the problem: https://codeforces.me/problemset/problem/687/A

1093D — Beautiful Graph

The idea of the previous problem helps a lot to solve this one as well.

The link to the problem: https://codeforces.me/problemset/problem/1093/D

369C — Valera and Elections

In here, we use a trick that is useful in many tree problems.

The link to the problem: https://codeforces.me/problemset/problem/369/C

429A — Xor-tree

Here, we see how to pass the state in DFS and use logical arguments and facts to solve the problem.

The link to the problem: https://codeforces.me/problemset/problem/429/A

105053E — Expanding STACKS

This is a problem we came across recently while practicing for ICPC. We’ll see how graph algorithms can be used to solve a problem that doesn’t initially seem like a graph problem.

The link to the problem: https://codeforces.me/gym/105053/problem/E

I hope this stream and the consequent ones will be helpful.

Note: The text editorials will be provided by the authors of the round. This video tutorial acts as an additional resource for those who prefer video over text, not as a substitute for the text editorial.

2009A — Minimize!

2009B — osu!mania

2009C — The Legend of Freya the Frog

2009D — Satyam and Counting

2009E — Klee's SUPER DUPER LARGE Array!!!

2009F — Firefly's Queries

2009G — Yunli's Subarray Queries

Note: The text editorials will be provided by the authors of the round. This video tutorial acts as an additional resource for those who prefer video over text, not as a substitute for the text editorial.

2007A — Dora's Set

2007B — Index and Maximum Value

2007C — Dora and C++

2007D — Iris and Game on the Tree

2007E — Iris and the Tree

2007F — Eri and Expanded Sets

Hi,

This is our second stream on Graph Algorithms, where we continued covering the basics. The next stream will be more challenging, as we’ll solve several problems from Codeforces. As mentioned earlier, in future streams, I plan to explain some of the hardest graph problems I’ve ever encountered.

If you’re already at an advanced level, this topic stream is not for you.

Bipartite Graphs

In this section, I discussed bipartite graphs: what they are, the condition for a graph to be bipartite, and how to find the two parts if a graph is bipartite.

Terminology Overview: Walk, Path, and Cycle

To continue our discussion, it’s important to familiarize ourselves with some basic terminology. Here, I define what a walk, a path, and a cycle are.

Find distances and BFS

In this section, we discuss how to find the distance between two vertices in an undirected graph. I first explain the algorithm and then reveal its name—BFS.

Solving a 1600 Difficulty BFS Problem from Codeforces

In this section, we solve a problem that’s perfect for implementing BFS:

https://codeforces.me/problemset/problem/601/A

I hope this stream and the consequent ones will be helpful. Feel free to criticize. I'll do my best to address any issues.

Hi,

We had our first topic stream on graph algorithms yesterday.

Since this was the first stream on this topic, I started with the very basics. We’ll cover more advanced topics in the upcoming streams. My goal is to eventually cover every graph algorithm from basic to advanced. In future streams, I plan to explain some of the hardest graph problems I’ve ever encountered.

If you’re already at an advanced level, the first topic stream is not for you, as I started from the very beginning to ensure that no prior knowledge is needed to follow along.

What is a Graph

In this section, I introduce what a graph is and how it can be useful. I also discuss the basic types of graphs (un/directed, un/weighted).

How to Store a Graph

The next question is how we can take a graph as input and store it. This is the first step we must take before running any algorithm on the graph.

Connectivity in Graphs and DFS

Here, I discuss the connectivity of a graph, and we solve a problem related to it. At the end, I mention that what we did is called DFS.

Solve a 1400 Difficulty Graph Problem from Codeforces

In this section, we solve a graph problem with a difficulty level of 1400 from Codeforces.

The link of the problem: https://codeforces.me/problemset/problem/505/B

I hope this stream and the consequent ones will be helpful. Feel free to criticize. I'll do my best to address any issues.

Note: The text editorials will be provided by the authors of the round. This video tutorial acts as an additional resource for those who prefer video over text, not as a substitute for the text editorial.

2001A — Make All Equal

2001B — Generate Permutation

2001C — Guess The Tree

2001D — Longest Max Min Subsequence

2001E1 — Deterministic Heap (Easy Version)

Note: The text editorials will be provided by the authors of the round. This video tutorial acts as an additional resource for those who prefer video over text, and not as a substitute for the text editorial.

2004A — Closest Point

2004B — Game with Doors

2004C — Splitting Items

2004D — Colored Portals

2004E — Not a Nim Problem

2004F — Make a Palindrome

2000A — Primary Task

2000B — Seating in a Bus

2000C — Numeric String Template

2000D — Right Left Wrong

2000E — Photoshoot for Gorillas

2000F — Color Rows and Columns

2000G — Call During the Journey

2000H — Ksyusha and the Loaded Set

I initially solved this problem for a fixed value of k (by mistake), and then generalized it for varying values of k.

2002A — Distanced Coloring

2002B — Removals Game

2002C — Black Circles

2002D1 — DFS Checker (Easy Version)

2002D2 — DFS Checker (Hard Version)

2002E — Cosmic Rays

1998A — Find K Distinct Points with Fixed Center

1998B — Minimize Equal Sum Subarrays

1998C — Perform Operations to Maximize Score

1998D — Determine Winning Islands in Race

1998E1 — Eliminating Balls With Merging (Easy Version)

1998E2 — Eliminating Balls With Merging (Hard Version)

Hi,

As always, we have topic streams on Fridays from 12-14 GMT. Today was the second topic stream on Dynamic Programming. Here are the topics covered in this livestream:

1. The idea of updating dp in two directions (Sending a Sequence Over the Network)
2. Keeping our states for matching subsequences (Easy Problem)
3. Importance of ordering in updating DP (Gargari and Permutations)
4. Keeping max values to optimize DP (Choosing Balls)
5. Memory optimization and moving in two directions (Pigs and Palindromes)

I will write the highlights of the livestream here, embedding specific parts of the videos so you can easily watch the sections you’re interested in. You can ask questions about any part here, on YouTube, or in our Telegram Channel. The main discussion thread is in our Telegram Channel.

Updating DP in two directions

In DP problems, sometimes we calculate dp[i] when we reach i by using smaller instances (j < i). Other times, when we reach i, we assume that we already have dp[i] and update the larger instances (j > i). In some cases, we can do both simultaneously.

Sending a Sequence Over the Network

Keeping our states for matching subsequences

In this problem, we want to remove certain characters to ensure that the string "hard" does not appear as a subsequence in our string. We explore how to maintain states that track how many characters of "hard" have already been matched and how this helps us solve the problem efficiently.

Easy Problem

Importance of ordering in updating DP

In this problem, we see how the order of calculating DP values can be important and how to find the right ordering.

Gargari and Permutations

Keeping max values to optimize DP

In this problem, we first come up with an O(n^2) DP solution. Then we optimize it by keeping track of the two maximum DP values. This way, we can update dp[i] in O(1) instead of O(n).

Choosing Balls

Memory optimization and moving in two directions

Here, in addition to the idea of considering the diagonals of a grid and maintaining our states, we see how we can optimize memory by taking one of the dimensions modulo 2.

Pigs and Palindromes

Let me know your opinions! Together we can make the livestreams better.

1999A — A+B Again?

1999B — Card Game

1999C — Showering

1999D — Slavic's Exam

1999E — Triple Operation

1999F — Expected Median

1999G1 — Ruler (easy version)

1999G2 — Ruler (hard version)

1993A — Question Marks

1993B — Parity and Sum

1993C — Light Switches

1993D — Med-imize

1993E — Xor-Grid Problem

Hi,

Today, I had my first topic stream on Dynamic Programming. The stream lasted for two hours, and this was the plan for the first livestream:

1. Start with the basics of Dynamic Programming: the logic behind it and when to apply it.
2. Boredom — difficulty 1500
3. Consecutive Subsequence — difficulty 1700
4. Red-Green Tower — difficulty 2000
5. Winter is here — difficulty 2200

I will write the highlights of the livestream here, while embedding the specific parts of the videos so that you can easily watch the parts you want. You can ask questions about any part here, on YouTube, or in our Telegram Channel. The main discussion thread is in our Telegram Channel.

The Basics of Dynamic Programming

In this part, I talk about what Dynamic Programming is and why we might want to use it. I explain how to figure out if we can apply DP to a problem. Of course, as an example, I discuss the Fibonacci sequence—who doesn’t use Fibonacci when explaining DP? I tried to skip unnecessary details and keep the focus on the most important points.

455A — Boredom

This problem helps to build intuition on how DP works. It’s an example of defining states and solving the main problem using those states. In this case, we define dp[i] as the answer when considering only the numbers from 1 to i and ignoring the rest.

977F — Consecutive Subsequence

This is another problem that helps with the idea of defining subproblems as the different cases that contribute to our final answer. Here, we define dp[i] as the answer if the last chosen number in our subsequence is i.

478D — Red-Green Towers

This problem combines a greedy algorithm to find the best value for h and defines subproblems like (i, j). This states how many ways we can have a pyramid of height i using j red blocks.

839D — Winter is here

This one features number theory. We want to find the value of dp[x] as the number of possible subsets whose GCD is x. To do this, we first find the number of subsets where one of their common divisors (not necessarily the maximum one) is x. From there, we determine the number of subsets whose GCD is x.

Let me know your opinions! This is your livestream, and together we can make it better.

1997A — Strong Password

1997B — Make Three Regions

1997C — Even Positions

1997D — Maximize the Root

1997D — Maximize the Root — O(n) Solution

1997E — Level Up

1997F — Chips on a Line

Today, I wasn’t at home. I was at Stevens University in New Jersey. So, the quality was not as usual and I had to keep the livestream shorter (solved only A-E), but it was a new format either way. I tried to show some views of New York City (which is on the other side of the river) to make up for it.

1991A — Maximize the Last Element

1991B — AND Reconstruction

1991C — Absolute Zero

1991D — Prime XOR Coloring

1991E — Coloring Game

Making Up for the Quality by Showing Some Scenery from New York

1996A — Legs

1996B — Scale

1996C — Sort

1996D — Fun

1995E — Decode

1995F — Bomb

1996G — Penacony — My Segtree solution

1996G — Penacony — Jiangly's XOR hashing beautiful solution

1995A — Diagonals

1995B1 — Bouquet (Easy Version)

1995B2 — Bouquet (Hard Version)

1995C — Squaring

1995D — Cases

1995E2 — Let Me Teach You a Lesson (Hard Version)

Just explained a code. If you know the full solution, please write that in the comments below.

1990A — Submission Bait

1990B — Array Craft

1990C — Mad MAD Sum

1990D — Grid Puzzle

1990E2 — Catch the Mole(Hard Version)

Not a formal proof! (please explain the formal proof of the algorithm in the comment section if you know that)

1994A — Diverse Game

1994B — Fun Game

1994C — Hungry Games

1994D — Funny Game

1994E — Wooden Game

1994F — Stardew Valley

1994G — Minecraft

1988A — Split the Multiset

1988B — Make Majority

1988C — Increasing Sequence with Fixed OR

1988D — The Omnipotent Monster Killer

1988E — Range Minimum Sum

1992A — Only Pluses

1992B — Angry Monk

1992C — Gorilla and Permutation

1992D — Test of Love

1992E — Novice's Mistake

1992F — Valuable Cards

1992G — Ultra-Meow