Solving competitive programming problems

Difficulty Ratings Idea Creativity: 3/5(Some are pretty geniosity) Techniques Used: 2/5 Implementation : 2/5 So uh I'll continue the previous post and post a few more randomization problems. Task 5 Link CF 452F Solution Sweep from left to right, consider a bitmask of elements that has appeared already. If the current element is x, you want to check whether the first 2x-1 bits of the bitmask is a palindrome, which can be done by polynomial hashing. There is also an OP deterministic solution that I'm not going to describe. Task 6 Link Link in simplified chinese Simplified Statement You have $M$ bitmasks of size $M$. The ith bitmasks have all bits set 0 except the ith bit, which is set 1. You are going to create $N-M$ new bitmasks, which each bitmask is created by taking bitwise-or of two bitmasks that already existed before. For each of the $N$ bitmasks, output the nubmer of bits that is 1. Your solution would be judged as correct, if for at least $95\%$ of th

Difficulty Ratings Idea Creativity: 3/5(Some are pretty geniosity) Techniques Used: 2/5 Implementation : 2/5 Resources Uh, there is not much techniquees in Randomization. But basically you must know Blogewoosh #6 trick. Task 1 Simplified Statement CF 1240E Note: This problem is not easy at all. Solution Read the editorial lol. The key to optimize from two logs to one log is to use blogewoosh trick, which is kinda surprise to me(?)... Task 2 By alex20030190 Simplified Statement Given a permutation A of length $N \le 100000$ and an array B, sum $f(l,r)$ for all pairs of $1 \le l \le r \le N$, where $f(l,r) = M1(l,r) \times M2(l,r) \times B[r-l+1]$, and $M1(l,r)$, $M2(l,r)$ means the maximum and second maximum in $A[l..r]$ respectively. It is guarenteed that A is randomly generated. Solution It is quite geniosity. The solution is to pick the maximum of array, compute sum for all ranges that included the value, then divide and conquer. The complexity analysis is simila

Difficulty Ratings Idea Creativity: 5/5 Techniques Used: 3/5 (1/5 if excluding subtask 4) Implementation : 2/5 Problem Link Link (Simplified Chinese) by WuHongXun Simplified Statement There are $N$ people. Each person has a number on his forehead, which is either $0$ or $1$. The $N$ people's objective is to vote the xor value of the $N$ numbers correctly. Each person can see numbers on every other person's forehead, but not his own. Every person has exactly one vote. Each person knows their id. Subtask 1 $N = 15$. Design a voting strategy such that out of 32768 situations, only less than 7000 of them would result in voting the wrong answer. Note that the people can have a different strategy than other people. Subtask 2 Same as subtask 1, but only less than 2100 of the situation would result in wrong answer. Subtask 3 Same as subtask 1, but this time, each person can vote $x$ times, where $0 \le x \le 10^8$. Design a strategy such that, only less than 3 of the

Difficulty Ratings Idea Creativity: 3/5 Techniques Used: 2/5 Implementation : 2/5 Problem Link Link (Simplified Chinese) by matthew99 afaik Simplified Statement Given an undirected graph with $N$ vertices and $M$ edges, where each edge has a label of either $0$ or $1$. Answer $Q$ queries of the following form: given $x,y$, determine whether there exist a path (not necessarily wihtout cycles) from $x$ to $y$ such that if we concatenate the labels along the path, we can obtain a palindrome. $N \le 5000, M \le 500000, Q\le 100000$. Solution First we try to figure out a solution with polynomial complexity. Consider we create a new graph where each node is a pair of ordered indices $(u,v)$, and we add a special node $S$. We create a directed edge $(u,v) \rightarrow (p,q)$ if there exists edges $u-p$ and $v-q$, and they have the same label. Also, we create edges $S\rightarrow (u,u)$, and $S\rightarrow (u,v)$ if $u$ and $v$ is connected by an edge. We have created a new gr

Who am I? Highschool dude active in sports programming field. What is this? In this series of blogs, I will share OI problems that is interesting in my opinion. I would probably post new blog weekly(I'm not always on time). I will update this page to add more additional information sometime later.