编程挑战题：SPOJ LOPOV - con'ted

Original post : http://computer.discuss.com.hk/viewthread.php?tid=22601830&;extra=page%3D6&page=1

Hi fitcat,

Long time no see I have not visited hkdiscuss for several months, and sorry for late reply. you may forgot the original post, but actually I have tried your suggestions and drafted the conclusion few months ago. however, suddenly, my focus be changed by other affair, and hence the conclusion has not posted so far. (I want to reply your original post, but unfortunately, the post has been closed)
to be concluded.

point 1: uses fread() to process the input data gain the significant improvement, the running time from 0.23 down to 0.15
point 2: uses static array instead of std:vector is no observable improvement in this case surprisingly
point 3: this suggestion is great, as you guess, std::sort is highly optimized, after remove the std_comp_bag parameter and uses the std:sort default comparison, the running time be improved 0.02 s, to 0.13s

引用:Glad to know my analysis is close to the fact.

The difference in time may be due to the following issues in order of significance:
1. I use fread() to read most (or all depends on the input size) of the input. My buffer size is 64KB and the maximum input size is 6.9MB. So, the total number of calls to read input is at most about 100. Yours is at most 300,000. Calling system functions especially on input/output is time consuming.
2. Since we know the maximum size, we should call std::vector.reserve() to allocate sufficient memory to avoid dynamic memory allocation due to growth in size. Fyi, GCC reserve storage for 16 elements by default, IIRC. I use static array to store both bags and jewellery. Static array is usually faster than std::vector.
3. std::sort by default sorts the elements in ascending order. So, you don't need to pass in std_comp_bag. I don't know whether this affects performance or not. Since std::sort is highly optimized, I believe omitting the third argument will help though the difference may not be significant.

[ 本帖最后由 assembly.jc 於 2014-3-10 06:43 AM 编辑 ]

作者: assembly.jc   发布时间: 2014-03-28

Glad to know you have tried my suggestions and made quite an improvement in speed.
There are a number of new problems added recently in SPOJ. As usual, some are easy while some are difficult and challenging. IMO, majority are in intermediate level, which is very suitable to train up programming skill.
BTW, my rank is now 33 (highest 32).

作者: fitcat07   发布时间: 2014-03-28

引用:原帖由 fitcat07 於 2014-3-10 10:56 AM 发表
Glad to know you have tried my suggestions and made quite an improvement in speed.

Yes, I/O is quite significant to the speed if SPOJ can provide some standard way to dual with I/O to all, the running time will be reflected to the speed of algorithm much truly.

引用:There are a number of new problems added recently in SPOJ. As usual, some are easy while some are difficult and challenging. IMO, majority are in intermediate level, which is very suitable to train up programming skill.

Would you suggests some interesting problems? Are some problems related to graphic or maths? or there exists some problems that need familiar with existing algorithm and can't to be solved immediately ?

引用:BTW, my rank is now 33 (highest 32).

升左呢 I remember that your rank is around 43 few months ago, right?

[ 本帖最后由 assembly.jc 於 2014-3-10 02:48 PM 编辑 ]

作者: assembly.jc   发布时间: 2014-03-28

引用:Yes, I/O is quite significant to the speed if SPOJ can provide some standard way to dual with I/O to all, the running time will be reflected to the speed of algorithm much truly.

Agree. It would be great if the system doesn't count the I/O time. In addition to what you said, other languages which have slow I/O can be accepted too.

引用:Would you suggests some interesting problems? Are some problems related to graphic or maths? or there exists some problems that need familiar with existing algorithm and can't to be solved immediately ?

Sure. The headache is I don't know those to be suggested, which are interesting to me, are interesting to others as well. Anyway, I'll try to post some to see.
With over 10,000 problems, you can imagine the great variety there. Quite a number of them involves maths. Geometry, series and probability are very common. Of course, there are also a lot of problems that require well-known algorithms to solve them in time. Graph theory is a hit topic. Besides, some require particular data structure for speed optimization. Examples are segment tree and binary indexed tree. Finally, there are some that require ad-hoc algorithms to solve. That is there are no suitable well-known algorithms and you have to derive them yourselves.
The following is the link for the SPOJ problem classifier:

引用:升左呢 I remember that your rank is around 43 few months ago, right?

You have a good memory.

作者: fitcat07   发布时间: 2014-03-28

作者: form5   发布时间: 2014-03-28

