Solving competitive programming problems

I will stop posting content for a while because gugugugugugu

Difficulty Ratings Idea Creativity: 4/5 Techniques Used: 3/5 Implementation : 3/5 Link Simplified Chinese by zhangzy Statement Given an undirected graph with $n \le 1e4$ vertices and $m \le 1e6 edges$, determine if there are two simple cycles of same size in the graph. Solution We will exhausive search for all cycle lengths for every edge biconnected component sepeartely. Now assume the graph is edge-biconnected. According to RMM 2019 Q3 , when $M-N>c \sqrt{NlgN}$ for some constant $c$, the answer must be Yes. (By instinct if $M-N$ is big it would obviously fail, so you can just guess this $M-N>magic$ and put the largest $magic$ that your solution can run in time.) Now, we build a condensed graph by repeatedly contracting nodes of degree $2$. As there are no degree 1 vertices (the graph is biconnected), the graph we have now has both $|V|$ and $|E|$ in $O(\sqrt{NlgN})$. Consider we run an exhausive search for all cycles. We pick a vertex and assume that the cyc

Difficulty Ratings Idea Creativity: 2/5 Techniques Used: 3/5 Implementation : 3/5 Link Simplified Chinese Japansese by semiexp Statement Imagine you have a range $[A,B]$. An operation is moving to left into $[A-1,B-1]$ using 1 cost, or moving to right into $[A+1,B+1]$ using 1 cost. You can do any operations at any number of times and each operation takes 0 time. Then, there will be $N$ events happening, in event $i$ you have to move your range to cover a point $x_i$. Let $f([A,B])$ be the minimal cost to handle the $N$ events. Given $Q$ queries of $[A_j,B_j]$, find out $f([A_j,B_j])$ for each of them. $N,Q \le 2e5$. Solution So I assume you realise that moving greedily (move towards the point you have to cover if you haven't) is optimal. Firstly, lets compare $f(0,B-A)$ and $f(A,B)$. Let's find the first position $i$ such that there exist $j < i$ that $|x_i-x_j|>B-A$. Two observations are to be made: 1) You will end up at the same position after the

Difficulty Ratings Idea Creativity: 4/5 Techniques Used: 3/5 Implementation : 2/5 By xudyh Statement Given $n \le 1e7$, find $s$ distinct integers $1 \le a_1,a_2, \cdots ,a_s \le n$ such that: -For all pairs $(a_i,a_j)$ such that $i < j$, their XOR sum should be distinct. -$s \ge \lfloor \sqrt{0.5n} \rfloor$ Solution Well known in Poland So obviously we pick the minimum valid $s$. As $s$ is $O( \sqrt{n})$, we would imagine splitting each integer into 2 parts, something like each integer is $u_i \times 2^q+v_i$ where $0 \le u_i,v_i \lt 2^q$, and all $u_i,v_i$ is distinct. Then we just have to guarentee that if $u_w \oplus u_x = u_y \oplus u_z$ then $v_w \oplus v_x \neq v_y \oplus v_z$. ( $\oplus$ is xor) Let $q$ be the smallest integer such that $2^q \ge s$. Consider we create a function $f(x)=y$ that $0 \le x,y \lt 2^q$. Our final set will be $i \times 2^q + f(i)$ for all integers $i$ in $[0,s)$. It is easy to see that all integers generated is $\le N$. So now