I didn't "panic" but when I made a reasoning about cases 2 and 3, I could
not accept that the solution would be so easy as just an integer. I built a
test program to quickly simulate Goro's actions and build stats over the
number of hits.
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class Test {
public static void main(String[] args) {
int n=10;
int cases = 100000;
double sum = 0;
for(int i=0; i<cases; i++)
sum += loop(n);
System.out.println(sum/cases);
}
private static int loop(int n) {
List<Integer> numbers = new ArrayList<Integer>();
for(int i=0; i<n; i++)
numbers.add(i);
Collections.shuffle(numbers);
int unordered = 0;
for(int i=0; i<n; i++){
if(numbers.get(i) != i)
unordered++;
}
if(unordered>0)
return 1 + loop(unordered);
return 1;
}
}
Here n=10 gave me results aroud 10, I tried with a few other values of n and
I was convinced.
It also made me think - whenever you detect a possible solution that would
be that simple, it seems worth implementing it and trying to solve the small
case ; the 4 minutes penalty is nothing compared to the time I spend doing
some maths and building the test program, and I guess a lot of people also
lost much more than 4 minutes to prove their intuition was correct.
2011/5/10 Igor Naverniouk <[email protected]>
> Igor (the problem author) did that too, but without the panic since he had
>> a little more time. :-)
>>
>> Yes, I actually implemented a complicated Dynamic Programming solution, in
> rational numbers, with BigInteger. It had an exponential running time. And
> then I spend a long time looking for the bug, when I saw that the answers
> were always coming out as integers.
>
> Of course, it didn't help that there were no input limits given to me, so I
> did not know whether there was a polynomial-time solution or not.
>
> David Arthur was actually first to formally prove that the simple solution
> was always correct. He wrote the problem analysis.
>
> igor
>
> --
> You received this message because you are subscribed to the Google Groups
> "google-codejam" group.
> To post to this group, send email to [email protected].
> To unsubscribe from this group, send email to
> [email protected].
> For more options, visit this group at
> http://groups.google.com/group/google-code?hl=en.
>
--
You received this message because you are subscribed to the Google Groups
"google-codejam" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/google-code?hl=en.
