Author Topic: 程序竞赛  (Read 35922 times)

fzy

  • Hero Member
  • *****
  • Posts: 520
程序竞赛
« on: 十一月 30, 2005, 10:49:47 am »
一个长为n的数组,里面的数为1到n-1的整数。找出一个重复的值。

有一个条件:能够用的存储单元有限制:存在一个与n无关的c,使用的存储单元不超过c*log(n)。例如n是64位整数时,使用的存储单元不能超过8c bytes,即最多存c个64位整数。(数组是 read only 的。可用内存是指数组以外能存能取的部分。)

还有一个条件:程序的速度要求是 O(n)。

万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1830
Re: 程序竞赛
« Reply #1 on: 十一月 30, 2005, 11:45:03 am »
Is the repeated number unique? Or there are more than one repeated numbers? If it is unique, then the repeated value is sum(array)-n*(n-1)/2, and should be fairly easy to find the location.

idiot94

  • Sr. Member
  • ****
  • Posts: 484
Re: 程序竞赛
« Reply #2 on: 十一月 30, 2005, 11:49:54 am »
I probably did not understand your question, but if you do this:
take the sum of all the numbers in that array (i.e., a=0;  for i=1 to n, a=a+array(i);  then a-.5*n*(n-1) is the repeated number).
It takes n+1 addition and do not use any memory ...
In general, the men of lower intelligence won out. Afraid of of their own shortcomings ... they boldly moved into action. Their enemies, ...  thought there was no need to take by action what they could win by their brains. Thucydides, History

idiot94

  • Sr. Member
  • ****
  • Posts: 484
Re: 程序竞赛
« Reply #3 on: 十一月 30, 2005, 11:50:40 am »
oops... Prof. W already pointed it out :D
In general, the men of lower intelligence won out. Afraid of of their own shortcomings ... they boldly moved into action. Their enemies, ...  thought there was no need to take by action what they could win by their brains. Thucydides, History

fzy

  • Hero Member
  • *****
  • Posts: 520
Re: 程序竞赛
« Reply #4 on: 十一月 30, 2005, 12:18:49 pm »
Quote from: 万精油
Is the repeated number unique? Or there are more than one repeated numbers? If it is unique, then the repeated value is sum(array)-n*(n-1)/2, and should be fairly easy to find the location.

