maomao90's blog

By maomao90, 3 months ago, In English

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

Full text and comments »

  • Vote: I like it
  • +519
  • Vote: I do not like it

By maomao90, history, 3 months ago, In English

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 😁

Full text and comments »

  • Vote: I like it
  • +340
  • Vote: I do not like it

By maomao90, history, 3 months ago, In English

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!

  1. ecnerwala
  2. ksun48
  3. VivaciousAubergine
  4. gamegame
  5. cnnfls_csy
  6. maroonrk
  7. tourist
  8. Geothermal
  9. kmjp
  10. yosupo

Congratulations to the first solves as well!

UPD: Editorial

Full text and comments »

Announcement of Hello 2024
  • Vote: I like it
  • +2422
  • Vote: I do not like it

By maomao90, 3 months ago, In English

1919A - Wallet Exchange

Author: maomao90

Hint 1
Solution
Code

1919B - Plus-Minus Split

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

1919D - 01 Tree

Author: maomao90

Hint 1
Hint 2
Solution
Code

1919E - Counting Prefixes

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)

1919F2 - Wine Factory (Hard Version)

Author: maomao90

Hint 1
Hint 2
Hint 3
Solution
Code

1919G - Tree LGM

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

Full text and comments »

Tutorial of Hello 2024
  • Vote: I like it
  • +760
  • Vote: I do not like it

By maomao90, history, 4 months ago, In English

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!

  1. Radewoosh
  2. ksun48
  3. ecnerwala
  4. maroonrk
  5. jqdai0815
  6. hos.lyric
  7. zh0ukangyang
  8. 244mhq
  9. Vercingetorix
  10. BigYellowDuck

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!

Full text and comments »

  • Vote: I like it
  • +788
  • Vote: I do not like it

By maomao90, history, 6 months ago, In English

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

Full text and comments »

  • Vote: I like it
  • +119
  • Vote: I do not like it

By maomao90, history, 8 months ago, In English

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.

Score distribution

Full text and comments »

  • Vote: I like it
  • +310
  • Vote: I do not like it

By maomao90, history, 11 months ago, In English

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.

Full text and comments »

  • Vote: I like it
  • +52
  • Vote: I do not like it

By maomao90, history, 13 months ago, In English

Recently when I was doing Universal Cup Round 5, I got stuck 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 can 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 have 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.

Optimization

We try to make use of the idea of HLD and visit the visit the vertex with the largest subtree size first.

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
}
int sub[MAXN];
void getSub(int u, int p) {
    sub[u] = 1;
    pair<int, int> heavy = {-1, -1};
    for (int i = 0; i < adj[u].size(); i++) {
        int v = adj[u][i];
        if (v == p) continue;
        getSub(v, u);
        sub[u] += sub[v];
        heavy = max(heavy, {sub[v], i});
    }
    // make the vertex with the largest subtree size the first
    if (heavy.first != -1) {
        swap(adj[u][0], adj[u][heavy.second]);
    }
}
S dp(int u, int p) {
    // do not initialize yet
    S res;
    bool hasInit = false;
    for (int v : adj[u]) {
        if (v == p) continue;
        S tmp = dp(v, u);
        if (!hasInit) {
            res = init();
            hasInit = true;
        }
        res = merge(res, tmp);
    }
    if (!hasInit) {
        res = init();
        hasInit = true;
    }
    return res;
}
int main() {
    getSub(1, -1);
    dp(1, -1);
}

If we analyze the memory complexity properly, we will realize that it becomes $$$O(N + |S|\log N)$$$. The $$$O(N)$$$ comes from storing the subtree sizes, and the $$$O(|S|\log N)$$$ comes from the DP itself.

Proof

The two main changes from our naive DP is that we initialize our res only after we visit the first child, and we visit the child with the largest subtree size first. Recalling the definitions used in HLD, we define an edge $$$p_u \rightarrow u$$$ to be a heavy edge if $$$u$$$ is the child with the largest subtree size among all children of $$$p_u$$$. We will call all other non-heavy edges as light edges. It is well known that the path from the root to any vertex of a tree will involve traversing many heavy edges but at most $$$O(\log N)$$$ light edges.

Making use of this idea, if we visit heavy edges first, res of the parent of heavy edges will not be stored in the recursion stack since we only initialize our res after visiting the first edge, hence only res of the parent of light edges will be stored in the recursion stack. Then since there is at most $$$O(\log N)$$$ light edges, the memory complexity is $$$O(|S|\log N)$$$.

My solution to the above problem

Conclusion

I have not seen this idea anywhere before and only came up with it recently during Universal Cup. Please tell me if it is actually a well-known technique or there are some flaws in my analysis. Hope that this will be helpful to everyone!

Full text and comments »

  • Vote: I like it
  • +270
  • Vote: I do not like it

By maomao90, history, 14 months ago, In English

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.

My rating graph

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

Full text and comments »

  • Vote: I like it
  • +273
  • Vote: I do not like it

By maomao90, history, 15 months ago, In English

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

Full text and comments »

  • Vote: I like it
  • +35
  • Vote: I do not like it

By maomao90, history, 15 months ago, In English

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!

Link to google slides

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

Full text and comments »

  • Vote: I like it
  • +190
  • Vote: I do not like it

By maomao90, history, 22 months ago, In English

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://codeforces.com/blog/entry/47821 and https://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.

Full text and comments »

  • Vote: I like it
  • +211
  • Vote: I do not like it

By maomao90, history, 22 months ago, In English

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 - Sonya and Problem Wihtout a Legend) 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 :)

Full text and comments »

  • Vote: I like it
  • +395
  • Vote: I do not like it

By maomao90, 23 months ago, In English

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

1672A - Log Chopping
Author: errorgorn

Hints
Tutorial
Solution

1672B - I love AAAB
Author: errorgorn

Hints
Tutorial
Solution

1672C - Unequal Array
Author: maomao90

Hints
Tutorial
Solution

1672D - Cyclic Rotation
Author: errorgorn

Hints
Tutorial 1
Tutorial 2
Solution 1
Solution 2

1672E - notepad.exe
Author: errorgorn, oolimry

Hints
Tutorial
Solution

1672F1 - Array Shuffling and 1672F2 - Checker for Array Shuffling
Author: errorgorn

Hints
Tutorial
Solution for F1
Solution for F2

1672G - Cross Xor
Author: maomao90, errorgorn

Hints
Tutorial
Solution

1672H - Zigu Zagu
Author: maomao90, errorgorn

Hints
Tutorial
Solution

1672I - PermutationForces
Author: errorgorn

Hints
Tutorial
Solution

Full text and comments »

  • Vote: I like it
  • +135
  • Vote: I do not like it

By maomao90, history, 2 years ago, In English

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 proof reading.

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

Data types

There are three 128 bit data types for integers, floats and doubles respectively.

__m128i i; // stores 4 integers since each integer is 32 bit and 128/32=4
__m128 f; // stores 4 floats since each float is 32 bit and 128/32=4
__m128d d; // stores 2 doubles since each double is 64 bit and 128/64=2

Full text and comments »

  • Vote: I like it
  • +277
  • Vote: I do not like it

By maomao90, history, 3 years ago, In English

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

Full text and comments »

  • Vote: I like it
  • +14
  • Vote: I do not like it