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

Difficulty Ratings Idea Creativity: 3/5 Techniques Used: 2/5 Implementation : 3/5 Link English Statement You are given a string of length $1 \le N \le 1e5$ that only consists of digits $1$~$9$. Permutate the given digits to minimize the maximum integer that can be formed by taking a substring of length $K$. Solution Firstly, it is obvious that you can move the largest K-1 digits to the back of the string and ignore them. Now, the $K$ is no longer significant and you only have to minimize the lexiographically largest non empty-suffix (here empty string is lexicographically largest :P). So, let's imagine you have a bunch of strings $s$ where you have to stick them together in some ways to minimize the maximum suffix. Then, you should repeat the following step until only one string remain: append the lexicographically smallest string to the back of the lexicographical string. I uh..., have tried to come up with a proper proof for a while, but I couldn't... So, pr

Difficulty Ratings Idea Creativity: 4/5 Techniques Used: 3/5 Implementation : 3/5 Author rated this task as the 5/6th hardest task out of 11 tasks. Yet it has 2 solves in contest. Link English by 300iq Statement Wang Xiuhan has an initially empty undirected graph on $1 \le n \le 3e5$ vertices. Each vertex $i$ has a weight $0 \le w_i \le 1e6$ Also, he has $1 \le m \le 3e5$ tuples $(a_i,b_i,s_i)$, where $1 \le a_i,b_i \le n$, $a_i \neq b_i$, and $0 \le s_i \le 1e6$ After that, he starts the following process: - If there is no such i that ai and bi lie in different connected components of the graph and (total weight of vertices in the component of $a_i$) + (total weight of vertices in the component of $b_i$) ≥$s_i$, end the process. - Otherwise, choose the smallest such $i$, add an edge between $a_i$ and $b_i$ to the graph, write this $i$ in the notepad, and repeat the process (but now on the larger graph). After the process was completed, a misfortune happen

Difficulty Ratings Idea Creativity: 4/5 Techniques Used: 2/5 Implementation : 2/5 OP hard interactive... It is modified from an MO practise problem. I put this picture here so that spoilers dont appear in preview... Please tell me how to do this properly. Link Simplified Chinese by tEMMIE.w.=moorhsum=peehs_moorhsum=Cauchysheep=newbiedmy Simplified Statement There is a complete undirected graph of size $n$, where each edge is colored in either red or blue. Lets denote $(u) - (v)$ as the edge between $u$,$v$. It is given that $(i) - (i+1)$ is red for $1 \le i < k$. In each query, you can specify two nodes, and the interactor will return the color between the pair of nodes. You can make only $q$ queries. Find a path with $k$ edges such that the color of all edges on the path is the same, and the path is simple (visits $k+1$ vertices in total). $q=2k$, $\frac{3k}{2} \le n \le 2k$, $1 \le k \le 2000$. Solution Let's assume $n = \lceil \frac{3k}{2} \rceil$. We can s