Solving competitive programming problems

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

Difficulty Ratings Idea Creativity: 3/5 Techniques Used: 3/5 Implementation : 2/5 Link Simplified Chinese , Japanese Statement There is an $N \times M$ grid, each cell is a square. We draw a diagonal line (can be in one of both directions) in each cell and split it , and now we put a sandwich in each of the $2NM$ isosceles right angled triangles. We can eat a sandwich $X$ if 1) There are no sandwiches $Y$ adjacent to $X$ on both of the two shorter sides or 2) THere are no sandwiches $Y$ adjacent to $X$ on the longer side. Find out for each sandwich, the minimum number of sandwiches that you need to eat so that you can eat it, or output -1 if impossible. $N,M \le 400$. Solution It is hard to make use of the grid property, so lets first model this problem into a graph problem. Consider we make two nodes for each square, one for each sandwich out of the two being eaten first. Obviously if you have eaten one sandwich in the square, you would eat the other immediately