DeadlyCritic's blog

By DeadlyCritic, history, 5 months ago, In English
$$$~-\text{In the name of God}~-$$$

Hi

I saw my contribution going down so I decided to write a decent blog, explaining super advanced stuff, funny enough, I don't have the knowledge nor have the patience to write such a blog, so I wrote this blog explaining some applications of Rerooting Technique. But I was tired and lazy so here is a not quite usable nor perfect blog for whoever likes the Rerooting Technique(me for instance).

Note that RT stands for Rerooting Technique, DP stands for Dynamic Programming, RHS stands for Right Hand Side of an equation, LHS stands for Left Hand Side of an equation. (I assumed the reader is familiar with basics of math, trees, DFS and BFS)

Also I recommend reading my previous blog $$$\texttt{before}$$$ reading the rest of this blog:

Online Query Based Rerooting Technique

I recently solved the following problem for second or third time (which I believe is a very classic problem):

Given a tree, calculate $$$\displaystyle \sum_{u, v} d^2(u, v)$$$ (where $$$u$$$ and $$$v$$$ are two vertices not necessarily distinct, and $$$d(u, v)$$$ is the distance from $$$u$$$ to $$$v$$$ in the given tree, also $$$d^2(u, v) = d(u, v) \cdot d(u, v)$$$).

Trivial solution is $$$O(n^2)$$$, where for each vertex $$$u$$$ we use BFS and calculate $$$d(u, v)$$$ for all $$$v$$$. Then we add up $$$d^2(u, v)$$$ for all $$$u$$$ and $$$v$$$. Now we try to solve the problem in $$$O(n)$$$.

One can solve this problem using 3-4 DPs (and potentially using RT), which is what we are going to talk about, and then extend it to death.

To solve this problem, we need the following fact ($$$a_i$$$-s are some variables, in this problem they are $$$d(u, v)$$$ for some $$$u, v$$$):

$$$\sum_i (a_i+1)^2 = \sum_i a_i^2+2a_i+1 = \sum_i a_i^2 + 2\sum_i a_i + \sum_i 1$$$

This fact says that if we know all the sums in the RHS we can find the sum in LHS with the aforementioned equation, which is pretty useful.

Now we can calculate three DPs for each vertex $$$u$$$ (also $$$v \in subree_u$$$) using the fact above:

  • $$$dp_u = \sum_{v} d^2(u, v)$$$
  • $$$sum_u = \sum_{v} d(u, v)$$$
  • $$$size_u = \sum_{v} 1 = \text{size of }subtree_u$$$

One can simply calculate $$$sum_u$$$ and $$$size_u$$$. To calculate $$$dp_u$$$ we can do this(where $$$c \in children_u$$$):

  • $$$dp_u = \sum_c dp_c + 2\sum_c sum_c + \sum_c size_c$$$

After that $$$dp_r$$$ where $$$r$$$ is the root is equal to $$$\sum_v d^2(r, v)$$$ where $$$v$$$ is any of the vertices. So if we do the same dp from all possible roots, then answer to the problem is the sum of $$$dp_r$$$ when $$$r$$$ is the root with $$$O(n^2)$$$ time complexity. However, one can realize that we can use RT to solve the problem in $$$O(n)$$$, and I'm not going through that.

Now we solved the last problem in $$$O(n)$$$, what do we do next? EXTEND IT TO DEATH:

You are given a tree, and a polynomial $$$P$$$ of degree at most $$$k$$$. Calculate $$$\sum P(d(u, v))$$$.

Again we can calculate $$$d(u, v)$$$ for all $$$u$$$ and $$$v$$$, then add up $$$P(d(u, v))$$$-s, overall time complexity will be $$$O(n^2k)$$$ if done properly. I would hope for a $$$O(nk^2)$$$ time complexity looking at the second solution of the previous problem.

First define:

  • $$$P_0 = x^0$$$
  • $$$P_1 = x^1$$$

$$$\;\;\vdots$$$

  • $$$P_k = x^k$$$

It's quite trivial that if we could calculate $$$S_i = \sum_{u,v} P_i(d(u, v))$$$ for $$$0 \le i \le k$$$, then we can calculate $$$\sum_{u, v} P(d(u, v)) = a_0S_0+a_1S_1+\dots+a_kS_k$$$

Let's try to extend the fact we used in the second solution. We want to be able to calculate $$$P_i(x+1)$$$ using $$$P_j(x)$$$-s. If we were able to do so we could define $$$k+1$$$ dp-s and do the rest pretty much the same as the first problem. It's trivial we can calculate $$$P_i(x+1)$$$ using $$$P_j(x)$$$-s where $$$0 \le j \le i$$$, same can be said about $$$P_i(x-1)$$$:

