Computer Science Canada ECOO 2013 Round 3 Solutions |
| Author: | SamScott [ Sun May 12, 2013 6:25 am ] |
| Post subject: | ECOO 2013 Round 3 Solutions |
Here are the questions, test data, and solutions for round 3. I thought questions 2 and 4 were the hardest because of the efficiency issues - if you code an inefficient solution in both cases you will only get 6 or 7 of the 10 test cases within 30 seconds. But judging by the choices the teams made, it seems like question 3 might have been harder. Sam. |
|
| Author: | ishiney [ Sun May 12, 2013 3:43 pm ] |
| Post subject: | RE:ECOO 2013 Round 3 Solutions |
DP O(N^2) solution for #2: First, assume that the given child is the "bottom" child (that is, it inherited at least the first & last genes from the 2nd parent). Trivially, check if the minimum # of mutations decreases by assuming it as the "top" child. Let dp[start][length] be our states (length being the distance between the 2 indices/crossover endpoints, start being the index of the leftmost endpoint). Initialize dp[i][0] for all relevant i to the differences between the bottom child and bottom parent. Transform between dp[i][j] --> dp[i][j+1] by using the precomputed value for dp[i][j], then noting whether there's an increase/decrease/no change in # of mutation after including j+1 in the crossover. Take minimum over all valid ranges for answer. O(N^2) states, O(1) transition time, thus O(N^2) solution. |
|
| Author: | SamScott [ Wed May 15, 2013 7:02 pm ] |
| Post subject: | Re: RE:ECOO 2013 Round 3 Solutions |
ishiney @ Sun May 12, 2013 3:43 pm wrote: DP O(N^2) solution for #2:
First, assume that the given child is the "bottom" child (that is, it inherited at least the first & last genes from the 2nd parent). Trivially, check if the minimum # of mutations decreases by assuming it as the "top" child. Let dp[start][length] be our states (length being the distance between the 2 indices/crossover endpoints, start being the index of the leftmost endpoint). Initialize dp[i][0] for all relevant i to the differences between the bottom child and bottom parent. Transform between dp[i][j] --> dp[i][j+1] by using the precomputed value for dp[i][j], then noting whether there's an increase/decrease/no change in # of mutation after including j+1 in the crossover. Take minimum over all valid ranges for answer. O(N^2) states, O(1) transition time, thus O(N^2) solution. That sounds good, thanks for posting! You can also do it without the O(n^2) space requirement of the dp array by pre-computing a "base mutation rate" between the child and each parent, and then updating those mutation rates one bit at a time as you search through the various crossover points, keeping track of the smallest value so far as you go. Sam. |
|
| Author: | Stefan69 [ Tue Oct 22, 2013 6:02 am ] |
| Post subject: | RE:ECOO 2013 Round 3 Solutions |
I am satisfied with you and you are in right . |
|