Algorithms: Design and Analysis, Part 2, week2 交作业以及请教

这次作业写了我好久。。。
第二道编程还是错的。。。怎么都找不出来错误。上来找高手答疑。。。

所有的test case我都过了。但是答案就是不对。。。我的答案是 6210.... 不知道大家有没有犯和我一样的错误，然后解决了的。。。快要抓狂了。
我的大概思路是参考了discussion forums上的：
每个node用十进制位数做key，然后用hash，我用了100个bucket，用余数来决定bucket。
然后类似第一题的思路，用union find。最后数有多少个leader node，就是答案。

死也没找到为啥出错。
求拍。。。。

Problem Set #2 Help

Attempt Quiz
Due Date         Sun 20 Jul 2014 11:59 PM PDT
If you submit after the due date (but before the hard deadline), your submission score will be penalized 50%.

Hard Deadline         Sun 24 Aug 2014 11:59 PM PDT
If you submit any time after the hard deadline, you will not receive credit.

Effective Score        4.00 / 5.00
Explanation: 4.00 = 4.00 (Score for attempt 1) * 100% (No penalties)
Each time that you attempt it, we'll record a score based on your performance and any penalties due to late submissions. Your effective score will be the highest score of all the allowed attempts made before the hard deadline.

# of Attempts        2 / 2
Last Attempted        Mon 7 Jul 2014 7:35 AM PDT
Last Attempted Score        4.00 / 5.00Show Previous Attempts
  Programming Assignment #2
(collapsed, click to expand)
Completed
Programming Assignment #2 Help

Attempt Quiz
Due Date         Sun 20 Jul 2014 11:59 PM PDT
If you submit after the due date (but before the hard deadline), your submission score will be penalized 50%.

Hard Deadline         Sun 24 Aug 2014 11:59 PM PDT
If you submit any time after the hard deadline, you will not receive credit.

Effective Score        5.00 / 5.00
Explanation: 5.00 = 5.00 (Score for attempt 5) * 100% (No penalties)
Each time that you attempt it, we'll record a score based on your performance and any penalties due to late submissions. Your effective score will be the highest score of all the allowed attempts made before the hard deadline.

# of Attempts        5 / 15
Last Attempted        Tue 8 Jul 2014 8:24 AM PDT
Last Attempted Score        5.00 / 5.00Show Previous Attempts

kelvinzhong 发表于 2014-7-13 21:53
你的答案真的已经很接近了....但是思路是不是有点不对？ 我第二题和第一题的思路完全不一样的..

能说说你第二题的思路么。

我的思路是参照论坛上的一个人的。
就是对每个node，我用combination找到1个不同的点，对应1的距离，2个不同的点，对应2的距离。然后用hashtable去找24*1+ 24*23/2 = 300个可能距离小于3的所有点是否在file里面，在的话，我就union find。

我对所有小数据上跑都没问题，我都怀疑是不是啥stack overflow类似的毛病了。。。

kelvinzhong 发表于 2014-7-17 23:55
同学week3做了吗？...求指导呀..不会做大数据的那个TAT...

做了2M个points那个，我是用了hash table，然后每次update的时候只保留一个column，这样可以不占用memory。。。

这个我也用了很长时间...

你的答案真的已经很接近了....但是思路是不是有点不对？ 我第二题和第一题的思路完全不一样的..

xingzhui222 发表于 2014-7-14 00:09
能说说你第二题的思路么。

我的思路是参照论坛上的一个人的。

我也是这么做的.........

kelvinzhong 发表于 2014-7-14 09:26
我也是这么做的.........

额，那就更奇怪了。。。理论上如果我出错了的话，test cases应该通不过才对。。。真是懊恼啊。。
你是用啥写的？ running time是多少呀？

这。。我当时没有跑test cases..python, runningtime应该和你一样， 200000*300

kelvinzhong 发表于 2014-7-14 19:39
这。。我当时没有跑test cases..python, runningtime应该和你一样， 200000*300

Thanks for your help!!!
I found a tiny bug in my code and it is fixed now.