Hi Codeforces,

Our last topic stream was on Combinatorics. We talked about exponentiation, combination (+ why does it have that formula), what is a combinatorial proof (the most interesting part), and proved Pascal's equality and a bunch of other problems using that. Then, we talked about how to calculate combination with O(N) preprocess time and O(1) query time, and finally, solved 559C — Gerald and Giant Chess.

Exponentiation ($$$a^b$$$) in $$$O(lgb)$$$

Combination $$$n\choose k$$$ and why is it $$$\frac{n!}{k!(n-k)!}$$$

Algebraic proofs suck, what is a Combinatorial Proof

(+ Proving a bunch of equalities like Pascal's, using combinatorial proof)

ChatGPT trolling me

Calculating combination in code

simplest: $$$O(n^2+q)$$$

better: $$$O(n+qlgn)$$$

even better: $$$O(nlgn+q)$$$

not that much different: $$$O(n + q)$$$

Solving 559C — Gerald and Giant Chess

(Combination + DP)

This is the link to choose the topic for the next topic stream:

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.

2065A — Skibidus and Amog'u

2065B — Skibidus and Ohio

2065C — Skibidus and Fanum Tax

2065D — Skibidus and Sigma

2065E — Skibidus and Rizz

2065F — Skibidus and Slay

2065G — Skibidus and Capping

2065H — Bro Thinks He's Him

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.

During today’s contest solution discussion, we tested ChatGPT o3-mini-high on our contest problems. And get this: it solved problems C and D! It claimed that it did it without internet access.

We asked about its capability, and it said that if it made a Codeforces account, its rating would be 3500–4000! I don’t know if AI has learned to solve very hard problems or if it’s getting overconfident.

All I can say is, things are getting pretty SCARY. I have no idea what’s going to happen with CP contests and competitive programmers soon.

2059A — Milya and Two Arrays

2059B — Cost of the Array

2059C — Customer Service

GPT o3-mini-high Solved C

2059D — Graph and Graph

GPT o3-mini-high Solved D

Asking ChatGPT if it is Cheating (Has Internet Access)

o3 claiming that it has rating 3500 on Codeforces!

Trying to Solve E2 with o2 — Not Successful

P.S. Seems like rank 4000+ should be called GPT soon.

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.

2060A — Fibonacciness

2060B — Farmer John's Card Game

2060C — Game of Mathletes

2060D — Subtract Min Sort

2060E — Graph Composition

2060F — Multiplicative Arrays

2060G — Bugged Sort

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.

2050A — Line Breaks

2050B — Transfusion

2050C — Uninteresting Number

2050D — Digital string maximization

2050E — Three Strings

2050F — Maximum modulo equality

2050G — Tree Destruction

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.

2042A — Greedy Monocarp

2042B — Game with Colored Marbles

2042C — Competitive Fishing

2042D — Recommendations

2042E — Vertex Pairs (not complete)

2042F — Two Subarrays

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.

2034A — King Keykhosrow's Mystery

2034B — Rakhsh's Revival

2034C — Trapped in the Witch's Labyrinth

2034D — Darius' Wisdom

2034E — Permutations Harmony

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.

2037A — Twice

2037B — Intercepted Inputs

2037C — Superultra's Favorite Permutation

2037D — Sharky Surfing

2037E — Kachina's Favorite Binary String

2037F — Ardent Flames

2037G — Natlan Exploring

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.

2028A — Alice's Adventures in "Chess"

2028B — Alice's Adventures in Permuting

2028C — Alice's Adventures in Cutting Cake

2028D — Alice's Adventures in Cards

2028E — Alice's Adventures in the Rabbit Hole

2028F — Alice's Adventures in Addition

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.

2029A — Set

2029B — Replacement

2029C — New Rating

2029D — Cool Graph

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.

2036A — Quintomania

2036B — Startup

2036C — Anya and 1100

2036D — I Love 1543

2036E — Reverse the Rivers

2036F — XORificator 3000

2036G — Library of Magic

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.

2032A — Circuit

2032B — Medians

2032C — Trinity

2032D — Genokraken

2032E — Balanced

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.

2026A — Perpendicular Segments

2026B — Black Cells

2026C — Action Figures

2026D — Sums of Segments

2026E — Best Subsequence

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.

2035A — Sliding

2035B — Everyone Loves Tres

2035C — Alya and Permutation

2035D — Yet Another Real Number Problem

2035E — Monster (Observations)

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.

2027A — Rectangle Arrangement

2027B — Stalin Sort

2027C — Add Zeros

2027D2 — The Endspeaker (Hard 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, not as a substitute for the text editorial.

2033A — Sakurako and Kosuke

2033B — Sakurako and Water

2033C — Sakurako's Field Trip

2033D — Kousuke's Assignment

2033E — Sakurako, Kosuke, and the Permutation

2033F — Kosuke's Sloth

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.

2030A — A Gift From Orangutan

2030B — Minimise Oneness

2030C — A TRUE Battle

2030D — QED's Favorite Permutation

2030E — MEXimize the Score

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.

2022A — Bus to Pénjamo

2022B — Kar Salesman

2022C — Gerrymandering

2022D1 — Asesino (Easy Version)

2022E1 — Billetes MX (Easy Version)

2022E2 — Billetes MX (Hard Version)

Hi,

Our last topic stream was on Number Theory. I will continue discussing number theory next week, where we will cover more facts and solve more problems.

Here is the text version of this topic stream. I will briefly summarize all the topics discussed in the livestream. You can watch the full session below.

Definition of GCD

In this section, I introduce the concept of the Greatest Common Divisor.

Proving that gcd(a, b) = gcd(a — b, b)

As the title suggests, we prove a fact about GCD. This fact is extremely useful!

The Naive Algorithm to Calculate GCD

Here, we introduce the naive solution to calculate the GCD. It works in O(min(a, b)) by simply iterating through all possible candidates.

Extend the Fact to gcd(a, b) = gcd(a % b, b)

Then, we extend the fact that gcd(a, b) = gcd(a — b, b) to gcd(a, b) = gcd(a % b, b).

Prove that a % b < a / 2 if a >= b

In this section, we prove another very useful fact, which helps us find the GCD with improved time complexity.

O(lg a) Algorithm to Calculate GCD

Here, we use the facts to improve our solution to calculate the gcd of two numbers.

Solving 1458A from Codeforces

In this section, the following problem will be solved. It is really beautiful.

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

How to Find All the Prime Numbers between 1 and N in O(N)

Another classic problem in number theory.

Improving the Algorithm to O(N sqrt(N))

We use a simple fact to reduce one N to sqrt(N).

Sieve of Eratosthenes — Improving the Algorithm to O(N.lgN)

Here, I introduce the Sieve of Eratosthenes. I explain the solution step by step, and at the end, I mention that this method is called the Sieve of Eratosthenes.

Harmonic Series

In the middle of solving the problem with this method, we encounter with a number that we have to find out how big it is. We need this to find out the time complexity of our method. We will analyze the complexity of this number. We will analyze the complexity of this number, and we’ll see that it is actually known as the Harmonic Series.

Solving 230B from Codeforces

Then, we try to use the topics we talked about to solve the following problem from Codeforces.

https://codeforces.me/problemset/problem/230/B

Find the Smallest Prime Factor with Sieve

Actually, Sieve can be used to solve more challenging problems as well. Here, we discuss how to find the smallest prime factor of a number using Sieve.

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.

2020A — Find Minimum Operations

2020B — Brightness Begins

2020C — Bitwise Balancing

2020D — Connect the Dots

2020E — Expected Power

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.

2019A — Max Plus Size

2019B — All Pairs Segments

2019C — Cards Partition

2019D — Speedbreaker

2019E — Tree Pruning

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.