Do you know any nice tasks which require randomization to decrease complexity which are not well known (like: you are given given set of points, find a line with at least n/2 points <- this one is well known)? Such like 364D - Ghd. Unfortunately codeforces has only tag "probabilities", which is usually used for problems where we have to calculate probability of something. Every time when I come across this kind of problem I am impressed how cool it is, so maybe you want to impress me? :D
Problem J from NEERC'15: http://codeforces.net/gym/100851/attachments
Oh, yes, this one was great, but unfortunately I've already solved it. :/ Anything more?
Unfortunately, no. That was the only randomization task which was proven(!) and solved by my team during the contest.
Look at my task 442E - Gena and Second Distance. There are some technical details in realization which make it not so cool, but there is still an interesting idea of how we can decrease complexity of algorithm (you can read it in editorial).
There was a problem from IOI 2016 practice tasks saying:
There's a string S of length N containing 1s and 0s only, you don't know the string but you know N (N<=1000), you can ask at most 1024 questions: is P a substring of S? then you have to know the string S.
even though it has deterministic solution but if the questions are guaranteed to be answered honestly then a nice randomization solution exist
Here is a similar problem. 753C, Interactive Bulls and Cows
How to solve it?
I remember solving this task from NCPC 2014, Basin City Surveillance, using a randomized backtrack algorithm.
Here is a solution to another problem solved with randomization.
Hello, Can you share your solution using randomized backtrack algorithm? Thank in advance
Sure why not? https://paste.ubuntu.com/p/Qp4yQb5JFn/
It's not really the best solution and also note that it will only get accepted randomly as well :D
Smallest enclosing circle is a classic example of randomization. In "higher algorithmics" there are lots of randomization algorithms, for example a lot of color coding techniques like "k-path", "triangle packing", "d-clustering". You can also search for applications of isolation lemma which is some prob lemma that is used to estimate success prob in various randomized algorithms.
Moreover, you can view it as a lame kind of randomization, but technically speaking all polynomial hashes etc are also technically speaking randomized algorithms. Another funny example is checking if there is a perfect matching in bipartite graph by creating an nxn matrix denoting adjacency matrix, but with ones replaced with some random numbers modulo some big prime number P. Then you calculate its determinant and if there is a perfect matching you get nonzero number with very high prob and if there is no such you get zero. Maybe this one isn't so impressive because problem we wanted to solve is pretty easy using standard methods, but you can use similar idea for any graphs, not just bipartite, but you need something more clever called Tutte's matrix.
You might wish to see Freivald's Algorithm which is a probabilistic randomised algorithm to verify matrix multiplication in O(n^2) time. (You might probably know it!! :D)
I recalled one more example. Problem C here http://codeforces.net/gym/100203 is probably a completely different randomization approach than those you have already seen. Very similar idea shows up in a "Conway" problem from Petrozavodsk Winter 15 Moscow SU Tapirs Contest (which was, unsurprisingly, unsolved during actual contest).
This problem is pretty neat I think: Pizza Problems But just by simply posting it here the solution is kind of semi-spoiled. ^^
How to solve it? I think that I'd be able to get AC with heuristics algorithms, some hill climbing or something like this, but I have no solution with O(1) chances for getting correct answer.
I summon Gassa and Burunduk1 to share their expertise about randomized algorithms and problems.
Another person that comes to my mind is Petr — he often provides problems with randomized solutions in his contests, as well as randomized approaches to problems from contests he participated in.
Summon failed :D perhaps you need to tribute with some monsters first :D
Some suggestion:
444B — DZY Loves FFT
329C — Graph Reconstruction
http://codeforces.net/gym/100512 J
What is the correct solution for this problem ? :)
That problem is a piece of shit. During the contest we invented a solution, then discovered a simple counter test, started to try another solutions but failed. Of course that test was absent and everyone who was brave enough got AC.
I saw a lot of different solutions that didn't seem to pass any test case. This is the reason why I am interested in a correct approach.
This is a relatively simple problem from regional school olympiad.
Given a set of points, it's known that these points are lying on not more than two circles. You are to determine the coordinates of centers and radiuses.
Among first five points there are three that lie on one of those two circles, no randomization, O(n), ggwp :D
Not to be pedantic but isn't this more precisely O(1) (in addition to being O(n))?
I don't get your point. O(1) checks ((5 choose 3) = 10 to be precise), each of them in O(n), total complexity O(n).
Sorry I misunderstood original algorithm, thanks for the elaboration.
This one has randomized solution : https://www.codechef.com/IPC15P2B/problems/NOPI
Not sure if you consider it nice task though.
I suggest you to check long algorithm contests, like Topcoder Marathons. As to my knowledge, all the top solutions from the past are randomized there. One of the latest tasks featured a problem that could be reduced to modified TSP, for instance.
I didn't mean this kind of randomization, ofc. approximation problems require some randomization, but it's definitely different topic.
Another one from Bubble cup finals. 717H, Pokermon League Challenge
Given a connected undirected graph, find number of pairs of edges such that graph becomes disconnected when these two edges are deleted.
Seems very interesting, what complexity are we looking for? Or better: for what limits?
In practice, one dfs is enough for n, m = 105.
There is timus version with n ≤ 2000
Man, you already got this accepted on Petrozavodsk >_>. It is problem C5 (Eulerian Orientation).
You are right, I remember now, even I was solving it in my team during the contest XD But it consisted only of nice hashes (I know that hashes are randomization too).
please provide problem link.
It's not easy to provide links to Petrozavodsk problems :<
Please provide solution then :)
If you want to do it then you're free to go
solution video link
This video made my day xD
Finding Lines from NWERC 2014.