### maomao90's blog

By maomao90, history, 3 weeks ago,

# Introduction

Remember my previous blog? I mentioned that I am planning to write a blog about static top tree. AtCoder already has a pretty good explanation of the static top tree, so I was thinking how I can do better. Then, VisualAlgo came into mind. Why not I make an interactive website that showcases the static top tree? Well, that is exactly what I did!

# Website

Here is the website that is hosted using GitHub pages. The public GitHub repository of my code is here.

The website is created using the React framework. This is my first time using React, so the code is quite messy. Feel free to let me know how I can improve the code in the comments, or even submit pull requests on GitHub!

I will be making use of my website to create diagrams for my Static Top Tree blog that will be coming up in the near future. Let me know what else you would like to see from the visualisation or how I can make the visualisation clearer and better. Feel free to suggest any additional features as well.

# Credits

I am not an artistic person, so most of the UI is inspired by other websites. The majority of my UI is inspired by VisualAlgo and CS academy graph editor.

• +130

By maomao90, history, 5 weeks ago,

# Introduction

I recently came across this problem which required an interesting trick to compute $a_i \otimes a_{i + 1} \otimes \ldots \otimes a_{i + w - 1}$ for all $1 \le i \le n - w + 1$ in $O(n)$ time and space. I found the trick very interesting, so I decided to write a short blog about it.

# Problem

Given an array $a$ of size $n$ and an integer $w$. You are required to compute the value of $a_i \otimes a_{i + 1} \otimes \ldots \otimes a_{i + w - 1}$ for all $1 \le i \le n - w + 1$ in $O(n)$ time and space. $\otimes$ is a binary operation that is associative ($(x \otimes y) \otimes z = x \otimes (y \otimes x)$).

# Solution

Split array $a$ into blocks of size $w$. In each block, we calculate applying the operator on each prefix and on each suffix. Then, any range of width $w$ can be formed by combining the suffix of one block with the prefix of another block.

The implementation is very easy as well. Let $p_i = a_{\left\lfloor\frac{i - 1}{w}\right\rfloor\cdot w + 1} \otimes \ldots \otimes a_i$ and $s_i = a_i \otimes \ldots \otimes a_{\left\lceil\frac{i}{w}\right\rceil\cdot w}$ for all $1 \le i \le n$. Then, $a_i \otimes a_{i + 1} \otimes \ldots \otimes a_{i + w - 1} = s_i \otimes p_{i + w - 1}$.

# Extension

If we try to generalize this solution to work for queries of arbitrary width, we will realize that it becomes a disjoint sparse table. In disjoint sparse table, the queries can have arbitrary width, so we need to split into blocks of width $2^k$ for all $1 \le k \le \log_2 n$. For our application, since we only have queries of a fixed width, we only need one layer, and hence we can obtain a solution in linear time and space.

• +178

By maomao90, 6 weeks ago,

It's about time... 6 months have passed since Hello 2024 and the halving is taking place. It is about time I retire from my top 1 contribution spot :(

I want to take this opportunity to thank the community for being so generous with your upvotes for my Hello 2024 round. Thank you for letting me have this achievement of reaching the top contributor spot that not many people will get to experience. Regarding this, I hope that people will be more generous with their upvotes for other rounds as well. A big part of why Hello 2024 received so many upvotes is that Goodbye 2023 was not a great round. If a round went smoothly with no serious issues, why not upvote the round? This will encourage the problem-setters and motivate them to create more rounds in the future.

In return for the community's support, I am considering writing some educational blogs. Let me know what type of blog you want to see from me in the comments. I am considering writing a tutorial about Static Top Tree since there are some functionality that the atcoder editorial does not explain, and there has been quite a few problems that can be solved using Static Top Tree recently. Let me know what you think in the comments. Thanks!

• +635

By maomao90, history, 4 months ago,

# Introduction

Many communication problems involve sending information from one function to another by sending $0$s and $1$s (binary) or some number smaller than $b$ (base $b$). In these problems, we often need to change the information that we want to send from one base to another.

