Hello coders,
my idea how to solve Killing Gs problem (CKROACH) from May 2012 Long contest was to generate random permutations of N integers (k_1, …, k_n) and using just first few insecticides to get probability that Gs_i is dead with probability above 90%. But my submission is getting WA, any idea why?
I believe that this formulae holds: When k_1, …, k_m are indexes of used insecticides, than probability that Gs_i is alive is
so I’m looking for such min m, that p[i] <= 0.10 for all i.
as far as i know, this formula seems to be correct, as it is directly derived from the problem statement. the mistake here is probably a glitch in your implementation, or related to the way you input/output the result of your computations… i don’t know. you should check your code on several test cases to spot the corner case (if there is one).
First I thought that problem is in double aritmetics (rounding or something), but when I tried BigDecimal (Java) I’m getting WA still.
I tried to use generator (http://www.codechef.com/download/CKROACH_generator.c) for testing, but my results are correct according to above formulae…
I skipped this condition:
The second line should have K integers, the numbers of insecticides which Ciel buys, in ascending order.
or related to the way you input/output the result of your computations…
i think this question was N-P completeness question
Yes, it is. Setters use such problems as tie break problems. We have to find as good solution as it’s possible in given timelimit, but my was wrong according to wrong output format…