Radewoosh's blog

Randomization tasks
By Radewoosh, history, 8 years ago, In English

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

  • Vote: I like it
  • +131
  • Vote: I do not like it

Comments Comments (45)
| Write comment?
»
8 years ago, # |
  Vote: I like it +41 Vote: I do not like it
Spoiler alert for NEERC problem!
→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +28 Vote: I do not like it

    Oh, yes, this one was great, but unfortunately I've already solved it. :/ Anything more?

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Unfortunately, no. That was the only randomization task which was proven(!) and solved by my team during the contest.

      → Reply
»
8 years ago, # |
  Vote: I like it +33 Vote: I do not like it

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

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +34 Vote: I do not like it

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

→ Reply
»
8 years ago, # |
  Vote: I like it +30 Vote: I do not like 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.

→ Reply
»
8 years ago, # |
  Vote: I like it +84 Vote: I do not like it

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.

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +65 Vote: I do not like it

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)

→ Reply
»
8 years ago, # |
  Vote: I like it +20 Vote: I do not like it

I recalled one more example. Problem C here http://codeforces.me/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).

→ Reply
»
8 years ago, # |
  Vote: I like it +10 Vote: I do not like it

This problem is pretty neat I think: Pizza Problems But just by simply posting it here the solution is kind of semi-spoiled. ^^

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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.

    → Reply
»
8 years ago, # |
  Vote: I like it +118 Vote: I do not like it

I summon Gassa and Burunduk1 to share their expertise about randomized algorithms and problems.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +49 Vote: I do not like it

    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.

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +26 Vote: I do not like it

    Summon failed :D perhaps you need to tribute with some monsters first :D

    → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Some suggestion:

444B — DZY Loves FFT

329C — Graph Reconstruction

→ Reply
»
8 years ago, # |
  Vote: I like it +21 Vote: I do not like it

http://codeforces.me/gym/100512 J

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What is the correct solution for this problem ? :)

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +49 Vote: I do not like it

    Among first five points there are three that lie on one of those two circles, no randomization, O(n), ggwp :D

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Not to be pedantic but isn't this more precisely O(1) (in addition to being O(n))?

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
        ← Rev. 2   Vote: I like it +8 Vote: I do not like it

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

        → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Sorry I misunderstood original algorithm, thanks for the elaboration.

          → Reply
»
8 years ago, # |
  Vote: I like it +13 Vote: I do not like it

This one has randomized solution : https://www.codechef.com/IPC15P2B/problems/NOPI
Not sure if you consider it nice task though.

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +28 Vote: I do not like it

    I didn't mean this kind of randomization, ofc. approximation problems require some randomization, but it's definitely different topic.

    → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Another one from Bubble cup finals. 717H, Pokermon League Challenge

→ Reply
»
8 years ago, # |
  Vote: I like it +62 Vote: I do not like it

Given a connected undirected graph, find number of pairs of edges such that graph becomes disconnected when these two edges are deleted.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    Seems very interesting, what complexity are we looking for? Or better: for what limits?

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      In practice, one dfs is enough for n, m = 105.

      → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +36 Vote: I do not like it

      Man, you already got this accepted on Petrozavodsk >_>. It is problem C5 (Eulerian Orientation).

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it +18 Vote: I do not like it

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

        → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        please provide problem link.

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it +10 Vote: I do not like it

          It's not easy to provide links to Petrozavodsk problems :<

          → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Finding Lines from NWERC 2014.

→ Reply