This can be particularly tricky when the information that we want to send is a sequence of numbers. A common way to do so is to send each number one by one using $\lceil \log_b (k) \rceil$ digits where $b$ is the base we can send information in and the elements of the sequence are between $0$ and $k - 1$. The problem with this is that if we are sending $l$ numbers, we are possibly wasting some digits as $l\lceil \log_b (k) \rceil \ge \lceil l\log_b (k) \rceil$.

In this blog, I will be demonstrating a way to encode $n$ sequences $a_0, a_1, \ldots, a_{n - 1}$, each sequence $a_i$ consisting of $l_i$ non-negative integers $0 \le a_{i, 0}, a_{i, 1}, \ldots, a_{i, l_i - 1} < k_i$. The sequences will be encoded into a single sequence $x$ of length $m$ consisting of non-negative integers $0 \le x_0, x_1, \ldots, x_{m - 1} < b$, where $m = \lceil\sum_{i=0}^{n - 1} l_i\log_b k_i\rceil$. Conveniently, the inverse operation to decode sequence $x$ back into $n$ sequences $a_0, a_1, \ldots, a_{n - 1}$ follows a very similar structure which I will show below.

• +138

By maomao90, 7 months ago,

I guess I can farm even more contribution since I am top 1 contributor now 🤡 . Maybe some of you might have some questions about my CP journey or Hello 2024 so feel free to ask here. No guarantees that I will answer every question because I will be serving in the Singapore Police Force soon (all male Singaporeans are required to serve two years of military service ://), which also explains the comments here. Thanks everyone for your support on Hello 2024 and helping me to climb from ~130 contribution to almost 170 contribution :).

• +519

By maomao90, history, 7 months ago,

How did Hello 2024 announcement blog get 1000 upvotes before the contest even started 🤪 ? Is 4000 downvotes on Goodbye 2023 too much for codeforces to handle so upvotes on other blogs scale exponentially now 🤔 ? I mean... I don't mind but it's kind of funny that I am now one of the top 10 contributors because of Hello 2024 🤡 . Maybe this blog will get another 1000 upvotes 😁

• +340

By maomao90, history, 7 months ago,

Hello Codeforces,

We are very glad to invite you to participate in Hello 2024, which will start on Jan/06/2024 17:35 (Moscow time). You will be given 8 problems and 2.5 hours to solve them. One of the problems will be divided into two subtasks. The round will be rated for everyone. There will be at most 2024 interactive problems, so please read the guide for interactive problems before the contest.

All the problems are written and prepared by me.

Spoiler

We would like to give our sincere thanks to:

The score distribution is $250 - 500 - 1000 - 1500 - 2250 - (1500 + 1500) - 4000 - 5000$.

Hope everyone will enjoy the round!

Congratulations to the winners!

Congratulations to the first solves as well!

UPD: Editorial

Announcement of Hello 2024
• +2422

By maomao90, 7 months ago,

Author: maomao90

Hint 1
Solution
Code

Author: maomao90

Hint 1
Solution
Code

### 1919C - Grouping Increases

Author: maomao90

Hint 1
Solution 1
Hint 1
Hint 2
Hint 3
Solution 2
Code (Solution 1)
Code (Solution 2)
Bonus

Author: maomao90

Hint 1
Hint 2
Solution
Code

Author: maomao90

Hint 1
Hint 2
Solution
Code
Bonus

### 1919F1 - Wine Factory (Easy Version)

Author: maomao90

Hint 1
Solution 1
Solution 2
Code (Solution 1)

Author: maomao90

Hint 1
Hint 2
Hint 3
Solution
Code

Author: maomao90

Hint 1
Hint 2
Hint 3
Hint 4
Hint 5
Solution
Code

### 1919H - Tree Diameter

Author: maomao90
Full solution: dario2994

Background
Hint 1
Hint 2
Hint 3
Hint 4
Hint 5
Hint 6
Solution
Code
Tutorial of Hello 2024
• +760

By maomao90, history, 9 months ago,

Hello Codeforces,

We are very glad to invite you to participate in CodeTON Round 7 (Div. 1 + Div. 2, Rated, Prizes!), which will start on Nov/25/2023 17:50 (Moscow time). You will be given 8 problems and 2.5 hours to solve them. The round will be rated for everyone.

All the problems are written and prepared by lanhf, Mike4235, thenymphsofdelphi, xuanquang1999 and me.

We would like to give our sincere thanks to:

The score distribution is $500-1000-1500-2000-2250-2750-3250-(4000+1000)$.

Hope everyone can enjoy the round!

Congratulations to the winners!

Congratulations to the first solves as well!

UPD1: The contest is delayed by 15 minutes due to prior issues with the registration system in order to make sure everyone is correctly registered. Please double-check that you are registered.

UPD2: Editorial

And here is the information from our title sponsor:

Hello, Codeforces!

We, the TON Foundation team, are pleased to support CodeTON Round 7.

The Open Network (TON) is a fully decentralized layer-1 blockchain designed to onboard billions of users to Web3.

Since July 2022, we have been supporting Codeforces as a title sponsor. This round is another way for us to contribute to the development of the community.

The winners of CodeTON Round 7 will receive valuable prizes.

The first 1,023 participants will receive prizes in TON cryptocurrency:

• 1st place: 1,024 TON
• 2–3 places: 512 TON each
• 4–7 places: 256 TON each
• 8–15 places: 128 TON each
• 512–1,023 places: 2 TON each

We wish you good luck at CodeTON Round 7 and hope you enjoy the contest!

• +788

By maomao90, history, 11 months ago,

It is not uncommon to have interactive tree problems where you are allowed to query some connected component of the tree and use the return value to determine whether the answer is in the connected component or outside the connected component (Link to example problem). The general approach for these kinds of problems is to always choose a connected component of size $\frac{n}{2}$. However, there are also problems where the allowed queries are more restricted, preventing $\frac{n}{2}$ halving from being possible. This blog covers one of those types of problems.

# Definitions

• Subtree: $S(r, u)$ contains the set of vertices in the subtree of vertex $u$ if the tree was rooted at vertex $r$.
• Neighbour: $N(u)$ contains the set of vertices that are directly adjacent to vertex $u$.
• Extended subtree: $ES(r, V) = \bigcup_{v\in V} S(r, v)\text{ if } v\in N(r)$. In other words, an extended subtree is a combination of the subtrees of a chosen set of vertices that are directly adjacent to the root.

# Problem Structure

There is a hidden special vertex in a tree with $n$ vertices. Find the special vertex using at most $\lceil\log_{1.5}n\rceil$ of the following query:

• Choose an extended subtree of the tree. The grader will return whether the special vertex is in the chosen extended subtree. More formally, choose any vertex $r$ and a subset of neighbours $V \subseteq N(r)$, then the grader will return whether the special vertex $x \in ES(r, V)$.
• +119

By maomao90, history, 12 months ago,

After 21 days and 56 submissions on IOI 2010 Maze, I finally broke the 100 point barrier and achieved a score of 100.081 / 100.

• +310

By maomao90, history, 15 months ago,

# Code golf challenge for 1817D - Toy Machine

In case you do not know what code golf is, the objective is to write the shortest code possible that solves the problem.

After losing 41 rating from Codeforces Round 869 (Div. 1) and almost becoming yellow again, I was depressed and decided to try to upsolve this problem. Surprisingly, I was able to discover a very simple pattern that allowed me to come up with a short and cute solution. Why do I always only solve problems after contest and not during contest 😭

Anyways, here is my code in python:

n,k=map(int,input().split())
print(["RDLU"*(n-k-2)+"LDLU"*n+"RDL","LDRU"*(k-1)+"L"][k<n/2])


Here is my original C++ code that is more readable 204002089.

The prize for coming up with an even shorter code is an ego boost. Bonus points if you come up with an even simpler solution that is different from the pattern that I discovered.

• +52

By maomao90, history, 17 months ago,

Recently when I was doing Universal Cup Round 5, I got stuck on a tree problem A as I realized that my solution required way too much memory. However, after the contest, I realized that there was a way that I could reduce a lot of memory using HLD. So here I am with my idea...

# Structure of Tree DP

Most tree DP problems follow the following structure.

struct S {
// return value of DP
};
S init(int u) {
// initialise the base state of dp[u]
}
S merge(S left, S right) {
// returns the new dp state where old state is left and transition using right
}
S dp(int u, int p) {
S res = init(u);
for (int v : adj[u]) {
if (v == p) continue;
res = merge(res, dp(v, u));
}
return res;
}
int main() {
dp(1, -1);
}


An example of a tree DP using this structure is maximum independent set (MIS).

Code

Suppose struct $S$ requires $|S|$ bytes and our tree has N vertices. Then this naive implementation of tree DP requires $O(N\cdot |S|)$ memory as res of the parent is stored in the recursion stack as we recurse down to the leaves. This is fine for many problems as most of the time, $|S| = O(1)$, however in the case of the above question, $|S| = 25^2\cdot 24$ bytes and $N = 10^5$, which will require around $1.5$ gigabytes of memory, which is too much to pass the memory limit of $256$ megabytes. Below, I will show a way to use only $O(N + |S|\log N)$ memory.

• +270

By maomao90, history, 19 months ago,

For the past 6 months, I have been changing from red to yellow and back to red repeatedly. As a competitive programmer, I used my acute observation skills to try to figure out the problem. Immediately, I was able to see a trend. Whenever I am yellow, my rating increases. However, the moment I reach red, my rating will decrease.

Hence, can the color of GM be changed to yellow so that I can reach LGM? Thank you!

• +273

By maomao90, history, 19 months ago,

I was attempting to implement the solution to 1770G - Koxia and Bracket after reading the editorial recently but I kept getting TLE on test case 12. However, after changing the compiler from GNU C++17 to GNU C++17 (64), I got AC in 1185ms, which is very far off from the time limit of 5 seconds.

GNU C++17: 188211296

GNU C++17 (64): 188211331

I tried testing it on errorgorn solution in the editorial as well and there was the same problem.

GNU C++17: 188211673

GNU C++17 (64): 188211705

I thought that it might be because of the NTT implementation that we used (KACTL), however, I even tried on Radewoosh submission which uses a different NTT implementation, but still faces the same issue.

GNU C++17: 188203821

GNU C++20 (64): 187349301

I have seen some cases where 64-bit compiler runs faster than 32-bit before, but never to such a large extent. Does anyone know the reason why? Does NTT run a lot faster on 64-bit compiler? Or is it something about our implementation?

If anyone know the reason why, I will appreciate it very much if you could explain it to me down in the comments. I guess it is about time that I shift from GNU C++17 to GNU C++17 (64) 😢

• +35

By maomao90, history, 20 months ago,

I recently had to make slides to teach people about maximum flow and minimum cost maximum flow, so I thought it would be good if I share it with Codeforces as well. I think this will benefit everyone as the beginners can get a better understanding of the basics of maximum flow and minimum cost maximum flow in the first few slides and the more advanced people can look at the slides further on which explains how we can use minimum cost maximum flow to solve some greedy problems. Hope everyone will enjoy my slides!

Please let me know in the comment if you see any mistakes or you want to suggest any improvements. Thank you!

• +190

By maomao90, history, 2 years ago,

# Introduction

As mentioned in my previous blog, I will be writing a tutorial about slope trick. Since there are already many blogs that goes through the concept of slope trick, my blog will focus more on the intuition behind coming up with the slope trick algorithm.

Hence, if you do not know slope trick yet, I suggest that you read other slope trick blogs such as https://mirror.codeforces.com/blog/entry/47821 and https://mirror.codeforces.com/blog/entry/77298 before reading my blog. In the future explanation on the example problems, I will assume that the reader already knows the big idea behind slope trick but do not know how to motivate the solution.

Great thanks to errorgorn for proofreading and writing the section on convex convolution and merchant otter.

# When to use slope trick?

Most of the time, slope trick can be used to optimise dp functions in the form of $dp_{i, j} = \min(dp_{i - 1, j - 1}, dp_{i - 1, j} + A_i)$ or dp functions containing costs with absolute values. In this kind of dp functions, the graph of the dp function where the x-axis is $j$ and y-axis is $dp_{i, j}$ changes predictably from $i$ to $i + 1$ which allows us to store the slope-changing points and move to $i + 1$ by inserting and deleting some slope-changing points.

Sometimes, slope trick can also be an alternative solution to a greedy question. The code will probably end up being the same as well, so sometimes slope trick can help you to find out the greedy solution instead. Personally, I find that slope trick is very helpful in this area as we do not have to proof the greedy since dp completely searches all possible states and is definitely correct.

• +211

By maomao90, history, 2 years ago,

Slope trick is one of my favorite algorithms, so I have been considering writing a blog about it. However, there are already a lot of resources about slope trick, so I am not sure whether anyone would benefit from yet another slope trick blog.

If I were to write a slope trick blog, it would focus more on the intuition behind how I solve slope trick problems together with multiple difficult example problems (not 713C - Соня и задача без легенды) where I show my step by step thought process. If you would like to see this slope trick blog, please upvote this blog. I will write a slope trick blog if this blog receives more than 100 upvotes. Thanks for all your support 👍

EDIT: Wow, already more than 100 upvotes in such a short time. See you in my upcoming slope trick blog 😉

EDIT 2: The long awaited slope trick blog is here! Hope that you will enjoy it :)

