Solving competitive programming problems

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...

Difficulty Ratings Idea Creativity: 2/5 Techniques Used: 3/5 Implementation : 2/5 Last week very hard, this week easier... Problem Link Link in simplified chinese by matthew99 Simplified Statement Given two sequences $a,b$, both of length $1 \le N \le 2 \times 10^5$ consisting of positive integers. Pick $K$ elements on each sequence such that there exists at least $L$ integers $i$, where both $a_i$ and $b_i$ are chosen. Find the maximum possible sum of the chosen elements. Solution You realise that this problem probably is looking for some kind of greedy, but it is hard to find one or prove this. In this case, you might write stress test and try your greedies out. In this problem, a lot of different fishy-looking solutions work, and most of them can be proved by min-cost flow. Consider the following construction. Create a source $S$, a sink $T$, $N$ nodes, each for an element in $a$; another $N$ nodes, each for an element in $b$, and finally, two additional nodes $C$ ...

Difficulty Ratings Idea Creativity: 5/5 Techniques Used: 3/5 Implementation : 5/5 Very hard problem, a lot of details in implementation too. However, I think that general idea is quite interesting and easy to understand:) Problem Link Link in simplified chinese by jiry_2 Simplified Statement Consider a graph $G$. Create $G'$ as follows: - each edge in $G$ corresponds to each node in $G'$ - build an edge between two nodes in $G'$ if their corresponding edge in $G$ have a common endpoint Let $L(G)=G'$. Given a tree $T$ with $N \le 5000$ nodes and $k \le 9$, find the number of nodes in $L^k(T)$ modulo 998244353, where $L^k(G)$ is the function $L$ operated $k$ times on $G$. Solution Define $|G|$ as the number of nodes in $G$. Lets see what is $|L^k(G)|$ for small $k$. $k=1$: Number of edges in $G$. $k=2$: Number of chains of 3 nodes in $G$. $k=3$: Number of chains of 4 nodes in $G$ + 3*(Number of stars of 4 nodes in $G$) + 3*(Number of cycles of 3 nod...