By Radewoosh, history, 3 years ago, ,

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

• +131

 » 3 years ago, # |   +41 Spoiler alert for NEERC problem!Problem J from NEERC'15: http://codeforces.com/gym/100851/attachments
•  » » 3 years ago, # ^ |   +28 Oh, yes, this one was great, but unfortunately I've already solved it. :/ Anything more?
•  » » » 3 years ago, # ^ |   0 Unfortunately, no. That was the only randomization task which was proven(!) and solved by my team during the contest.
 » 3 years ago, # |   +33 Look at my task 442E - Гена и второе расстояние. 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).
 » 3 years ago, # | ← Rev. 2 →   +34 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
•  » » 3 years ago, # ^ |   +30 Here is a similar problem. 753C, Interactive Bulls and Cows
 » 3 years ago, # |   +30 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.
•  » » 3 months ago, # ^ | ← Rev. 2 →   +4 Hello, Can you share your solution using randomized backtrack algorithm? Thank in advance
•  » » » 7 weeks ago, # ^ |   -6 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
 » 3 years ago, # |   +84 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.
 » 3 years ago, # | ← Rev. 2 →   +65 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)
 » 3 years ago, # |   +20 I recalled one more example. Problem C here http://codeforces.com/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).
 » 3 years ago, # |   +10 This problem is pretty neat I think: Pizza Problems But just by simply posting it here the solution is kind of semi-spoiled. ^^
•  » » 3 years ago, # ^ |   +5 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.
•  » » » 3 years ago, # ^ |   0 The solution slides for the contest where the problem appeared are here. You can find testdata and judges' solutions here: challenge.csc.kth.se/2014
 » 3 years ago, # |   +118 I summon Gassa and Burunduk1 to share their expertise about randomized algorithms and problems.
•  » » 3 years ago, # ^ |   +49 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.
•  » » 3 years ago, # ^ |   +26 Summon failed :D perhaps you need to tribute with some monsters first :D
 » 3 years ago, # |   0 Some suggestion:444B — DZY Loves FFT329C — Graph Reconstruction
 » 3 years ago, # |   +21
•  » » 3 years ago, # ^ |   0 What is the correct solution for this problem ? :)
•  » » » 3 years ago, # ^ |   +3 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.
•  » » » » 3 years ago, # ^ |   0 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.
 » 3 years ago, # |   0 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.
•  » » 3 years ago, # ^ |   +49 Among first five points there are three that lie on one of those two circles, no randomization, O(n), ggwp :D
•  » » » 3 years ago, # ^ |   0 Not to be pedantic but isn't this more precisely O(1) (in addition to being O(n))?
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   +8 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).
•  » » » » » 3 years ago, # ^ |   0 Sorry I misunderstood original algorithm, thanks for the elaboration.
 » 3 years ago, # |   +13 This one has randomized solution : https://www.codechef.com/IPC15P2B/problems/NOPI Not sure if you consider it nice task though.
 » 3 years ago, # |   0 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.
•  » » 3 years ago, # ^ |   +28 I didn't mean this kind of randomization, ofc. approximation problems require some randomization, but it's definitely different topic.
 » 3 years ago, # |   0 Another one from Bubble cup finals. 717H, Pokermon League Challenge
 » 3 years ago, # |   +62 Given a connected undirected graph, find number of pairs of edges such that graph becomes disconnected when these two edges are deleted.
•  » » 3 years ago, # ^ |   +18 Seems very interesting, what complexity are we looking for? Or better: for what limits?
•  » » » 3 years ago, # ^ |   +8 In practice, one dfs is enough for n, m = 105.
•  » » » » 3 years ago, # ^ |   +13 There is timus version with n ≤ 2000
•  » » » 3 years ago, # ^ |   +36 Man, you already got this accepted on Petrozavodsk >_>. It is problem C5 (Eulerian Orientation).
•  » » » » 3 years ago, # ^ |   +18 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).
•  » » » » 3 months ago, # ^ |   +5 please provide problem link.
•  » » » » » 3 months ago, # ^ |   +10 It's not easy to provide links to Petrozavodsk problems :<
•  » » » » » » 3 months ago, # ^ |   +31 Please provide solution then :)
•  » » » » » » » 3 months ago, # ^ |   0 If you want to do it then you're free to go
•  » » » » » » » 3 months ago, # ^ |   -17 solution video link
 » 3 months ago, # |   0