• +395

By maomao90, 2 years ago,

Hope that everyone enjoyed the round. Feel free to ask questions in the comments if you do not understand any part of the editorial

Hints
Tutorial
Solution

1672B - I love AAAB
Author: errorgorn

Hints
Tutorial
Solution
Hints
Tutorial
Solution
Hints
Tutorial 1
Tutorial 2
Solution 1
Solution 2
Hints
Tutorial
Solution
Hints
Tutorial
Solution for F1
Solution for F2
Hints
Tutorial
Solution
Hints
Tutorial
Solution
Hints
Tutorial
Solution
• +135

By maomao90, history, 3 years ago,

I decided to write a blog on this as I was doing a problem on our local judge and I decided to try to speed up my brute force code. However, it was quite difficult to find resources on SIMD vectorisation, so I decided to try to compile some of the resources I found to hopefully allow more people to learn to scam brute force solutions

Thanks to iLoveIOI and jamessngg for proofreading.

# Introduction

SIMD stands for single instruction, multiple data. SIMD allows us to give vector instructions which will allow the code to run faster. Vector instructions are instructions that handle short (length 2-16) vectors of integers / floats / characters in a parallel way by making use of the extra bits of space to do operations simultaneously.

The most common form of vectorisation is making use of pragmas such as

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")


