A Few Randomization Problems

Difficulty Ratings

Idea Creativity: 3/5(Some are pretty geniosity)
Techniques Used: 2/5
Implementation : 2/5

Resources

Uh, there is not much techniquees in Randomization. But basically you must know Blogewoosh #6 trick.

Task 1

Simplified Statement

CF 1240E Note: This problem is not easy at all.

Solution

Read the editorial lol. The key to optimize from two logs to one log is to use blogewoosh trick, which is kinda surprise to me(?)...

Task 2

By alex20030190

Simplified Statement

Given a permutation A of length $N \le 100000$ and an array B, sum $f(l,r)$ for all pairs of $1 \le l \le r \le N$, where $f(l,r) = M1(l,r) \times M2(l,r) \times B[r-l+1]$, and $M1(l,r)$, $M2(l,r)$ means the maximum and second maximum in $A[l..r]$ respectively. It is guarenteed that A is randomly generated.

Solution

It is quite geniosity. The solution is to pick the maximum of array, compute sum for all ranges that included the value, then divide and conquer. The complexity analysis is similar to quick sort.

Task 3

Problem Link

Link in simplified chinese by jiry_2

Simplified Statement

Maintain an array of length $N \le 100000$ with $Q \le 1000000$ updates and queries. Initially, each value of the array is a random number which is in $[0,100000]$.
There are three types of operations:
C: Generate random by given seed $p,y$, and set $A[p]=y$. $y$ is in $[0,100000]$.
R: Generate random by given seed $l,r$, swap if $l \gt r$, and set $A[p]=100000-A[p]$ for all $p$ inside $[l,r]$.
Q a b c: Generate random by given seed $l,r$, swap if $l \gt r$, and find the maximum value of $a \times p + b \times A[p] + c \times p \times A[p]$, where p is inside $[l,r]$.

Solution

So basically you realise that if $p \le q$ and $A[p] \le A[q]$ then point $p$ is not optimal. From blogewoosh trick you can know that there are only $O(logN)$ points that are useful. Therefore, you just need a segment tree storing minimum and maximum of a range, then you can search all useful points and answer queries in $O(log^2N)$. (btw this problem somehow had no solves in opencup idk why maybe they trolled with constants, you can find this problem in prime new year contest 2018).

Task 4

By Warsaw U.

Simplified Statement

Fixed $1 \le N \le 300,1 \le M \le 400$, randomly generate $M$ pairs of $(x,y)$ where $x \lt y$ and add edge $x \rightarrow y$. Then the $N,M$, the graph and $0 \le k \le 4$ is given to you. You can remove $k$ vertices and also the edges incident to them in any direction. You want to minimize the longest path in the DAG. Find the smallest length you can make.

Solution

As the graph is random, the length of longest path is around $O(\sqrt{M})$, and it is optimal remove at least one point from one longest path, so you just exhaust and recursion. The complexity is $O(M^{\frac{k}{2}+1})$... Sometimes you have to find/guess the thing to use which is small when randomized. For example, the expected length of Longest Increasing Subsequence of array is $O(\sqrt{N})$, where the proof is not simple.

Comments

Above are problems that have random written in the statement. Not all randomization problems are like this. Next week I will talk about problems that are not like this.