ouuan's blog

By ouuan, history, 5 months ago, In English

I want to keep the story short and clear:

  1. On 2020/6/21, I received an e-mail from help@codechef.com. I was told that one of my solutions in APRIL20A was found to be similar to others'.

    Let us know within five days, if you think you are being wrongly penalized due to the false positive that MOSS has thrown.

  2. On the same day when I received the e-mail, I replied that I used a third-party code which had been publicly available since 2017, and according to the Code Of Conduct I could use it.

  3. On 2020/6/23, I replied with a new e-mail to ask for the progress.

  4. On 2020/6/26, I thought that maybe I shouldn't reply to help@codechef.com, so I wrote a new e-mail to feedback@codechef.com.

  5. Until 2020/6/30 13:50 (UTC+8), I haven't received any reply to the e-mails mentioned above, and my solutions are still disqualified.

Without any reply for days, I began to think that I might have sent the e-mail to a wrong place again. In the first e-mail, I was only told to "let them know" without any instructions on how to reach them.

However, I heard that some people got a quick reply after writing a blog post, so I guess this is the proper way to reach CodeChef admins.

I hope that "writing a blog post" can be added in Contact Us so that no one will be wasting his/her time on writing e-mails to CodeChef.

Relevant screenshots:

First e-mail from CodeChef

My first two replies

My third e-mail

APRIL20A scores

Read more »

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

By ouuan, history, 7 months ago, In English

