Computer Science Canada DWITE Round #2 Question #5 |

Author: | A.J [ Wed Nov 30, 2011 5:58 pm ] |

Post subject: | DWITE Round #2 Question #5 |

Turns out there is an error on of the the testcases for #5. So the maximum possible testcases one can get right is 4/5. Once again, sorry about this, AJ |

Author: | jli1 [ Wed Nov 30, 2011 7:28 pm ] |

Post subject: | RE:DWITE Round #2 Question #5 |

Yet no one gets above 2/5... What was the correct solution for this one? |

Author: | Revolution [ Wed Nov 30, 2011 8:03 pm ] |

Post subject: | RE:DWITE Round #2 Question #5 |

Can you post the data file for Question 5? |

Author: | antybash [ Wed Nov 30, 2011 8:40 pm ] |

Post subject: | Re: DWITE Round #2 Question #5 |

Hmm.. so I don't want to steal AJ's thunder in the analysis of the solution. Although if you want a sneak peek, this site has a superb explanation! http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=disjointDataStructure |

Author: | Revolution [ Wed Nov 30, 2011 8:55 pm ] |

Post subject: | RE:DWITE Round #2 Question #5 |

I was going to do that ^ but i forgot to include one line of code and got 0 /5 T.T |

Author: | d310 [ Wed Nov 30, 2011 9:01 pm ] |

Post subject: | Re: DWITE Round #2 Question #5 |

I recognised that it was a disjoint data structure... I guess I got TLE because I used an array indexes instead of pointers, and forgot to use the rank optimisation. Just wondering what were the values on N for each test case? |

Author: | Tony [ Wed Nov 30, 2011 9:05 pm ] |

Post subject: | RE:DWITE Round #2 Question #5 |

something crazy large. Knowing AJ, he'd try to hit the specified 100000. I'll let him post the details. |

Author: | trishume [ Wed Nov 30, 2011 9:45 pm ] |

Post subject: | Re: DWITE Round #2 Question #5 |

We (ttm, others, and I) solved this using lists of sets and merging and adding to the sets. Kind of dynamic programming like. But we were in the final 15 minutes and ended up submitting a non-compiling solution with bugs, twice. Tony (the ttm one) wrote a better version which finished compiling 1m too late. But without the test data we don't know if it works |

Author: | antybash [ Wed Nov 30, 2011 10:16 pm ] |

Post subject: | Re: DWITE Round #2 Question #5 |

Yeah .. I'm in favour of seeing the testcase. I thought I coded up the disjoint sets and thought I should have received a few points but didn't get any. :\ Would be possible to post on say google docs or some place like this? |

Author: | A.J [ Thu Dec 01, 2011 12:28 am ] |

Post subject: | RE:DWITE Round #2 Question #5 |

I'll be posting solutions over this weekend. I am super busy with assignments and exams. I will say that the intended solution for this problem was Union Find. The link antybash provided is a good read. I'll explain the details in the solutions (and release the testdata). |

: |

You can syndicate this boards posts using the file backend.php or view the topic map using sitemap.php.