$$$P_i(x+1) = (x+1)^i = C(i, 0)x^01^i + C(i, 1)x^11^(i-1) + \dots + C(i, i)x^i1^0$$$

So if we have some some integers $$$a$$$, then if we know $$$\sum_j P_i(a_j)$$$, we can calculate $$$\sum_j P_i(a_j+1)$$$, and $$$\sum_j P_i(a_j-1)$$$, so we can use this to first find all dp-s when tree is rooted at a vertex, then use RT and calculate dp-s for different roots as well, and so, problem solved in $$$O(nk^2)$$$.

This problem can be solved in $$$O(nk)$$$ as well, as nor mentioned in the comments section (thanks!). To do that we need to change the definition of $$$P_i$$$, we can achieve $$$O(nk)$$$ if we define $$$\displaystyle P_i(x) = x(x-1)\dots (x-i) = \prod_{j=0}^i x-j$$$, so we'll have $$$P_i(x+1) = \frac{P_i(x)(x+1)}{x-i}$$$. However I don't fully understand how we find $$$P(x)$$$ using $$$P_i$$$-s, but we can assume there's a mathematical equation we can use or something, idk.

Sorry for skipping many details, feel free to ask any questions and/or discuss and/or give any recommendation/opinion in the comments section.

Yet it's not enough extension, what if it wasn't a tree but another special graph, or a graph in general.

Read more »

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

By DeadlyCritic, history, 23 months ago, In English

A. FashionabLee :

Invented by DeadlyCritic.

Brief Solution
Complete Proof
Python solution
C++ solution

B. AccurateLee :

Invented by DeadlyCritic.

Brief Solution
Complete Proof
Python solution
C++ solution

C. RationalLee :

Invented by DeadlyCritic and adedalic.

Brief Solution
Complete Proof
Python solution
C++ solution

D. TediousLee :

Invented by DeadlyCritic.

Brief Solution
Complete Proof
Python solution
C++ solution

Challenge : Try solving problem D for $$$n \le 10^{18}$$$. (no matrix-multiplication)

E. DeadLee :

Invented by DeadlyCritic.

Hints
Brief Solution
Complete Proof
Python solution
C++ solution

F. BareLee :

Invented by DeadlyCritic and AS.82.

Brief Solution
Complete Proof
Python solution
C++ solution

Read more »

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

By DeadlyCritic, history, 23 months ago, In English
$$$~-\text{In the name of God}~-$$$

Hi community,

I'm glad to invite you to my first contest, Codeforces Round #652 (Div. 2) which will be held at Jun/23/2020 17:05 (Moscow time) ($$$\text{notice the unusual time}$$$). The problems are mainly prepared and invented by me. The round is rated for participants with rating strictly less than $$$2100$$$, others are able to take part in the round out of competition. You will be given $$$2$$$ $$$\text{hours}$$$ to solve $$$6$$$ $$$\text{problems}$$$.

Firstly I'd like to thank adedalic for coordinating and reviewing the round, as well as helping with many different things.

I'd like to thank antontrygubO_o, physics0523, McDic, Ashishgup, dannyboy20031204, Kuzey, SinaSahabi, FieryPhoenix, ma_da_fa_ka, ITDOI, AM_I_Learning, awoo, lynmisakura, JustasLe and ArimeZ for testing the round and giving valuable feedback.

Also I'd like to thank coauthors, amiralisalimi, AS.82 and davooddkareshki for helping me with inventing and choosing the problems.

Finally, thanks to MikeMirzayanov for very nice and convenient Codeforces and Polygon platforms.

I wish you all will find the problems interesting, thank you for participating, and good luck!

$$$\text{Scoring distribution : } \; 500 ~- 1000 ~- 1500 ~- 2000 ~- 2500 ~- 3000$$$

$$$\textbf{UPD}$$$ : Editorial is out

Read more »

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

By DeadlyCritic, history, 23 months ago, In English

In the name of God;

Hi, here I want to suggest some random functions for Testlib.

Testlib has nice random functions, here I want to suggest some other ones. The first and the second random functions are available in testlib, but the rest are not.

1, $$$\text{rnd.next(l, r)}$$$, it will return a random number in range $$$l$$$ to $$$r$$$ with equal weights :

