Hello!

Today i coded a nondeterministic solution for Problem C (Fashion Police) and got AC verdict using it, which led me to qualify to Round 2. Since it is a very different "paradigm", i wanted to share my solution here so it can maybe be useful for someone in the future :)

My solution relies on a random outfit subset generator. Inicially we are going to set a precision r, the number of times our generator is going to run. I empirically chose to use 10000 random generations because that led my code to run in about ~2 minutes, enough to solve the downloaded input. In each step, it generates a random outfit subset in the following manner:

  solution = {}
  choose a value p, the probability that some outfit will be discarded (in my code i used p = 10%)
  for each possible outfit o:
    if you can include o in the solution without violating the Fashion Police rules:
      choose a random number n in the range [1,100]
      if n > p:
        include o in the solution

You can argue that this subset probably won't be maximal, but that's no problem! After we generate the random subset, we can simply iterate over all possible outfits and include every missing valid outfit until the solution is maximal! This will be efficient because there are only J*P*S (max 27) such outfits.

So we are going to generate r maximal random outfits. Now we just pick the biggest and hope that it will really be the optimal value! We can use this RNG-based solution and expect that it will produce the correct output because there are 2^27 possible subsets, but only 27 possible answers (remember that any answer with the correct value is optimal, so consider them to be the same). Since we are only generating maximal subsets, the chance that some iteration will hit the optimal value is huge.

My code : http://pastebin.com/nTxWKyJH