tl;dr: Write a new blog on CF (you don't have to post it), add a line [tutorial: <problem id>] (e.g. [tutorial: 1336A]), and preview it.

This tag fetches the tutorial from Polygon. After the problem is added to the problemset, anyone can get it. However, you can't get it if the authors haven't written the tutorial, or they didn't write it on Polygon.

But, why don't authors publish the tutorial even if they've finished writing the tutorials?

There can be many reasons:

  • The tutorials of one or two problems are still under construction, while the tutorials of other problems are finished.

  • The tutorial is written, but not completely finished yet. For example, there may be some grammar mistakes, maybe it's not very easy to understand. The authors may want to make the tutorial better before publishing it.

However, if you don't mind reading a non-finished tutorial which may be hard to understand with some mistakes, this method may be helpful for you.

Read more »

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

By ouuan, history, 9 months ago, In English

When solving CP problems, are you tired of copy-pasting the testcases, and compare the outputs with the answers by eyes?

Today I'll recommend a free-software IDE for those who want to automate everything in competitive programming.

Latest Stable Latest Release

CP Editor began from running testcases in one click, and has been grown into an IDE with many features, like parsing sample testcases from websites and submitting to Codeforces inside the IDE. It's cross-platform and lightweight, and most important, specially designed for competitive programming.

You can learn about more features on the official website.

It's also recommended to visit the GitHub repo to learn more about how to get started and get help.

As you can see, this project is on its early stage, and there are still many features on the way, like auto-completion and stress testing. But it has improved much since the first version! It will be a long way to perfect if there are only a few people working on it, but, if more and more people join us, everything will be possible. It's written in C++ and based on Qt, so it's won't be that hard even if you haven't worked on GUI projects before (personally, I hadn't written anything with Qt before I began contributing to CP Editor). If you are willing to help us, you can read the contributing guidelines.

If you like this editor, please give us a star on GitHub, I believe it will be better and better!

Last but not least, thanks to other contributors including snapdragon3101(the founder), razdeep, w33z8kqrqk8zzzx33, Yatharth1 and polyomino, other projects including CF Tool, Competitive Companion, QCodeEditor, QtFindReplaceDialog, and the Qt framework which make this project possible. Also thanks to the users of CP Editor, Mike MikeMirzayanov Mirzayanov, and all CP problem setters, for making this project meaningful.

screenshot1

screenshot2

(The whole-application dark theme is only available on several platforms including KDE and MacOS, but code editor dark themes are available on all platforms.)

UPD: You should use CF Tool 0.9.0 as for now, we will support CF Tool 1.0.0 soon.

UPD2: New versions 6.1.3 and 6.2.1 are available, CF Tool 1.0.0 is supported in the new versions. (There are also many other changes.)

UPD3: Now 6.4.1 and 6.3.3 are released, you can read the changelog to see what awesome features are added. We have migrated our website to Hugo with the Docsy theme, but we are short of people to write the documentation since we are working hard on developing (writing codes). If anyone is interested in writing the documentation, you can submit pull requests in the website repo or contact us on Telegram or Slack. If you are not familiar with some features of CP Editor, you can ask us and we are glad to offer help. Any small contribution helps.

Read more »

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

By ouuan, history, 11 months ago, In English

tags.png

I've never seen such an educational problem like 1287C - Garland before.

UPD: Fixed now.

UPD2: Though it's obvious, I hope no one would think it's done by me. I only reported it. (Seems that I got some downvotes?)

Read more »

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

By ouuan, history, 11 months ago, In English

Although magic rank is fun, it's also sometimes confusing.

This script can be used for disabling magic rank. You need to install a browser plugin like Tampermonkey to use it.

But, it doesn't work if there are old handles which have been changed recently on the page (during the new year, there are many people who changed their handles, so in many pages, this script doesn't work), due to the CF API (the API won't redirect old handle to new handle, and the whole request fails on a single missing handle).

Read more »

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

By ouuan, history, 11 months ago, In English

Is "In C++, comparator should return false if its arguments are equal." all you should know about comparators in C++?

Definitely NOT.

What's the requirement of the custom comparator in STL?

It should be a Strict Weak Ordering. In other words, let the comparator be $$$f$$$, and $$$f(x, y)=true$$$ means $$$x< y$$$, then:

  1. $$$f(x, x)$$$ must be false (Irreflexivity)

  2. If $$$f(x, y)$$$ is true, then $$$f(y, x)$$$ must be false. (Antisymmetry)

  3. If $$$f(x, y)=true$$$ and $$$f(y, z)=true$$$, then $$$f(x, z)$$$ must be true. (Transitivity)

  4. If $$$f(x, y)=false$$$, $$$f(y, x)=false$$$, $$$f(y, z)=false$$$ and $$$f(z, y)=false$$$, then $$$f(x, z)=false$$$ and $$$f(z, x)=false$$$. (Transitivity of equivalence)

In fact, Antisymmetry can be deduced by Irreflexivity and Transitivity, so we can ignore it.

Here are some examples that these rules aren't satisfied:

Comparator Irreflexivity Transitivity Transitivity of equivalence Example
$$$f(x, y)=x\le y$$$ $$$\times$$$ $$$\sqrt{}$$$ $$$\sqrt{}$$$ any element
$$$f(x, y)=((x-y)\bmod 3 = 1)$$$ $$$\sqrt{}$$$ $$$\times$$$ $$$\sqrt{}$$$ $$$3, 2, 1$$$
$$$f(x, y)=x+1 < y$$$ $$$\sqrt{}$$$ $$$\sqrt{}$$$ $$$\times$$$ $$$3, 2, 1$$$

Why do we need to follow these rules?

Imagine you are the designer of the STL function sort. It's a template function, so you know nothing about the type provided by the user, except the comparator, which means "<".

Is a single "<" enough? Is it necessary for users to provide ">", "≤", "≥" and "=" as well?

In fact, all other comparators can be expressed by "<":

  • $$$x > y$$$ means $$$y < x$$$;

  • $$$x \le y$$$ means $$$y \not < x$$$;

  • $$$x \ge y$$$ means $$$x \not < y$$$;

  • $$$x = y$$$ means $$$x \not < y$$$ and $$$y \not < x$$$. That's why the fourth rule above is called Transitivity of equivalence. We can also say "$$$x$$$ and $$$y$$$ are incomparable" if $$$x \not < y$$$ and $$$y \not < x$$$.

What does "sort" mean exactly?

A sequence is sorted with respect to a comparator comp if for any iterator it pointing to the sequence and any non-negative integer n such that it + n is a valid iterator pointing to an element of the sequence, comp(*(it + n), *it) (or *(it + n) < *it) evaluates to false.

std::sort — cppreference.com

Let's say the sorted array is $$$a_1, a_2, \ldots, a_n$$$, does "sorted" mean "$$$\forall 1\le i\le n-1, a_{i+1}\not < a_i$$$"?

It does, if the comparator is a Strict Weak Ordering.

But if the comparator isn't a Strict Weak Ordering, even "$$$\forall 1\le i\le n-1, a_{i+1}\not < a_i$$$", there can be inversions ($$$a_j < a_i, 1\le i\le j\le n$$$).

Why is Irreflexivity needed?

STL just chose one from Irreflexivity and Reflexivity , and that's the difference between "strict" ($$$<$$$) and "non-strict" ($$$\le$$$).

As this choice is made, if we provide a comparator without Irreflexivity, every two equal elements will be considered as an inversion, thus sorting will become impossible.

Why is Transitivity needed?

In fact, only "no $$$<$$$ cycle with non-equal elements" is needed. Formally, there is no $$$x_1, x_2,\ldots, x_k$$$ satisfying $$$x_1 < x_2 < \ldots < x_k \land x_k < x_1$$$. (I'm not so sure whether it is OK to have $$$\le$$$ cycles or not.)

If the comparator doesn't form any cycles, but Transitivity is not satisfied, we can add Transitivity to it, which won't affect the sorting.

Why is Transitivity of equivalence needed?

Have you ever considered why can't we do the topological sort on a DAG in $$$O(n\log n)$$$ (make it an interactive problem, so that you don't need to read all the edges)?

That's because Transitivity of equivalence is not guaranteed.

In fact, the best query complexity for sorting a poset (partially ordered set) is $$$O(n(w+\log n))$$$, where $$$w$$$ is the width of the poset (or you can treat it as the size of the maximum independent set in a DAG). Reference: Sorting and Selection in Posets.

If we consider incomparable elements as a single element, Strict Weak Ordering will become a strict total order, or a strict partial order with the width of $$$1$$$, thus the query complexity will be $$$O(n\log n)$$$.

Transitivity of equivalence is used in all $$$O(n\log n)$$$ comparison sorting algorithms. Let's see where Transitivity of equivalence is used in bubble sort and quicksort for example.

In bubble sort, it is required that "if there are any inversions, at least one of them is two adjacent elements". But this may be not true without Transitivity of equivalence. In the $$$f(x, y)=x+1 < y$$$ and $$$3, 2, 1$$$ example, the only inversion is $$$(3, 1)$$$, and they are not adjacent.

In the Partitioning step of quicksort with fat partition, the incomparable elements are not handled, thus Transitivity of equivalence is needed.

A problem which needs to be careful with Transitivity of equivalence

I only know links of this problem on some Chinese OJs, if anyone knows links of this problem on other OJs, please make a comment.

There is a practical statement in LOJ10003, and a mathematical version in LG2123.

Practical version

There are $$$n$$$ jobs, each job consists of two parts, the first part must be done in center A, the second part must be done in center B, each center can do at most one job in one time, the second part of the $$$i$$$-th job can be started only if the first part of the $$$i$$$-th job is already done.

The time needed for each part of each job is given, please arrange the order of doing these jobs, in order to minimize the time when all jobs are done.

Mathematical version

There is an array of $$$n$$$ elements, each element has two positive attributes $$$a_i$$$ and $$$b_i$$$. You have to rearrage the elements (but you can't change the corresponding relationship between each pair of $$$a_i$$$ and $$$b_i$$$), the goal is to minimize $$$c_n$$$, where:

$$$ c_i= \begin{cases} a_1+b_1 & i=1\\ \max\left(c_{i-1},\sum\limits_{j=1}^ia_j\right)+b_i & 2\le i\le n \end{cases} $$$

The solution

Let's consider two adjacent elements $$$i$$$ and $$$i+1$$$. Now, we are going to decide whether to swap these two elements or not.

Let $$$pre$$$ be $$$c_{i-1}$$$, $$$sum$$$ be $$$\sum_{j=1}^{i-1}a_j$$$ which are both condidered as constants. Let $$$a_i$$$, $$$b_i$$$, $$$a_{i+1}$$$, $$$b_{i+1}$$$ refer to the value before swapping, no matter whether we swapped them or not.

If we don't swap them, then $$$c_i$$$ will be $$$\max(pre, sum+a_i)+b_i$$$, and $$$c_{i+1}$$$ will be $$$\max(\max(pre, sum+a_i)+b_i, sum+a_i+a_{i+1})+b_{i+1}=\max(pre+b_i+b_{i+1}, sum+a_i+b_i+b_{i+1}, sum+a_i+a_{i+1}+b_{i+1})$$$.

If we swap them, then $$$c_{i+1}$$$ will be $$$\max(pre+b_{i+1}+b_i, sum+a_{i+1}+b_{i+1}+b_i, sum+a_{i+1}+a_i+b_i)$$$.

Let's compare them. We can know that $$$\max(a_{i+1}+b_{i+1}+b_i, a_{i+1}+a_i+b_i) < \max(a_i+b_i+b_{i+1}, a_i+a_{i+1}+b_{i+1})$$$ is a necessary condition for swapping is better. And this condition is equal to $$$\max(-a_i, -b_{i+1}) < \max(-a_{i+1}, -b_i)$$$, thus equal to $$$\min(a_i, b_{i+1}) > \min(a_{i+1}, b_i)$$$.

That's to say, "swapping $$$i$$$ and $$$i+1$$$ when $$$\min(a_i, b_{i+1}) \le \min(a_{i+1}, b_i)$$$ won't make $$$c_n$$$ smaller".

Then, the solution comes:

Sort the elements by some comparator, such that $$$\min(a_i, b_{i+1}) \le \min(a_{i+1}, b_i)$$$ holds for all $$$1\le i\le n-1$$$.

But, if we just use $$$f(i, j)=\min(a_i, b_j)<\min(a_j, b_i)$$$ as the comparator, something will go wrong.

For example:

$$$ \begin{array}{c|c|c|c|c} a&1&1&2&3\\ b&1&1&5&4 \end{array} $$$

and

$$$ \begin{array}{c|c|c|c|c} a&1&3&1&2\\ b&1&4&1&5 \end{array} $$$

They are two different permutations, both satisfy $$$\forall 1\le i\le n-1, \min(a_i, b_{i+1}) \le \min(a_{i+1}, b_i)$$$, but $$$c_4$$$ in the first example is $$$13$$$, $$$c_4$$$ in the second example is $$$14$$$.

Do you know why it is wrong?

In fact, this comparator doesn't satisfy Transitivity of equivalence.

In the example above, $$$\begin{cases}\min(3,1)=\min(1,4)\\ \min(1,5)=\min(2,1)\end{cases}$$$, but $$$\min(3,5)\ne \min(2,4)$$$.

The correct comparator should be:

$$$ f(i, j)=\begin{cases}a_i< a_j&\min(a_i,b_j)=\min(a_j,b_i)\\ \min(a_i,b_j)<\min(a_j,b_i)&\text{otherwise}\end{cases} $$$

The above function is a Strict Weak Ordering.

Let's prove the correctness of this algorithm using the correct comparator:

  1. There is at least one optimal permutation which is a sorted array under this comparator. Proof: Otherwise, apply bubble sort to the optimal permutation to get a sorted array, $$$c_n$$$ won't be larger.

  2. All sorted arrays under this comparator are optimal. Proof: All sorted arrays can be made by swapping incomparable elements from the optimal sorted array mentioned above. And swapping incomparable elements won't change $$$c_n$$$.

In the second step, we used Transitivity of equivalence. If it's not satisfied, the proof will go wrong.

There is another comparator, which is known as "Johnson's rule". This "rule" is equivalent to this comparator:

$$$ f(i, j)= \begin{cases} true & a_i < b_i \land a_j \ge b_j\\ false & a_i \ge b_i \land a_j < b_j\\ a_i < a_j & a_i < b_i \land a_j < b_j\\ b_i > b_j & a_i \ge b_i \land a_j \ge b_j \end{cases} $$$

This is also a Strict Weak Ordering, and $$$f(i, j)=true$$$ implies $$$\min(a_i, b_j)\le\min(a_j, b_i)$$$, so it can solve this problem.

As a conclusion, The "sorting considering swapping adjacent elements" method works like this:

  1. $$$P(x, y)=true$$$ is a necessary condition for "swapping $$$x$$$ and $$$y$$$ is better".

  2. $$$f(x, y)=true$$$ is a sufficient condition for $$$P(x, y)=false$$$, and $$$f$$$ is a Strict Weak Ordering for the elements in the array.

  3. Then, sort the array with $$$f$$$ as the comparator, the sorted array is optimal.

P.S. I tried my best to make statements in this blog correct, but since I'm not an expert at order theory, there may be mistakes. Please make a comment if you find any mistakes.

Read more »

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

By ouuan, history, 12 months ago, In English

Today, I spent a whole afternoon solving 786C - Till I Collapse, because of undefined behavior.

The origin code is here: 66394911. It seems pretty well, but can't even pass the sample tests.

However, after adding one line (t.reserve(5000000);) it passed: 66394938.

For those who don't want to read my codes, here is a shorter one:

#include <iostream>
#include <vector>

using namespace std;

vector<int> bar;

int foo(int p)
{
    int x = bar.size();
    bar.push_back(bar[0]);
    if (p == 0) return x;
    bar[x] = foo(p - 1);
    cout << bar[x] << ' ';
    return x;
}

int main()
{
    bar.resize(1, 0);
    foo(5);
    return 0;
}

Can you guess the output?


The output

The reason

Read more »

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

By ouuan, history, 13 months ago, In English

Many people think they know how to solve the min-cost-max-flow problem, but most of them only know how to solve it with pseudo-polynomial time algorithm (although it usually runs very fast). And in this blog, min_25 provided a counter case generator, most people's MCMF algorithm runs in $$$O(2^{\frac n 2}n^2\log n)$$$ on it.

the counter case

I tried to find learning materials of polynomial minimum cost flow algorithms, but I can only find papers like A Faster Strongly Polynomial Minimum Cost Flow Algorithm and Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems, and I can't understand them very well.

Are there any other learning materials besides the papers? Thanks in advance.

UPD. I've learned an algorithm with time complexity of $$$O(m^2\log U\log m)$$$ ($$$U$$$ refers to the maximum capacity), for Chinese and those who want to see my code, I wrote a blog; for those who want English learning materials, the one mentioned in Laakeri's comment is good.

Read more »

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

By ouuan, history, 14 months ago, In English

Are you bored of writing duplicate codes when solving segment tree problems?

Did you find that segment trees have very little difference from each other?

Do you want a template, which allows you to code only the key parts, the parts different from other segment trees?

Then this template may help.

An example of segment add & multiply, segment query for sum modulo p:

codes

For more information (how to use it), please read README.md on Github.

Read more »

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

By ouuan, history, 14 months ago, In English

The links of the problem:

You can check the statement by yourself.

The solution

My problem is: what's the complexity of the solution to this problem, if there is no limit for nodes' degrees (every constraint including $$$answer\le 30n$$$ keep unchanged, except "each server can be directly connected to at most 10 other servers"). If it's still solvable, why? If not, how to hack the solution in this case?

Tried to hack it with star graph but failed.

Read more »

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

By ouuan, history, 14 months ago, In English

AtCoder Beginner Contest 141 has just finished, and this is an unofficial editorial.

You can check my solutions, but I used lots of defines in my codes, and they're hard to read.

C — Attack Survival

Let $$$cnt[i]$$$ be the number of times the player $$$i$$$ correctly answered a question. The player $$$i$$$ survived if and only if $$$q-cnt[i]<k$$$.

D — Powerful Discount Tickets

First, you have to know $$$\left\lfloor\frac{x}{2^k}\right\rfloor=\left\lfloor\frac{\left\lfloor\frac x 2\right\rfloor}{2^{k-1}}\right\rfloor$$$(when both $$$x$$$ and $$$k$$$ are positive integers and $$$k\ge 1$$$).

In fact, it is true that $$$\left\lfloor\frac{\left\lfloor\frac{x}{y}\right\rfloor}{z}\right\rfloor=\left\lfloor\frac{x}{yz}\right\rfloor$$$ (when $$$x$$$, $$$y$$$, $$$z$$$ are all positive integers).

Proof

Because of this, we can use a single ticket $$$k$$$ times instead of use $$$k$$$ tickets at one time.

Then, we can use a heap (or priority_queue) to maintain all the prices, each time choose the most expensive item, and use a ticket for it.

E — Who Says a Pun?

If we enumberate the split point, it will become a Longest Common Substring Problem.

For example, if we split the string into $$$[1,mid)$$$ and $$$[mid,n]$$$, we need to calculate the LCS of them, and the answer is the maximum LCS among all possible splits.

I used suffix automaton to solve it.

You can also use DP to solve it:

Let $$$f_{i, j}$$$ be the longest length if the first substring starts from $$$i$$$ and the second one starts from $$$j$$$.

$$$f_{i,j}=\begin{cases}0&s[i]\ne s[j]\\min(j-i,f_{i+1,j+1})&s[i]=s[j]\end{cases}$$$

The answer is the maximum value of all $$$f_{i,j}$$$.

F — Xor Sum 3

Consider each bit separately. Let $$$cnt[i]$$$ be the number of "1"s in the $$$i$$$-th bit (the bit of $$$2^i$$$), if $$$cnt[i]$$$ is odd, the sum of this bit is definitely $$$1$$$.

So, we only have to consider the bits with even number of "1"s. If the XOR of the red integers of a bit is $$$1$$$, then the blue one is also $$$1$$$; otherwise they are both $$$0$$$.

So, we have to maximize the XOR of either the red integers or the blue integers (only consider the bits with even number of "1"s), that's to say, find the maximum subset XOR of a given set.

Read more »

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

By ouuan, history, 15 months ago, In English

The top10 of them:

Rank ID Name Upvotes
1 913 Hello 2018 +2848
2 773 VK Cup 2017 — Round 3 +2247
2 806 Codeforces Round #412 (rated, Div. 1, based on VK Cup 2017 Round 3) +2247
2 807 Codeforces Round #412 (rated, Div. 2, base on VK Cup 2017 Round 3) +2247
3 1097 Hello 2019 +1909
4 549 Looksery Cup 2015 +1426
5 611 Good Bye 2015 +1387
6 1205 Codeforces Round #580 (Div. 1) +1335
6 1206 Codeforces Round #580 (Div. 2) +1335
7 908 Good Bye 2017 +1310
8 538 Codeforces Round #300 +1212
9 515 Codeforces Round #292 (Div. 2) +1116
10 1149 Codeforces Round #556 (Div. 1) +1064
10 1150 Codeforces Round #556 (Div. 2) +1064

I wanted to find some rounds with high upvotes for virtual participating, so I wrote a Python program to get this and shared it to the community. Hope it can be helpful.

For more information and the full list, please visit the Github Repo.

Suggestions are welcomed. (e.g. How to get the announcement URL if it's not on the contest page instead of doing it manually, like Codeforces Round #379 (Div. 2)?)

The list only contains the contests which have their annoucement URL (which matches /blog/entry/[0-9]*"[^>]*>Announcement[^<]*</a>) on the contest page.

UPD: The most upvoted round in each year:

Year ID Name Upvotes
2010 48 School Personal Contest #3 (Winter Computer School 2010/11) - Codeforces Beta Round #45 (ACM-ICPC Rules) +85
2011 135 Codeforces Beta Round #97 (Div. 1) +237
2011 136 Codeforces Beta Round #97 (Div. 2) +237
2012 193 Codeforces Round #122 (Div. 1) +367
2012 194 Codeforces Round #122 (Div. 2) +367
2013 264 Codeforces Round #162 (Div. 1) +446
2013 265 Codeforces Round #162 (Div. 2) +446
2014 472 Codeforces Round #270 +794
2015 549 Looksery Cup 2015 +1426
2016 618 Wunder Fund Round 2016 (Div. 1 + Div. 2 combined) +707
2017 773 VK Cup 2017 - Round 3 +2247
2017 806 Codeforces Round #412 (rated, Div. 1, based on VK Cup 2017 Round 3) +2247
2017 807 Codeforces Round #412 (rated, Div. 2, base on VK Cup 2017 Round 3) +2247
2018 913 Hello 2018 +2848
2019 (up to Sep.10th) 1097 Hello 2019 +1909

UPD2: The (announcement) writters with the highest average number of upvotes, who have written the contest annoucement in at least two rounds.

Handle Average Upvotes Number of Rounds
tourist 1800 3
antontrygubO_o 978 2
Radewoosh 836.6667 3
adamant 826.5 2
viktork 806 2
dreamoon_love_AA 737.5 2
Ashishgup 650.5 2
DarthKnight 565.2857 7
majk 564.6 5
Errichto 545.7143 7

Read more »

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

By ouuan, history, 16 months ago, In English

Want to generate different kinds of trees with simple functions or even a single string? The Tree Generator may be a good choice for you.

You can generate a tree by a single string:

Tree t("ch9,0st10,9"); // a tree consisting of a 10-node chain and a 10-node star at the bottom of it

You can add nodes by simple functions:

t.binary(10, 3); // add a 10-node binary tree with node 3 as its parent

You can shuffle the nodes and edges and output the tree:

t.shuffleNodes();
t.shuffleEdges();
cout << t;

You can customize the random function and the output function so that you can use it with testlib.h or print the edges with weights:

#include "testlib.h"

int myRandInt(int l, int r)
{
    return rnd.next(l, r);
}
randint = myRandInt;

void myOutputEdge(ostream& os, int u, int pa)
{
    os << u + 1 << ' ' << pa + 1 << ' ' << randint(1, 10) << endl;
}
cout << t;

Why don't you try it? Just visit https://github.com/ouuan/Tree-Generator to clone/copy the codes, and read the GUIDEBOOK to learn how to use it.

However, it hasn't been well-tested, so bug reports are welcomed. My English is not very good, so any opinions for guidebook improvement are welcomed, too.

Read more »

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

By ouuan, history, 18 months ago, In English

In the tutorial of 1172E - Nauuo and ODT, I didn't write things on how to maintain subtree information, because I thought it was a popular trick. However, through tmwilliamlin168's comment, I realized that this trick may be not so common in other countries, so I decided to write a blog on it.

This blog will tell you how to maintain subtree information using LCT, with solutions on some problems, so you should know LCT before reading this blog.

Main Idea

The main idea is simple: record the sum of information of "virtual subtrees", where the "virtual subtrees" refers to the subtrees except the one in the Splay.

In the picture, $$$1$$$, $$$2$$$, $$$6$$$, $$$10$$$ are in a Splay, while $$$8$$$ and $$$12$$$ are in another. The "virtual subtrees" of $$$1$$$ is $$$3$$$ and $$$4$$$, the "virtual subtrees" of $$$4$$$ is $$$7$$$ and $$$8$$$, the node $$$8$$$ has no "virtual subtree".

You need to update the information when the "virtual subtrees" changes, usually, when accessing and linking.

An easy example is using LCT to maintain the size of subtrees.

Here are some codes:

struct Node
{
    int fa, ch[2], siz, vir; // father, two children, size of subtrees (including the root), size of virtual subtrees
} t[N];

void access(int x)
{
    for (int y = 0; x; x = t[y = x].fa)
    {
        Splay(x);
        t[x].vir -= t[y].siz; // update the size of virtual subtrees
        t[x].vir += t[t[x].ch[1]].siz;
        t[x].ch[1] = y;
        pushup(x); // update the information of the node x
    }
}

void link(int x, int y)
{
    makeroot(x);
    access(y);
    Splay(y);
    t[x].fa = y;
    t[y].vir += t[x].siz;
}

void pushup(int x)
{
    t[x].siz = t[t[x].ch[0]].siz + t[t[x].ch[1]].siz + t[x].vir + 1;
}

Problems

Some problems are in Chinese, I will translate the statements (in a simplified version).

[BJOI2014] Great Integration

There are initially $$$n$$$ nodes, there will be $$$q$$$ operations in two types:

  1. A x y add an edge between $$$x$$$ and $$$y$$$
  2. Q x y a query, asking how many simple paths are there which go through the edge between $$$x$$$ and $$$y$$$.

It is guaranteed that the graph is always a forest (one or more trees).

Input

n m
m lines of operations
Tutorial
Solution

UOJ #207. Gongjia toured Changsha

There is a tree consisting of $$$n$$$ nodes and a multiset of simple paths $$$S$$$. $$$S$$$ is initially empty. There are $$$m$$$ operations in $$$4$$$ types:

  1. x y u v $$$cut(x, y)$$$, $$$link(u, v)$$$
  2. x y insert the simple path $$$(x, y)$$$ in $$$S$$$
  3. x delete the $$$x$$$-th simple path inserted in $$$S$$$
  4. x y a query, asking if all simple paths in $$$S$$$ go through the edge $$$(x,y)$$$

It is guaranteed that the graph is always a tree.

Input

the id of subtask
n m
n-1 lines of the initial tree
m lines of operations
Tutorial
Solution

1172E - Nauuo and ODT

You can see the problem on Codeforces, and the tutorial is also available here.

Read more »

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

By ouuan, history, 18 months ago, In English

At only age 16, CauchySheep(Mingyang Deng) reached Legendary Grandmaster on Codeforces Round #564 (Div. 1). What's more, he won the first place in the Chinese team selection for IMO2019 and will be a participant of IMO2019.

It's a pity that IMO2019 and NOI2019 (a necessary step in Chinese team selection for IOI) are conflicted in time, and he will probably not be able to participate in IOI2020. However, he's in grade 10 now, so he still has the chance to participate in IOI2021.

Congratulations!

Read more »

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

By ouuan, history, 18 months ago, In English

1173A - Nauuo and Votes

Idea: ouuan

Tutorial
Solution

1173B - Nauuo and Chess

Idea: Sooke

Tutorial
Solution

1172A - Nauuo and Cards

Idea: QAQAutoMaton

Tutorial
Solution

1172B - Nauuo and Circle

Idea: Sooke

Tutorial
Solution

1172C1 - Nauuo and Pictures (easy version) and 1172C2 - Nauuo and Pictures (hard version)

Idea: ouuan

Tutorial
Solution

1172D - Nauuo and Portals

Idea: Sooke

Tutorial
Solution

1172E - Nauuo and ODT

Idea: ODT

Tutorial
Solution

1172F - Nauuo and Bug

Idea: rushcheyo

Tutorial
Solution

We had prepared a problem similar to 1174F - Ehab and the Big Finale before that round, so we needed to prepare new problems in four days. It was in such a hurry that there are some imperfections in our round. Please accept our sincere apology.

Read more »

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

By ouuan, history, 18 months ago, In English

Hi!

We are glad to invite you to take part in Codeforces Round #564 (Div. 1) and Codeforces Round #564 (Div. 2), they will be held on Jun/07/2019 15:05 (Moscow time). The round will be rated for both divisions.

Participants in each division will be offered 6 problems and 2 hours to solve them, including 4 shared problems for both divisions, and one of them has two versions with the only difference in constraints.

The problems were written and prepared by me, Sooke, QAQAutoMaton, ODT, ccz181078, rushcheyo and PinkRabbit.

Great thanks to 300iq for coordinating and testing the round, we enjoyed the experience of preparing a round with him.

Thanks to Um_nik, KAN, isaf27, xht37, ButterflyDew and DKACVenus for testing the round, too.

Of course, thanks to MikeMirzayanov for amazing systems Codeforces and Polygon!

Last but not least, thanks to everyone who participates in this round, for making our efforts meaningful.

Both English and Chinese editorials will be available after the contest.

UPD 1: The scoring distribution will be:

  • Div.2: 500 — 1000 — 1500 — 1750 — (1250 + 1250) — 2750

  • Div.1: 500 — 750 — (750 + 750) — 1750 — 2500 — 2750

UPD 2: Congratulations to the winners!

Div.1:

  1. CauchySheep

  2. maroonrk

  3. WA_TLE

  4. zeronumber

  5. nhho

Div.2:

  1. foreverlasting

  2. wifiiiiii

  3. liuxiao

  4. Joysh

  5. YenSean

UPD 3:

The English Editorial and the Chinese Editorial are published.

Read more »

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

By ouuan, history, 22 months ago, In English

The video is here (uploaded by myself).

Anguei helped me upload it on YouTube.

Thank I_love_Tanya_Romanova for pointing out my mistake of ignoring the inactive users. I have fixed it now.

I get the rating history of each user who is in the top5000 either of the active or the inactive now by Codeforces API. So if a user was in the top10 but is in neither the top5000 of the active nor the inactive now, he will not be included in the historical top10s.

I made the video using Dynamic Ranking Visualization. And the codes written by me is here.

P.S. The numbers change continuously in the video, so the ratings in the picture are not the exact value.

P.P.S Some interesting datas: (count when the top10 changes)

Times in TOP10

Handle Times
tourist 327
Petr 325
rng_58 201
vepifanov 149
wxhtxdy 142
YuukaKazami 141
Egor 130
peter50216 107
yeputons 101
W4yneb0t 90

Times of TOP1

Handle Times
tourist 305
Petr 20
Anton_Lunyov 4
vepifanov 3
dzhulgakov 2
Um_nik 1
mnbvmar 1
Radewoosh 1

Read more »

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

By ouuan, history, 23 months ago, In English

Today I was solving a problem with bitset which needs to find the first set bit (bit with value 1/true). I looked up in C++ Reference but was not able to find a proper function.

Some one else told me that ._Find_first() works (also mentioned in this blog), which is not documented.

I was curious about if there are more undocumented member functions, so I took a look at the source code and found this:

I think the last question is so funny lol

Read more »

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

By ouuan, history, 2 years ago, In English

In the announcement of Codeforces Round #503, there are too many downvotes which are inexplicable. I saw that a comment which was +30 and then changed into -1. What happened? Is there a gang of people downvoting or some people saw the downvotes and joined in it?

I'm a bit afraid of this topic being downvoted too much... But I still think this situation should get a reasonable explanation.

Read more »

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