Solving competitive programming problems

Difficulty Ratings Idea Creativity: 4/5 Techniques Used: 2/5 Implementation : 2/5 When I asked people how to solve this problem they said its treap, but when i asked for details they run away smh... It is not a treap problem... Statement You are moving in a Cartesian plane. At the beginning you are at $(0, 0)$, and your target is $(n, m)$. Once you are at $(x, y)$, you can move to the point $(x, y + 1)$ with the cost $A_x$, or move to the point $(x + 1, y)$ with the cost $B_y$. Given the sequences $A$ and $B$, your task is to find out the minimum cost from $(0, 0)$ to $(n, m)$. $n,m \le 1e6$ Solution So the problem is equivalent to having costs on each line and find shortest path. Obviously it is beneficial to walk on lines with small cost. Lets define $x_{min}$ to be the x-coordinate with smallest cost, and $y_{min}$ to be the y-coordinate with smallest cost (tiebreak arbitarily). Then, we can conclude that the optimal path passes through $(x_{min},y_{min})$. It is not h...

Difficulty Ratings Idea Creativity: 3/5 Techniques Used: 4/5 Implementation : 3/5 This time I will share some standard tricks which I learnt recently. Simplified Statement You have $N \le 1e6$ chocolates, each having value $ a_i 1) Their intersection is empty set. 2) The xor sum of elements in $A \cup B$ is $0$. Find modulo $998244353$. Solution This problem screams Fast Walsh-Hadamard Transform (FWT). However, it is not obvious how to use it. For simplicity, let's define some symbols. -$f(A)$ is the FWT of $A$. -$f^{-1}(A)$ is the inverse FWT of $A$. -$A \oplus B$ is the xor-convolution of $A$ and $B$. -$A \cdot B$ is the dot-product of $A$ and $B$. So we know that -$f^{-1}(f(A) \cdot f(B)) = A \oplus B$ Also some properties are -$f(A+B)=f(A)+f(B)$ (Same holds for $f^{-1}$ too.) -$f^{-1}(f(A))=A$ So lets see how to use this. Define $A_i$ to be the array where all values are $0$ except $A_i[0]$, which is $1$ and $A_i[a_i]$, which is $2$. Then, the answe...

Difficulty Ratings Idea Creativity: 3/5 Techniques Used: 3/5 Implementation : 1/5 This is the Q9 of "Few randomization problems series" Dude I spent 10 hours on this problem with no progress... Statement (not simplified) You are given a set $A$ of $n$ different integers. You need to find a subset $S$ of $A$ such that $|S| \geq \frac{n}{3}$ and there are no triple $a,b,c$ such that $a \in S, b \in S, c \in S$ and $a+b=c$. It can be proved that it is always possible. Solution Pick a random real number r in $[0..1]$. For all integers $x$ in $A$, pick $x$ if and only if $x \times r$ has a decimal part in $[\frac{1}{3},\frac{2}{3})$. Repeat until $S$ is large enough. Because the expected size of $S$ each iteration is $\frac{n}{3}$, you only need a small number of iterations...... What a troll problem... This method is called probabilistic method/alteration. Check This KMO p6 for applications of this skill in Mathematics Olympiad

Difficulty Ratings Idea Creativity: 3/5 Techniques Used: 2/5 Implementation : 3/5 #beattheproblemsetter Problem Link Link by antontrygubO_o. $O(N\sqrt{N})$ Solution Not going to describe much because editorial talked about this. Basically, you seperate the awesome substrings into 2 cases, one is number of '1's less than $K$, and one is number of '1's more than or equal to $K$. Then you can do $NK$ on case 1 and $\frac{N^2}{K}$ on case 2. $O(Nlog^2(N))$ Solution by gs12117 Consider you plot a path in a coordinate plane, where you start at origin, walk rightwards if you encounter a '1' or upwards otherwise. Then we are finding the number of pairs of points that have an integer slope. So assume we are enumerating $K$ from 0 to $N$, the slope and count the number of valid pairs which has slope equals to $K$. Lets see what happens when we fix $K$. Imagine we building a graph, where each $x$ coordinate is a node, and an edge is built between $x_i$ a...

Difficulty Ratings Idea Creativity: 3/5 Techniques Used: 2/5 Implementation : 3/5 Game Theory not possible... Problem Link Link in Simplified Chinese by wzy. Simplified Statement Given an $N \times M$ grid, where $N,M \le 10$. Initially, some cells are colored pink, some are colored purple, and some are empty. While there is still an empty cell in the board: 1. Flip a coin. Heads show up 50% and Tails show up 50%. 2. If Heads show up, Alice will pick a cell and paint it pink. 3. If Tails show up, Bob will pick a cell and paint it purple. Alice score is 1 if there is a path consisting of only pink cells from the left hand side of the board to the right hand side of the board, and 0 otherwise. Bob score is 1 if there is a path consisting of only purple cells from the top side of the board to the bottom side of the board, and 0 otherwise. Note that each cell is adjacent to its 4 neighbouring cells. Alice wants to maximize (Alice's score - Bob's score), while...

Difficulty Ratings Idea Creativity: 4/5 Techniques Used: 4/5 Implementation : 3/5 Just a friendly reminder that this problem is out of IOI syllabus, although it may not look like. Problem link Link in simplified chinese by shanquan2. Simplified Statement Given an undirected graph of $N \le 2000$ nodes, determine whether it is possible to color every edge into either pink or purple, such that edges of each color form a forest. Full solution So in these kind of problems, there are two directions. One is to think from construction, one is to think from impossible cases. The second direction works very good here. Usually, after you eliminate very obvious impossible cases, then all the remaining cases are possible. So in this problem, a very obvious observation is that the number of edges $M \le 2N-2$, otherwise it will be impossible. However, it is not strong enough. A generalization would be, for every non-empty subset of nodes $S$, the number of edges in the corresponding...

Difficulty Ratings Idea Creativity: 1/5 Techniques Used: 1/5 Implementation : 1/5 I realised that there is a wide variety of audience for my blogs, so now I made this nobody can complain... This problem is by some alumni of PCMS that I am not aware of. Simplified Statement (Interactive problem) You have a bag that can hold $87$ balls. Now, $0 \le Q \le 1024$ people come to you one by one and the following happens. 1. The person gives you a ball with a number which is $3$, $4$ or $5$ written on it. 2. You look at it and you can either put into your bag or ignore. You can only put into your bag if there is less than $87$ balls beforehand. 3. The person disappears. Your objective is to maximize the sum of balls in your bag. Let $sum$ be the value you obtain and let $opt$ be the theoretical maximum (sum of the largest $min(87,Q)$ balls). If after the $Q$ people come, you have $1.45*sum \ge opt$ then you can get AC. Note that $Q$ is not given, and your bag can have less th...