2, $$$\text{rnd.wnext(l, r, w)}$$$, it will return a random number in range $$$l$$$ to $$$r$$$ with monotonically increasing/decreasing weights depending on $$$w$$$ :

If $$$w = 0$$$ then it will be equal to $$$\text{rnd.next(l, r)}$$$.

If $$$w > 0$$$ :

If $$$w < 0$$$ :

3, $$$\text{rnd.cnext(l, r, c)}$$$, it will return a random number in range $$$l$$$ to $$$r$$$ :

If $$$c = 0$$$ then it will be equal to $$$\text{rnd.next(l, r)}$$$

If $$$c > 0$$$ :

If $$$c < 0$$$ :

4, $$$\text{rnd.cnext(l, r, c1, c2)}$$$, it will return a random number in range $$$l$$$ to $$$r$$$ like $$$\text{rnd.cnext(l, r, c)}$$$, but its not centered around $$$\frac {r+l} 2$$$ : ($$$c1 \ge 0$$$ and $$$c2 \ge 0$$$)

About the implementation of $$$\text{cnext(l, r, c1, c2)}$$$, its as follow :

  1. Choose $$$c1+c2+1$$$ random numbers in rage $$$l$$$ to $$$r$$$ and sort them.

  2. Return $$$c1+1$$$-th one.

As you can see if $$$c1 = c2$$$ then its equal to $$$\text{cnext(l, r, c1)}$$$.

If $$$c1 = 0$$$ then it will be equal to $$$\text{wnext(l, r, -c2)}$$$, if $$$c2 = 0$$$ then it will be equal to $$$\text{wnext(l, r, c1)}$$$.

Please share your suggestions in the comment section.

Read more »

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

By DeadlyCritic, history, 2 years ago, In English

We have an array( $$$a$$$ ) of length $$$n$$$, all the elements are less than or equal to $$$n$$$, then we have to answer $$$q$$$ queries, each will be three numbers $$$x$$$, $$$l$$$, $$$r$$$, then you have to print $$$\displaystyle\sum\limits_{l \le i mod x \le r}a_i$$$, i.e print the sum of all $$$a_i$$$ for $$$1 \le i \le n$$$ and $$$i$$$ mod $$$x$$$ is in range $$$[l \cdot \cdot r]$$$.

$$$0 \le l \le r < x \le n$$$

Then what if we had queries to add a range?

The first query can be changed a little bit, it can be like we have $$$k$$$, $$$x$$$, $$$l$$$, $$$r$$$, then print the same number but with $$$i > k$$$.

$$$0 \le k < n$$$

Please share the solutions.

Read more »

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

By DeadlyCritic, history, 2 years ago, In English

Halo :D!

Story: It was 4 AM and I was unable to sleep so I brought you a nice trick and a couple of problems to practice it.

Introduction

