### animeFORever's blog

By animeFORever, 8 months ago,

It's one of the most beautiful dp I ever used. I'm going to explain it with an example.

Problem: 1265E

Solution: suppose $e_i$ equals the expected number of days that we stop.
$e_i = p_i * e_{i + 1} + (1 - p_i) * e_1 + 1$
$e_n = (1 - p_i) * e_1 + 1$

So how to update $e$?! :D
We will change how we show numbers. You know how we show complex numbers (if you don't learn it here), we are going to use the same idea.
Each number consists a part that is $e_1$ and another part that is a Real number(in this problem you can change it to integer when using modulo).
We show each number with $x$ and $y$ such that the number is equal to $x * e_1 + y$. So we use this idea and start updating $e$ backward.
Then we will get $e_1 = x * e_1 + y$ and now we can get $e_1$ as an intiger.
$e_1 = y / (1 - x)$

Any other problem that uses the same idea, please mention. :D

• +100

By animeFORever, 9 months ago,

Hi, let's get straight to the topic.

#### ==================

Problem : given an array a of size n. you are given q queries and in each queries you are given two intigers l and r (${l \le r}$) and you are supposed to print the sum of ${a_l}, {a_{l + 1}}, ..., {a_r}$.
Very easy huh?
First, let's solve it with time complexity $O(q * n)$. why?.
suppose we have a start pointer and an end pointer on the array and a value cur such that cur is equal to the sum of segment $[start, end]$, now we for each query, we are going to reach r with end and reach l with start and change cur such that after reaching both start and end to l and r, cur will be equal to the sum of segment $[l, r]$.

suppose $end < r$ : we can change end to end + 1 and update cur, just add $a_{end + 1}$ to cur.

We can use the same method to decrease end and change start and now we have an algorithm of complexity $O(n * q)$. what if for each query we know that given r will be bigger or equal than the r given before. total complexity will still be $O(n * q)$ but total changes of end will be $O(n)$ and that's good. even if queries didn't give us r in increasing order we could always sort queries base on their r.

now for decreasing the total changes of start what can we do?
let's decompose a to blocks of size S. what if we sort the queries such that for queries in each block have increasing r (You can see HERE for exact sorting method). let's calculate time complexity.

For the i-th block suppose we change end at most $O(n)$ times, so total changes of end will be $O((n / S) * n)$.
Suppose we have $q_i$ queries that have l in the i-th block.
For the i-th block, we change start at most $O(q_i * S)$. so total changes of start will be $O(S * q)$.
We do $O((n / S) * n + S * q)$. with $S = n / \sqrt q$ we get $O(n * \sqrt q)$ and that's really good. now you can apply the method described here with problems that are much harder and good luck.

I suggest before reading Mo with update, you solve some of the problems below.

#### ==================

Problem : The same problem before with diffrence that we have change query. You are given pos and $val$ and that means you have to change $a_{pos}$ to $val$.

What will happen if we use the same method that we used above? We get time complexity $O(q * n * \sqrt(q))$ because before each query we have to do some updates or undo some updates.
That's not good enough. Here is the main idea for what we will do:

Decompose array into blocks of size S.(pretty similar to the last one huh?) and sort queries that ask for some sum, firstly based on the block which l lies in and secondly by the block that r lies in and finally by t. t is the number of the update queries before this query.

now let's calculate the time complexity :

total changes of the start: for the i-th block that l lies in it, the start will change $O(q_i * S)$ ($q_i$ have the same definition as before). So total changes of the start will be $O(S * q)$.
total changes of the end: for the i-th that l lies in it, and for the j-th block that r lies in it, the end changes will be $O(q'_{i, j} * S)$. ($q'_{i, j}$ is number of queries that l of them lies in block i and r of them lies in block j). So the total change of the end for a fixed block for l is $O(S * q)$.
Changes of the end when changing between blocks of l is $O(n)$ and therefore we get total changes between blocks of the end is $O({n ^ 2} / S)$. So the total change will be $O(S * q + {n ^ 2} / S)$.
total updates we have to do and we have undo: because for the i-th block of l and the j-th block of r, t is in increasing order the total changes of t for these two fixed blocks is $O(q * {n ^ 2} / {S ^ 2})$.

TOTAL COMPLEXITY: from above we get total complexity of $O(S * q + S * q + {n ^ 2} / S + q * {n ^ 2} / {S ^ 2})$ and that is equivalent to $O(S * q + q * {n ^ 2} / {S ^ 2})$, If $S = {n ^ {2 / 3}}$ we get $O(q * n ^ {2 / 3})$.

FACT : with S = $(2 * n ^ 2) ^ {1 / 3}$ you will get best complexity.

Here is some problems (Sorry I didn't find many :) ) :
Primitive Queries
Machine Learning (AliceWalkingOutOfHerLife)
Candy Park
Any suggestion or problem, please comment :D.

• +120

By animeFORever, 10 months ago,

Problem : You have an array a of size $n$. for each $i$ (${i \le n}$) you have to find maximum $j$ such that ${1 \le j < i}$ and ${a_j > a_i}$ and if there is no $j$, consider the answer for $i$ equal to $0$, solve the problem with total complexity ${O(n)}$.

Solution 1 : Of course there is an easy solution using stack.

for (int i = 1; i <= n; i++) {
while (s.size() && a[s.top()] <= a[i])
s.pop();
if (s.size())
L[i] = s.top();
s.push(i);
}


Solution 2 : About 2-3 month ago I suggested a dp solution for this problem and i never thought that it would be ${O(n)}$ but here I am sharing it with you :D
${dp_i = }$ answer for i.
So how can we update this dp?!, let's check maximum $j$ that can be the answer for $dp_i$. It's obvious that if ${a_{i - 1} > a_i}$ the answer is $i - 1$.
what if ${a_{i - 1} \le a_i}$ : then the answer isn't in range $(dp_{i - 1}, i]$ so the next number we should check is $dp_{i - 1}$ and if it wasn't answer that we need we should check $dp_{dp_{i - 1}}$, and then $dp_{dp_{dp_{i - 1}}}$ and so on.
Do you see the pattern?! :D

int find_ans(int i, int j) {
if (!j)
return j;
return (a[j] > a[i]? j: find_ans(i, dp[j]));
}
for (int i = 1; i <= n; i++)
dp[i] = find_ans(i, i - 1);


some problems :

Psychos in a Line
These problems aren't necessarily the exact problem but the main idea is same.

• +75

By animeFORever, 10 months ago,

• +167

By animeFORever, 11 months ago,

Hello again :D

Here is my DSU struct in c++ because there isn't any in codeforces. I added some features like making a DSU equal to another or clearing DSU.

use it like :

DSU tmp(n);

Any suggestion comment below :D

UPD1 : I added more features

UPD2 : Now you can merge two DSUs. (like if you want to add every edge in graph A to graph B) https://paste.ubuntu.com/p/Xz3BNBGcN4/

• +19

By animeFORever, history, 13 months ago,

Hi, From the first that i started CP i always liked problems that could be solved with some random in it, so i searched a lot but didn't find a random problemset.

now i'm making one :D

https://vjudge.net/contest/323610

UPD1: so after adding many problems the last problemset got filled so here more problems. :D

https://vjudge.net/contest/323731

• +48

By animeFORever, 15 months ago,

Here is my bigint struct in c++.

enjoy it :))

upd1 : I added bitwise operator and shift. here is new link.

https://paste.ubuntu.com/p/FdxZ3QMG9h/

upd2 : I added popcount, ctz and tutorial to how to use change base function :D.

you can use the new code below :

https://paste.ubuntu.com/p/ZcMgDhvRhv/