### Author Topic: 程序竞赛  (Read 44121 times)

#### fzy

• Hero Member
• Posts: 520
##### 程序竞赛
« on: 十一月 30, 2005, 10:49:47 am »

#### 万精油

• Hero Member
• Posts: 1831
##### 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
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;&nbsp; for i=1 to n, a=a+array(i);&nbsp; 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.

#### 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 )...
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

#### 万精油

• Hero Member
• Posts: 1831
##### 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.

#### 万精油

• Hero Member
• Posts: 1831
##### 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
##### Re: 程序竞赛
« Reply #8 on: 十二月 01, 2005, 03:34:49 pm »

#### 万精油

• Hero Member
• Posts: 1831
##### Re: 程序竞赛
« Reply #9 on: 十二月 01, 2005, 04:28:58 pm »
Quote

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: 贼++

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

#### 贼++

• Full Member
• Posts: 153
##### Re: 程序竞赛
« Reply #11 on: 十二月 01, 2005, 05:59:05 pm »
Quote from: 贼++

The space is not log(n) either, it is log(n)^ 2.&nbsp;

#### 万精油

• Hero Member
• Posts: 1831
##### Re: 程序竞赛
« Reply #12 on: 十二月 02, 2005, 11:22:13 am »
Quote

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.