作者: fitcat07   发布时间: 2014-03-28

作者: assembly.jc   发布时间: 2014-03-28

作者: assembly.jc   发布时间: 2014-03-28

引用:原帖由 assembly.jc 於 2014-3-12 07:52 AM 发表

just a suggestion...

是否可以加上问题与那一种算法或资料结构有关，使初学者在解题之余学习到相关算法的知识

我谂做得编程挑战嘅人，都唔会系初学者。无番一年半载编程经验，应该应付唔到...佢哋可能连输入输出、循环使用方法、甚至语法都唔太清楚。如果佢哋发帖提问，你唔答佢唔系咁好，答佢又唔知点落手，唔可能将本书写嘅嘢，喺呢度又写一次...
初学者应该做书入面尐练习，SPOJ 题目对初学者嚟讲，实在太深啦。正如我所讲，佢哋可以做 SPOJ 内 BSCPROG，题目非常浅，好适合。
另外，如果一放条题目，就事先讲明用哪一种算法或资料结构，咁就失去编程挑战嘅原意，等同「剧透」，咁就唔好玩嘞。
但系我同意过咗一段时间后，可以给出一尐提示，如算法、资料结构或时间复杂度等。

作者: fitcat07   发布时间: 2014-03-28

好耐冇玩了

作者: Susan﹏汪汪   发布时间: 2014-03-28

作者: me888   发布时间: 2014-03-28

引用:原帖由 fitcat07 於 2014-3-12 12:00 PM 发表
我谂做得编程挑战嘅人，都唔会系初学者。无番一年半载编程经验，应该应付唔到...佢哋可能连输入输出、循环使用方法、甚至语法都唔太清楚。如果佢哋发帖提问，你唔答佢唔系咁好，答佢又唔知点落手， ...

Hi fitcat,

剧透的内容作反白处理是否可以考虑？
不过就我个人而言，之前尝试过二道题目，纵使知道了解题的思路，仍会花大量时间去尝试寻找有没有更佳的解法。所以提示对我而言并没有减低题目的挑战性。之前提议给出提示的目的只是希望降低入门的门槛，吸引更多的朋友参与，一起讨论，在交流的过程中了解其他人的想法，从中获益。但另一方面，若如你所言，他们连「输入输出、循环使用方法、甚至语法都唔太清楚」，那确是不好办

[ 本帖最后由 assembly.jc 於 2014-3-12 09:09 PM 编辑 ]

作者: assembly.jc   发布时间: 2014-03-28

引用:原帖由 assembly.jc 於 2014-3-12 07:52 PM 发表


Hi fitcat,

剧透的内容作反白处理是否可以考虑？ 尝试寻找有没有更佳的解法。所以提示对我而言并没有减低题目的挑战性。之前提议给出提示的目的只是希望降低入门的门槛，吸引更多的朋友参与，一 ...

好似以前咁....大家一齐去破解咪得lor

作者: Susan﹏汪汪   发布时间: 2014-03-28

作者: Susan﹏汪汪   发布时间: 2014-03-28

引用:原帖由 Susan﹏汪汪 於 2014-3-12 08:02 PM 发表
好似以前咁....大家一齐去破解咪得lor

看题目的难度吧，有的 classical problems 试多次还是 not accept 会很咀丧

作者: assembly.jc   发布时间: 2014-03-28

引用:原帖由 assembly.jc 於 2014-3-12 09:31 PM 发表

看题目的难度吧，有的 classical problems 试多次还是 not accept 会很咀丧

第一个问题应是问题的设计。
我印像中那些题目有时间限制，而该时间限制不会按选用的电脑语言不同而作适当的调整。
某程度上可以说，每条题目都是做 benchmark 测试。
不选用 C/C++ 、 Pascal 等语言，相对难度一定较大。

作者: xianrenb   发布时间: 2014-03-28

作者: me888   发布时间: 2014-03-28

引用:原帖由 xianrenb 於 2014-3-13 08:25 AM 发表

第一个问题应是问题的设计。
我印像中那些题目有时间限制，而该时间限制不会按选用的电脑语言不同而作适当的调整。
某程度上可以说，每条题目都是做 benchmark 测试。
不选用 C/C++ 、 Pascal 等语言，相对难度 ...

Hi xianrenb,

有些题目好像对执行速度较慢的电脑语言(e.g. Java) 有比较寛松的时间限制。我的经验不多，但就之前的经验来看，重点还是解题的logic，若能找到题目的本质，时间上还是足够的。

