Another Few Randomization 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 the $N$ bitmasks, the relative error is $\le 25\%$. $M \le 1e5$, $N \le 1e6$.

Solution

Assign a random number for each bit and pick an integer $k$. Then for each bitmask, maintain the k minimum values among the bits that are set to 1. Estimate the number of bits that are 1 with the $k$ values you have, by using that $\frac{k}{kth \, minimum \, value} \approx \frac{number \, of \, bits}{Rand max}$. Setting $k$ to 30~50 should work. Run few times to make the answers more accurate. Proving probability of correctness? We don't do that here...

Task 7

Simplified Statement

Given $1 \le N \le 1e5$ random points on coordinate plane (each has integer coordinates), find whether there exists 3 points that are collinear.

Solution

I'm not sure if there are better ways I came up with this myself. Pick a prime $p$ that is around $\sqrt{N}$. Take modulo p for every coordinate. Then, if the three points have to be collinear, it must be collinear in modulo p field too. You can loop the slope and split the $N$ points into $p$ buckets. Each bucket is expected to have $N/p$ elements. Check if there exists 3 points collinear in each bucket in $O(N^2)$. Complexity is $O(Np+\frac{N^2}{p})$. You can also discard and repick a $p$ if you check that one bucket is too large. Actually, the number of false alarms can be bounded (not 100% sure) by considering for each 3 points that are not collinear, the number of $p$ that will cause them to be placed in the same bucket.

Task 8

Link

Link in simplified chinese

Simplified Statement

Given an array of length $1 \le N \le 3e6$, there are exactly $1 \le k \le 5000$ integers that has occured an odd number of times in this array. Find all of them. Unfortunately, you only have 1MB memory...

Solution

Consider a function $f$ mapping an integer to a number in $[1,k]$, which it is deterministic, but the probability of $f(x)=p$, when choosing random $x$, is about $\frac{1}{k}$ for all $p$ in $[1,k]$. Create another function $g$, which maps every integer to a random integer. Consider the bitwise-xor of all $x$ in the array that has $f(x)=y$ for every $y$. Call it $P_y$. Consider the bitwise-xor of all $g(x)$ in the array that has $f(x)=y$ for every $y$. Call it $Q_y$. If $g(P_y)=Q_y$, then it is almost definite that $P_y$ occured odd number of times in the array. Do this multiple times to find all of them out.

Task 9

A problem from 300iq. Will share once it is publicized...