What you are looking for is some condition (let's call it S) that a good random permutation will satisfy with high probability, and a bad random permutation will satisfy with low probability.
Then the solution will be: read in each permutation, and output good if it satisfies the condition and bad if it does not. The probability of an individual test case being answered incorrectly is 0.5*Prob(Good shuffle marked Bad)+0.5*Prob(Bad shuffle marked Good) = 0.5*(1 - (Prob(Good shuffle satisfies condition)-Prob(Bad shuffle satisfies condition))). So ideally we would like a solution that maximises this difference. The condition that maximises this difference is: the probability of getting this permutation with a bad shuffle is less than 1/100!. Unfortunately I don't know how to calculate the problem of getting a particular permutation from a bad shuffle. The condition used below is that there are fewer than 509 numbers that are more than 5 larger than their index. My first idea was to use the number of numbers from 501-1000 that end up in the top 500, but this didn't seem to give a large enough probability. My second idea was to use the number of i<j with x[i]<x[j], which seems like it would work with a few attempts. Have not tried with actual google data though. Sent from my iPad > On 27 Apr 2014, at 10:00, vijendra rana <[email protected]> wrote: > > hi, > if anybody can help me with the problem on proper shuffle i am seeing the > solutions submitted on the questions and found an interesting solution can > anybody explain me the code > > #include <cstdio> > #include <cstdlib> > #include <cstring> > > int main() { > freopen("input.in","r",stdin); > freopen("out.txt","w",stdout); > int T, cas; > scanf("%d", &T); > > for (cas = 1; cas <= T; cas++) { > int n, cc = 0, x; > scanf("%d", &n); > for (int i = 0; i < n; i++) { > scanf("%d", &x); > if (x > i + 5) > cc += 1; > } > if (cc > 508) > printf("Case #%d: BAD\n", cas); > else > printf("Case #%d: GOOD\n", cas); > } > } > > thanks > Vijendra > > -- > You received this message because you are subscribed to the Google Groups > "Google Code Jam" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to [email protected]. > To post to this group, send email to [email protected]. > To view this discussion on the web visit > https://groups.google.com/d/msgid/google-code/ef4fd501-7184-4988-87a5-2ce571b59713%40googlegroups.com. > For more options, visit https://groups.google.com/d/optout. -- You received this message because you are subscribed to the Google Groups "Google Code Jam" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send email to [email protected]. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/C3A82CCC-F765-41CC-AC48-3D037287D7A0%40pebody.org. For more options, visit https://groups.google.com/d/optout.