作者: assembly.jc   发布时间: 2014-03-28

作者: assembly.jc   发布时间: 2014-03-28

Hi Jc, 要用 intranet 嘅软件系复杂啲啦，Standalone 嘅电脑就易搞啲，不过以我旧嘅IT人想法，系好难去追，去学日新月异嘅电脑语言先至咁想下啫。终生学习先至系正确嘅人生态度。

[ 本帖最后由 me888 於 2014-3-13 10:25 AM 使用 编辑 ]

作者: me888   发布时间: 2014-03-28

我同意一开始就做唔到，感觉会好灰。
大家如果觉得难，我会尝试贴上 Tutorial （教学）类嘅题目，睇睇大家反应。
又或一个星期后，加入提示，甚至解答方法。
其实，正如汪汪所讲，有问题唔识，大家一齐研究，咁先好玩。
呢度有好多高手，曾经帮我解答咗好几个问题，汪汪系其一，感谢。

作者: fitcat07   发布时间: 2014-03-28

至於时间限制与编程语言关系，无错用最快嘅语言，一定有著数。亦令人明白，点解今时今日，重要学 C/C++。
大部分问题，除咗 C/C++ 外，Java 基本上都能通过，因为 Java 执行速度上都算系快。
此外，我相信 Scala 同 Haskell 都可以，因为速度上，唔会慢 Java 好多。
至於脚本语言，如 Python、Perl、Ruby、JavaScript 等，就好难讲。Python 大约一半半机会 OK，其余多数唔得，因为实在太慢。
其他唔太多人用嘅语言，我就唔太清楚。我曾经试过用 Go，但可能 SPOJ 嘅编译器版本太旧，过唔到。

如果玩 Challenge （挑战）类问题，咁就好唔同。
有尐系限制某尐语言，如 Brainfuck、Whitespace、INTERCAL。如果你用过（我做过几题）呢尐语言，就会知好X难。
又有尐系斗源码档字元数，越少越高分。可能要用 bsh、awk 呢尐 Unix/Linux 支援嘅语言写，又或要用脚本语言如 Perl，先可以攞到高分。

作者: fitcat07   发布时间: 2014-03-28

引用:原帖由 assembly.jc 於 2014-3-13 09:50 AM 发表

Hi xianrenb,

有些题目好像对执行速度较慢的电脑语言(e.g. Java) 有比较寛松的时间限制。我的经验不多，但就之前的经验来看，重点还是解题的logic，若能找到题目的本质，时间上还是足够的。

今日再看看，如：
http://www.spoj.com/problems/SOLVING/
http://www.spoj.com/problems/SELF/
http://www.spoj.com/problems/FAST_BF2/

时间限制应该分别是： 2s 、 1s 及 0.009s 。
我看就应该没有分电脑语言有不同的时间限制。
或者你是指某些题目指定使用 Java 吧！
但我想指出的是，出题者很多没有考虑不同电脑语言本身效能上的分别。
又或者，目的本来就是想出难题考人。
某程度上可说只有选用合适的电脑语言才有答对的可能。

作者: xianrenb   发布时间: 2014-03-28

作者: fitcat07   发布时间: 2014-03-28

引用:原帖由 me888 於 2014-3-13 10:15 AM 发表
Hi Jc, 要用 intranet 嘅软件系复杂啲啦，Standalone 嘅电脑就易搞啲，不过以我旧嘅IT人想法，系好难去追，去学日新月异嘅电脑语言先至咁想下啫。终生学习先至系正确& ...

Hi me888,