It may not be unique.  :-(

Quote from: idiot94
I probably did not understand your question, but if you do this:
take the sum of all the numbers in that array (i.e., a=0;  for i=1 to n, a=a+array(i);  then a-.5*n*(n-1) is the repeated number).
It takes n+1 addition and do not use any memory ...

It does need some memory to store the sum. Also since the sum is in the range of n^2, which may be larger than the largest data type your language can handle, you also need to implement a new addition.  :evil:

idiot94

  • Sr. Member
  • ****
  • Posts: 484
Re: 程序竞赛
« Reply #5 on: 十一月 30, 2005, 12:51:00 pm »
ok, so I did not understand your question then.. (and i still do not understand ;D )...
In general, the men of lower intelligence won out. Afraid of of their own shortcomings ... they boldly moved into action. Their enemies, ...  thought there was no need to take by action what they could win by their brains. Thucydides, History

万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1830
Re: 程序竞赛
« Reply #6 on: 十一月 30, 2005, 11:37:54 pm »
Quote
Also since the sum is in the range of n^2, which may be larger than the largest data type your language can handle, you also need to implement a new addition.

This part is easy, if n is odd, mod n, if n is even, mod n-1.

万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1830
Re: 程序竞赛
« Reply #7 on: 十二月 01, 2005, 10:22:24 am »
Quote
ok, so I did not understand your question then.. (and i still do not understand


Just to clarrify the problem so that other people can understand it too.

The key here is the memory constraint. If there's no memory constraint, then, you can allocate an array of size n (call it B), initialize it to all zeros. Pass through the original data, update the array B along the way. When an element of B is greater than 1, then you have found the repeated data.  With the memory constraints, you cannot allocate this array B, well, you can, but with a much smaller size c*log(n), and somehow stuff all the information into this smaller array and still be able to differentiate the repeated data. I am thinking of bracketing with a log scale, (which is a method many people have used), but haven't found a good way yet. This is a good problem.

贼++

  • Full Member
  • ***
  • Posts: 153
    • Email
Re: 程序竞赛
« Reply #8 on: 十二月 01, 2005, 03:34:49 pm »
空间是log(n)的,时间是nlog(n)的:

一个counter是奇数个数,一个counter是4k+{1,2}的个数,一个counter是8k+{1,2,3,4}的个数。一共需要log(n)个counters,每次进来一个数,就update所有counter一次。

虽然这个办法花时间,但是有个好处:可以找到所有重复的数(原题只要求找到1个)。

万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1830
Re: 程序竞赛
« Reply #9 on: 十二月 01, 2005, 04:28:58 pm »
Quote
一个counter是奇数个数,一个counter是4k+{1,2}的个数,一个counter是8k+{1,2,3,4}的个数。一共需要log(n)个counters,每次进来一个数,就update所有counter一次。

So, you use each bit as a bracket. Very smart. Since the ith bit covers 2^i numbers, it is a log scale bracket like what I mentioned in my previous post. I was thinking along the same line, but not as fast as you. It is a good exercise to figure out how to use the updated counter information to find the repeated numbers(took me a while. :( )

fzy

  • Hero Member
  • *****
  • Posts: 520
Re: 程序竞赛
« Reply #10 on: 十二月 01, 2005, 04:53:10 pm »
Quote from: 贼++
空间是log(n)的,时间是nlog(n)的:


The space is not log(n) either, it is log(n)^ 2.  :-(

贼++

  • Full Member
  • ***
  • Posts: 153
    • Email
Re: 程序竞赛
« Reply #11 on: 十二月 01, 2005, 05:59:05 pm »
Quote from: 贼++
空间是log(n)的,时间是nlog(n)的:


The space is not log(n) either, it is log(n)^ 2.  :-(
对。那就改成:第一次数奇数个数;如果奇数比偶数多,第二次数4K+1个数;如果4K+1少,第三次数8K+3个数。。。
空间log(n),时间nlog(n)

万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1830
Re: 程序竞赛
« Reply #12 on: 十二月 02, 2005, 11:22:13 am »
Quote
对。那就改成:第一次数奇数个数;如果奇数比偶数多,第二次数4K+1个数;如果4K+1少,第三次数8K+3个数。。。
空间log(n),时间nlog(n)

With this new algorithm, the memory is not related to n at all. It is a constant (I only need 6 storage place in my implementation of this new algorithm). Thus, the problem becomes even more interesting. The problem should be rephrased as finding the repeated value using 6 storage place (or a constant to make it more general).

The time for this algorithm is n*log(n), which is not as good as FZY's original requirement of O(n). But I think this is a better solution, because the key of this problem is storage place, and a constant is much better than a constant times log(n). On the other hand, time is also an important factor, otherwise, we can easily design a O(n^2) algorithm which uses less storage place (just check one by one).
« Last Edit: 十二月 02, 2005, 11:46:08 am by 万精油 »

fzy

  • Hero Member
  • *****
  • Posts: 520
Re: 程序竞赛
« Reply #13 on: 十二月 02, 2005, 12:29:36 pm »
Quote from: 万精油
With this new algorithm, the memory is not related to n at all. It is a constant (I only need 6 storage place in my implementation of this new algorithm). Thus, the problem becomes even more interesting. The problem should be rephrased as finding the repeated value using 6 storage place (or a constant to make it more general).

You mean you used only 6 bytes or 6 other units? If it is 6 places for numbers of size n then it is 6*log(n). The first one alone (第一次数奇数个数) may be more than 6 bytes.

万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1830
Re: 程序竞赛
« Reply #14 on: 十二月 02, 2005, 02:46:02 pm »
Quote
You mean you used only 6 bytes or 6 other units? If it is 6 places for numbers of size n then it is 6*log(n). The first one alone (第一次数奇数个数) may be more than 6 bytes.

贼++'s first algorithm requires log(n) counters, (log(n) bracket holders), his new algorithm requires only one counter. It is in this sense that I said it is independant of n. I need 6 integer variables. I assume your n is an integer too. From your comments, it seems your n can be greater than a long integer in C (32 bits, or 64 bits depends on  the machines).