DeadlyCritic's blog

By DeadlyCritic, history, 6 months ago, In English

Tell me how you think.

Read more »

 
 
 
 
  • Vote: I like it
  • -19
  • Vote: I do not like it

By DeadlyCritic, history, 13 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, 14 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 23.06.2020 17:05 (Московское время) ($$$\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, 14 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, 15 months 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, 16 months 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.

Windows Package(50 MB) Linux Package(45 MB)

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, 16 months 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, 16 months 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, 17 months 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