Computer Science Canada Programming C, C++, Java, PHP, Ruby, Turing, VB   Username:   Password: Wiki   Blog   Search   Turing   Chat Room  Members
ECOO 2013 Round 3 Solutions
Author Message
SamScott

Posted: 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.

ECOO 2013 Finals - Solutions.zip
Description:
Filename:  ECOO 2013 Finals - Solutions.zip
Filesize:  386.62 KB

ishiney

Posted: 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.
SamScott

Posted: 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.
Stefan69

Posted: 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 .
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First

Page 1 of 1  [ 4 Posts ]
 Jump to:  Select a forum  CompSci.ca ------------ - Network News - General Discussion     General Forums   -----------------   - Hello World   - Featured Poll   - Contests     Contest Forums   -----------------   - DWITE   - [FP] Contest 2006/2008   - [FP] 2005/2006 Archive   - [FP] 2004/2005 Archive   - Off Topic     Lounges   ---------   - User Lounge   - VIP Lounge     Programming -------------- - General Programming     General Programming Forums   --------------------------------   - Functional Programming   - Logical Programming   - C     C   --   - C Help   - C Tutorials   - C Submissions   - C++     C++   ----   - C++ Help   - C++ Tutorials   - C++ Submissions   - Java     Java   -----   - Java Help   - Java Tutorials   - Java Submissions   - Ruby     Ruby   -----   - Ruby Help   - Ruby Tutorials   - Ruby Submissions   - Turing     Turing   --------   - Turing Help   - Turing Tutorials   - Turing Submissions   - PHP     PHP   ----   - PHP Help   - PHP Tutorials   - PHP Submissions   - Python     Python   --------   - Python Help   - Python Tutorials   - Python Submissions   - Visual Basic and Other Basics     VB   ---   - Visual Basic Help   - Visual Basic Tutorials   - Visual Basic Submissions     Education ----------- - Student Life   Graphics and Design ----------------------- - Web Design     Web Design Forums   ---------------------   - (X)HTML Help   - (X)HTML Tutorials   - Flash MX Help   - Flash MX Tutorials   - Graphics     Graphics Forums   ------------------   - Photoshop Tutorials   - The Showroom   - 2D Graphics   - 3D Graphics     Teams ------ - dTeam Public

 Style: Appalachia blueSilver eMJay subAppalachia subBlue subCanvas subEmjay subGrey subSilver subVereor Search: