ouuan's blog

By ouuan, history, 3 weeks 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, 5 weeks 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
  • +78
  • Vote: I do not like it

By ouuan, history, 6 weeks 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, 2 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, 2 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 Школьная индивидуальная олимпиада #3 (ЗКШ 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 - Раунд 3 +2247
2017 806 Codeforces Round #412 (рейтинговый, Div. 1, по задачам VK Cup 2017 Раунд 3) +2247
2017 807 Codeforces Round #412 (рейтинговый, Div. 2, по задачам VK Cup 2017 Раунд 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, 3 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, 5 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);
    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
  • +161
  • Vote: I do not like it

By ouuan, history, 5 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, 5 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, 5 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, 9 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, 10 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, 15 months 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