是的，终生学习是需要的，特别是 I.T.或 programming 这领域，日新月异，新的语言，新的概念层出不穷，有的时候就算工作上或学业上未必需要，但总都要学一学，以便其他人谈论时能答上一二句，感觉未与时代脱节，或者是出於好奇，总之在这个领域总有新的有趣的东西可以学，可以知，就如同八挂杂志一样，唔会有闷场。但精通某一语言或技术又是另一回事，就算世界顶尖的 programmer，要从零开始到可以利用新学到 的 language 写到一个有专业水准的软件，也需要一，二年的时间 (这是 joel 观察所得，http://local.joelonsoftware.com/wiki/%E9%A6%96%E9%A0%81)。更何况是一般的凡人。所以，要麽精通，要麽青蚲点水式的什么也学一学，二者不可兼得，这是这领域的一个 paradox，也是终生学习取舍的难处所在。

[ 本帖最后由 assembly.jc 於 2014-3-13 09:56 PM 编辑 ]

作者: assembly.jc   发布时间: 2014-03-28

引用:原帖由 xianrenb 於 2014-3-13 05:33 PM 发表

今日再看看，如：
http://www.spoj.com/problems/SOLVING/
http://www.spoj.com/problems/SELF/
http://www.spoj.com/problems/FAST_BF2/

时间限制应该分别是： 2s 、 1s 及 0.009s 。
我看就应该没有分电脑 ...

Hi xianrenb,

这是因为之前做过的这个 problem (http://www.spoj.com/problems/MAX_NUM/)，题目限制是 3秒，但 best soluation 有个 java 的 submission，5 秒也给通过了(http://www.spoj.com/ranks/MAX_NUM/start=200)，所以我以为对Java 有放寛的处理

[ 本帖最后由 assembly.jc 於 2014-3-13 09:57 PM 编辑 ]

作者: assembly.jc   发布时间: 2014-03-28

引用:原帖由 fitcat07 於 2014-3-13 05:04 PM 发表
我同意一开始就做唔到，感觉会好灰。
大家如果觉得难，我会尝试贴上 Tutorial （教学）类嘅题目，睇睇大家反应。
又或一个星期后，加入提示，甚至解答方法。
其实，正如汪汪所讲，有问题唔识，大家一齐研究 ...

Hi fitcat,

一起研究当然固然是好，但新手和老手始终有距离，新手的难，可能对你和汪汪而言很简单，但你们所讨论的算法，我和一般新手可能连名字也没有听闻，更谈不上参与了...

作者: assembly.jc   发布时间: 2014-03-28

引用:原帖由 assembly.jc 於 2014-3-13 10:08 PM 发表

Hi fitcat,

一起研究当然固然是好，但新手和老手始终有距离，新手的难，可能对你和汪汪而言很简单，但你们所讨论的算法，我和一般新手可能连名字也没有听闻，更谈不上参与了...

汪汪都系自学的

作者: Susan﹏汪汪   发布时间: 2014-03-28

Good point !

作者: me888   发布时间: 2014-03-28

作者: xianrenb   发布时间: 2014-03-28

作者: fitcat07   发布时间: 2014-03-28

引用:原帖由 assembly.jc 於 2014-3-13 10:08 PM 发表
一起研究当然固然是好，但新手和老手始终有距离，新手的难，可能对你和汪汪而言很简单，但你们所讨论的算法，我和一般新手可能连名字也没有听闻，更谈不上参与了...

你未听过，又如何？正如汪汪所讲，最重要系自学。
你系咪想学？想嘅话，用 google 又或维基网上搵一搵，大把资料立即出现喺你眼前。我自己就系咁学番嚟。重有，讨论区设立嘅目的，就系为咗「讨论」，系吗？当你搵完资料，但重有唔明，又或消化唔到，贴上嚟问，相信会有人乐意解答。
唔搵资料，又或唔愿睇者，就贴上嚟问，咁就好难有人会答嘞。

作者: fitcat07   发布时间: 2014-03-28

作者: xianrenb   发布时间: 2014-03-28

引用:原帖由 xianrenb 於 2014-3-14 01:18 PM 发表
...我就觉得要认叻都有好多种...

点解有人会咁在意我所讲嘅嘢，一切迷题终於解开啦如果有人有跟帖，就明白我从无认过叻。相反，认渣就有。

呢尐系我之前发帖，形容自己嘅字眼：

将勤补拙
同尐劲人冇得比
有好多题都唔识
一齐研究
令我可以学到嘢
code4food （网友名，最近好少出场）比我劲得多

相信好多人都可以做证。

原来讲下自己排名，就有人「唔抵得」，觉得我「认叻」。呢种心态，真系...

作者: fitcat07   发布时间: 2014-03-28

汪汪完全冇排名

作者: Susan﹏汪汪   发布时间: 2014-03-28

引用:原帖由 fitcat07 於 2014-3-14 03:46 PM 发表
点解有人会咁在意我所讲嘅嘢，一切迷题终於解开啦如果有人有跟帖，就明白我从无认过叻。相反，认渣就有。

呢尐系我之前发帖，形容自己嘅字眼：

将勤补拙
同尐劲人冇 ...

唔知你曲解定系我误导。
即是说，兴趣的事不必沉迷。
有人玩遥控飞机、有人玩自制 hi-fi 。
样样野都有所谓的排名。

我就好简单，试过玩 SPOJ 后发觉学不到什么，但明明自己用家里的电脑应是 pass 的（好像那次是用 Python），於是就连最简单的题目都不做，不继续玩了。
我无 check 过我在 SPOJ 的排名，我估是最后的一位吧？

无疑，你是论坛中较聪明的一位，但你应明白不是所有人都像你般聪明。
对於一般人来说，我提及不要沉迷是提醒他们，有些题目的要求实在太高（如果不是整人的话），不必不断的花时间“死试烂试”。

[ 本帖最后由 xianrenb 於 2014-3-14 06:26 PM 编辑 ]

作者: xianrenb   发布时间: 2014-03-28

作者: Susan﹏汪汪   发布时间: 2014-03-28

作者: xianrenb   发布时间: 2014-03-28

作者: Susan﹏汪汪   发布时间: 2014-03-28

作者: xianrenb   发布时间: 2014-03-28

作者: Susan﹏汪汪   发布时间: 2014-03-28

作者: Susan﹏汪汪   发布时间: 2014-03-28

试下上面提过

http://www.spoj.com/problems/MAX_NUM/

复制内容到剪贴板代码:import unittest

def find_max(number, n_digits):
result = ''

while n_digits > 0 and len(number) > 0 :
a = number[:-n_digits+1]
max_a = max(a) if len(a)>0 else max(number)
index_max_a = number.rindex(max_a)
number = number[index_max_a+1:]
result = '%s%s'%(result, max_a)
n_digits = n_digits - 1

return result


class TestFindMaxNumbers(unittest.TestCase):

def test_1223_give_23(self):
max_num = find_max('1223', 2)
self.assertEqual(max_num, '23')


def test_8756_give_87(self):
max_num = find_max('8756', 2)
self.assertEqual(max_num, '87')


def test_8576_give_87(self):
max_num = find_max('8576', 2)
self.assertEqual(max_num, '87')


def test_8567_give_87(self):
max_num = find_max('8567', 2)
self.assertEqual(max_num, '87')


def test_8567_give_8(self):
max_num = find_max('8567', 1)
self.assertEqual(max_num, '8')


def test_5678_give_8(self):
max_num = find_max('5678', 1)
self.assertEqual(max_num, '8')


def test_5678_give_678(self):
max_num = find_max('5678', 3)
self.assertEqual(max_num, '678')


def test_05678_give_678(self):
max_num = find_max('05678', 3)
self.assertEqual(max_num, '678')


def test_08576_give_87(self):
max_num = find_max('08576', 2)
self.assertEqual(max_num, '87')


if __name__ == '__main__':
unittest.main()

[ 本帖最后由 form5 於 2014-3-14 11:50 PM 编辑 ]

作者: form5   发布时间: 2014-03-28

引用:原帖由 xianrenb 於 2014-3-14 08:26 AM 发表

那就真的不是考 algorithm 了。
因为那极有可能是先前定 3s 以上，结果有人 5s 多完成，於是乎改时间为 3s 。
如果真是考算法， 5s 与 0.5s 很大可能同属同一种 big o notation 时间，根本无必要这样改。
可能出 ...

Hi xianrenb,

原来我搅错左，正确的计时方法 fitcat 兄己经解释了，误导了你，唔好意思。

其实尚算公平，而且有效考验到算法速度的，虽然之前也提及过I/O 的影响也不小，但最主要还是算法本身的速度，就以这一条题目(不是之前提及 MAX_NUM那一条) 为例，主要还是应用 sorting and searching 的方法去解决。但 O(N^2)的sorting 算法全过不了关 (我好像是试了 9种，全都是在最快的I/O实作基础上 submit 的)，就算 average 有O(nlogn) 的 quick sort 也失败了，只有最坏情况也是O(n log n) 和 O(n) 的 sorting 算法才合格。所以我觉得问题设计者设计问题和testing case时 没有偏向性，主要还是针对算法本身。而且，不得不偑服问题设计者设计的 test cases。很微少的问题也能测试到出来。我从中可以知道自己的 implementation 有无问题，其实也间接帮了我

[ 本帖最后由 assembly.jc 於 2014-3-15 02:46 AM 编辑 ]

作者: assembly.jc   发布时间: 2014-03-28

作者: assembly.jc   发布时间: 2014-03-28