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 < 2^M$, where $M = 20$. FInd the number of ways to choose two subsets of the chocolates $A$ and $B$ such that: 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

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