This form of vectorisation is known as auto-vectorisation as the compiler vectorises the code for you. However, for more complicated examples, the compiler might be unable to detect what to vectorise automatically, so in this case, we have to vectorise our code manually by using SIMD vectorisation.

# Syntax

The compilation of all the code given in the syntax section is given here

Code

To make use of SIMD, we have to add the following at the top of the code.

#include <nmmintrin.h>

#pragma GCC target("avx2")

• +277

By maomao90, history, 3 years ago,

### Abridged statement

There are $N$ vertices in the graph where $N=2^n$ where $n$ is an integer. An array $A$ of size $M$ is given. An edge can be drawn from $i$ to $i\oplus x$ ($\oplus$ represents xor operation) if $x\notin A$. Print $N - 1$ edges such that the edges form a tree.

Statement

#### Issue

The intended solution uses xor basis / gaussian elimination. However, I found some submissions that uses completely different algorithms that ACs all the testcases.

In summary, the code iterates through all the $x\notin A$, and for each $x$, iterate through all the vertices $v$ from $0$ to $n - 1$. While $v$ and $v \oplus x$ are not connected, connect them and move on to vertex $v + 1$, otherwise, break. This algorithm runs in $O(n)$ as it will only connect edges $n - 1$ times and when it cannot connect edges, it breaks immediately. However, does anyone have a proof that it is correct? Will there be any case where breaking early results in the wrong answer? I tried creating a few test cases by hand and it seems to always generate the correct answer.

Code

In another submission, a similar idea was used, however, instead of breaking early, it iterated through all the vertices from $0$ to $n - 1$ as long as $0$ and $x$ are not connected. This clearly results in the correct answer as by looping through all the vertices from $0$ to $n - 1$, it will definitely result in at least one edge being created, so $n - 1$ edges will be created after all iterations. However, it looks as if the algorithm runs in $O(n^2)$. Why does it not TLE?

Code
• +14