(Our DP changes if we change the root of the tree, otherwise it won't make any sense to use this trick)

Let's say we want to find $$$dp_v$$$ for every vertex in a tree, we must be able to update $$$dp_v$$$ using the children of vertex $$$v$$$. Then the trick allows you to move the root from a vertex to one of its adjacent vertices in $$$O(1)$$$.

Implementation

First, calculate DP when the root is some vertex $$$rat$$$. Its obvious that if we change root $$$r$$$ to one of its adjacent vertices, $$$v$$$, then only $$$dp_r$$$ and $$$dp_v$$$ can change, so that we can update $$$dp_r$$$ using its new children and last $$$dp_r$$$, also $$$dp_v$$$ can be updated the same way. It really depends on the DP.

Note:

Don't iterate over children of vertices when moving the root, it will be $$$O(\sum\limits_v\binom{d_v}{2})$$$ and $$$W(n^2)$$$ so just don't. ($$$d_v$$$ is the degree of vertex $$$v$$$)

Now being able to move the root with distance one, we will run a DFS from $$$rat$$$, and move the root with DFS.

See the semi-code below, i hope it helps for better understanding:

Semi-code

Problems

I can't open some of the problems so there is no solution for them, sorry.

You can read the same trick here, also the site has some problems.

Problem1 Solution

Problem2

Problem3 Solution

Problem4

Problem5 Solution

Probelm6 Solution

Please comment problems that can be solved using this trick.

Advanced

Let's say that the problem has online queries, such that each query gives two vertices $$$r$$$ and $$$v$$$ and wants you to calculate $$$f(r, v)$$$, it's equal to $$$dp_v$$$ when the root is $$$r$$$. It can be solved with rerooting + ancestors binary lifting, it will answers each query in $$$O(Q*log_2n)$$$ time($$$O(log_2n)$$$ for binary lifting), and also $$$O(n*log_2n)$$$ precalculation.

So lets see how it works, for every edge($$$v \to u$$$) find $$$dp_v$$$ if the root is $$$u$$$ and $$$dp_u$$$ if the root is $$$v$$$, it will take $$$O(n)$$$ time and $$$O(n)$$$ memory, and also for each vertex $$$v$$$, store $$$f(v, v)$$$. Then if the query is in form $$$v$$$ and $$$v$$$(i.e. it wants to find $$$dp_v$$$ such that the tree is rooted at vertex $$$v$$$ itself) then the answer will be $$$f(v, v)$$$, which is calculated in advance, otherwise the problem is reduced to the following problem:

You are given two vertices $$$r$$$ and $$$u$$$$$$(u \ne r)$$$ what is the second vertex in the unique path from $$$u$$$ to $$$r$$$(it means we want to find out which vertex is adjacent to $$$u$$$ and is the closest to $$$r$$$).

This problem can be solved using binary lifting, if $$$u$$$ is not an ancestor of $$$r$$$, then the answer is $$$u$$$'s parent(the root is vertex $$$rat$$$), otherwise, move $$$r$$$ using binary lifting until it's depth is equal to $$$u$$$'s depth plus 1, it can be done in $$$O(log_2n)$$$, let the answer to the reduced problem be $$$z$$$, then the answer to the whole query is equal to $$$f(z, u)$$$ such that $$$z$$$ is adjacent to $$$u$$$, we have already calculated it.

See the semi-code below, i skipped some parts so i will use $$$moveto(nw,\,u)$$$ to move the root from $$$nw$$$ to $$$u$$$, $$$f(r, u)$$$ for $$$dp_u$$$ when the root is $$$r$$$ and $$$rise(r,\,u)$$$ to find the ancestor of $$$r$$$ with depth equal to $$$depth_u+1$$$ in $$$O(log_2n)$$$.

Semi-code

I tried to add a problem from polygon for the advanced part, the problem is completed but I couldn't bring it to Codeforces, but I give you the link for problem's package, it includes 50 tests, validator and checker, main correct solution and problem statement, you can try running them in polygon.

Here is the link to a group, where I added the mashup which contains the problem:

link

Here is the complete implementation for the topic, $$$dp[u]$$$ is the size of the subtree of $$$u$$$ here.

Solution

I used map to store the data, so the solution is a little slower than expected.

I hope it will help you with solving DP-Tree problems.

Thanks for your attention.

Read more »

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

By DeadlyCritic, history, 2 years ago, In English

Nowadays tuns of people are in quarantine because of covid-19, so it increased visitors of lots of sites, including CF and caused CF' hosts to overload. So what should we do? In the time that we are bored of staying home and CF staffs(and problem setters) are doing they're best to bring us nice contests, what should we do to help them?

I know that some games' servers brought a feature that you can(if you want) use your computer as a host to help them(specially in Minecraft servers, they give you in-game items if you help them for example). I know it's a little forbidden to use this method but i think it will be much better if we could help CF that way, but it needs staffs attention to make it happen. Its a hard-to-do work but still worth it.

It can be used for example when CF servers are down, or they are overloading(it happens sometimes that lots of codes are submitted and are waiting for judgment), but sadly it will be harder to use this method in online contests, but truly a way to stop queueforces specially in system testing time after and normal times.

I believe lots of people are ready to help CF that way. Please let me know if you have any idea about how to help CF and decrease queueforces(not only after contests).

Please comment below your ideas.

Read more »

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

By DeadlyCritic, history, 2 years ago, In English

The issue is as follow :

It happens when we(me and some of my friends) try to login to our account, after filling the boxes and pressing the button, then it shows a page saying the following page is not found, eror 404(i added an image below). For example it always happens when i try to enter my codeforces account using steam's in-game browser, and sometimes when using opera browser, it also happens when trying to use my gmail to login. Also it always happens when my friend try to enter his account using his mobile phone.

I hope it helped codeforces staffs to improve the site.

Its fixed now, really appreciate it, now i can play and code in the same time :D.

News coming up, i asked my friend to check if he still has the issue, the answer is yes, its fixed for me but sadly not for him, i hope response from staff, thanks in advance.

Read more »

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

By DeadlyCritic, history, 2 years ago, In English

Who can see the comments in contest proposals? are they public? I think only authors and coordinators can see the comments on contest proposals, am i right?

Read more »

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