|
hml
|
|
journeyman
|
|
|
|
|
|
|
Рег.: 15.09.2005
|
|
Сообщений: 69
|
|
|
|
Рейтинг: 0
|
|
help me: i ca'nt solve it. (algorithm)
15.09.2005 22:29
|
|
|
An array A[1.. n] contains all the integers from 0 to n except one. It would be easy to
determine the missing integer in O(n) time by using an auxiliary array B[0 .. n] to record
which numbers appear in A. In this problem, however, we cannot access an entire integer in A
with a single operation. The elements of A are represented in binary, and the only operation
we can use to access them is "fetch the jth bit of A[i]," which takes constant time.
Show that if we use only this operation, we can still determine the missing integer in O(n)
time.
Перенесено модератором DarkGray из раздела Programming
Редактировал DarkGray (16.09.2005 02:28)
|
|
|
hml
|
|
journeyman
|
|
|
|
|
|
|
Рег.: 15.09.2005
|
|
Сообщений: 69
|
|
|
|
Рейтинг: 0
|
|
plz: help me. i can't solve it(algorithm)
[re: *NONE*]
15.09.2005 22:32
|
|
|
An array A[1.. n] contains all the integers from 0 to n except one. It would be easy to
determine the missing integer in O(n) time by using an auxiliary array B[0 .. n] to record
which numbers appear in A. In this problem, however, we cannot access an entire integer in A
with a single operation. The elements of A are represented in binary, and the only operation
we can use to access them is "fetch the jth bit of A[i]," which takes constant time.
Show that if we use only this operation, we can still determine the missing integer in O(n)
time.
Присоединено модератором Robin
|
|
|
Driver
|
|
Pooh-Bah
|
|
|
|
|
|
|
Рег.: 12.11.2004
|
|
Сообщений: 2185
|
|
|
|
Рейтинг: 1679
|
|
Re: plz: help me. i can't solve it(algorithm)
[re: hml]
15.09.2005 22:53
|
|
|
You can determinate the missing integer in the time O(k*n), where k - the number of the bits, used for the coding of the each integer, and only one additional variable is needed. It's very simple algorithm, so you must think it youself.
и кроме того, если есть дополнительная информация про n, то может быть даже не придется считывать все биты для всех чисел.
|
|
|
aset
|
|
boar
|
|
|
|
|
|
|
Рег.: 05.09.2003
|
|
Сообщений: 36470
|
|
|
|
Рейтинг: 6913
|
|
Re: help me: i ca'nt solve it. (algorithm)
[re: hml]
15.09.2005 22:56
|
|
|
The first algorithm, that is with aux. array -- could you describe it in formulas including O(n)?
|
may have come in contact with nuts |
|
|
hml
|
|
journeyman
|
|
|
|
|
|
|
Рег.: 15.09.2005
|
|
Сообщений: 69
|
|
|
|
Рейтинг: 0
|
|
Re: plz: help me. i can't solve it(algorithm)
[re: Driver]
15.09.2005 23:00
|
|
|
it 's not accepted solution.
O(k*n) ~ O (n log n) because k = log n.
|
|
|
hml
|
|
journeyman
|
|
|
|
|
|
|
Рег.: 15.09.2005
|
|
Сообщений: 69
|
|
|
|
Рейтинг: 0
|
|
Re: help me: i ca'nt solve it. (algorithm)
[re: aset]
15.09.2005 23:06
|
|
|
the first algorithm:
int s=0;
for(int i=0;i<n;i++) s+=a[i];
printf("the missing is %d\n", (n*(n-1)/2) -s);
|
|
|
Stress
|
|
|
|
|
|
|
|
|
Рег.: 05.08.2005
|
|
Сообщений: 1226
|
|
|
|
Рейтинг: 0
|
|
Re: help me: i ca'nt solve it. (algorithm)
[re: hml]
15.09.2005 23:29
|
|
|
Obviously, to determine the missing number we have to fetch all the bits.
There is O(n*log(n)) of them, so this problem looks fishy.
|
|
|
Driver
|
|
Pooh-Bah
|
|
|
|
|
|
|
Рег.: 12.11.2004
|
|
Сообщений: 2185
|
|
|
|
Рейтинг: 1679
|
|
Re: plz: help me. i can't solve it(algorithm)
[re: hml]
15.09.2005 23:29
|
|
|
I can do it in O(2*n) operation of "fetch the jth bit of A[i]"
you must determinate which bits are absent 
|
|
|
Holden
|
|
tankist
|
|
|
|
|
|
|
Рег.: 16.12.2004
|
|
Сообщений: 593
|
|
|
|
Рейтинг: 0
|
|
Re: help me: i ca'nt solve it. (algorithm)
[re: hml]
15.09.2005 23:40
|
|
|
there's no auxiliary array in the algorithm u've presented. what's wrong about such a solution?
|
|
|
hml
|
|
journeyman
|
|
|
|
|
|
|
Рег.: 15.09.2005
|
|
Сообщений: 69
|
|
|
|
Рейтинг: 0
|
|
Re: plz: help me. i can't solve it(algorithm)
[re: Driver]
15.09.2005 23:45
|
|
|
O(2*n) is ok. can u show details of your solution?
|
|
|
hml
|
|
journeyman
|
|
|
|
|
|
|
Рег.: 15.09.2005
|
|
Сообщений: 69
|
|
|
|
Рейтинг: 0
|
|
Re: help me: i ca'nt solve it. (algorithm)
[re: Holden]
15.09.2005 23:48
|
|
|
the solution with au array:
memset(b, 0, (n+1)*sizeof(int));
for(int i=0;i<n;i++)b[a[i]]=1;
int res;
for(int i=0;i<=n;i++)if(b[i]==0)res=i;
printf("the missing is %d\n", res);
|
|
|
hml
|
|
journeyman
|
|
|
|
|
|
|
Рег.: 15.09.2005
|
|
Сообщений: 69
|
|
|
|
Рейтинг: 0
|
|
Re: help me: i ca'nt solve it. (algorithm)
[re: Stress]
15.09.2005 23:51
|
|
|
to:Stress
the problem is extracted from "Introduction to algorithms"
Thomas H. Cormen
Charles E. Leiserson
Ronald L. Rivest
Clifford Stein
The MIT Press
the problem is on page 80.
|
|
|
Khumarahn
|
|
hard fart
|
|
|
|
|
|
|
Рег.: 04.12.2002
|
|
Сообщений: 777
|
|
|
|
Рейтинг: 105
|
|
Re: plz: help me. i can't solve it(algorithm)
[re: hml]
16.09.2005 00:27
|
|
|
I can determine it in any positive (or 0) number of operations :-)))
'cause it's one!
kiddind a bit :-))
|
Leela, Leela, Leela, save him
Save Fry, save Fry
Godzilla... |
|
|
Khumarahn
|
|
hard fart
|
|
|
|
|
|
|
Рег.: 04.12.2002
|
|
Сообщений: 777
|
|
|
|
Рейтинг: 105
|
|
Re: plz: help me. i can't solve it(algorithm)
[re: Driver]
16.09.2005 00:33
|
|
|
It's also easy... If you're using n bits to store data...
|
Leela, Leela, Leela, save him
Save Fry, save Fry
Godzilla... |
|
|
Stress
|
|
|
|
|
|
|
|
|
Рег.: 05.08.2005
|
|
Сообщений: 1226
|
|
|
|
Рейтинг: 0
|
|
Re: help me: i ca'nt solve it. (algorithm)
[re: hml]
16.09.2005 00:33
|
|
|
I see.
The only possible explanation I can think of is that a ceiling for log2(n) is known a priori (then fixed-length data chunks are used for number representation).
In that case a success of both strategies you've mentioned is clear.
|
|
|
ruel
|
|
scientist
|
|
|
|
|
|
|
Рег.: 21.12.2004
|
|
Сообщений: 1011
|
|
|
|
Рейтинг: 0
|
|
Re: help me: i ca'nt solve it. (algorithm)
[re: Stress]
16.09.2005 00:42
|
|
|
Quote:
Obviously, to determine the missing number we have to fetch all the bits.
There is O(n*log(n)) of them, so this problem looks fishy.
obviously this is not true
if we have the ability to store the index in the auxilary arrays B[(n+1)/2], C[(n+1)/2] in constant time then I know the algorithm that works in O(n)
|
(1) прочтите до конца, (2) обдумайте прочитанное, (3) отвечайте по существу |
|
|
Stress
|
|
|
|
|
|
|
|
|
Рег.: 05.08.2005
|
|
Сообщений: 1226
|
|
|
|
Рейтинг: 0
|
|
Re: help me: i ca'nt solve it. (algorithm)
[re: ruel]
16.09.2005 01:03
|
|
|
What kind of index do you mean?
Suppose we have alg which finds the missing number without any fetching the jth bit of some A[i]. There is such n that two numbers K and L which differ only in their jth bit exist. We can take two different sequences of numbers: one with A[i]=K and missing L and another one with A[i]=L and missing K. The alg will be unable to distinguish the difference.
|
|
|
Stress
|
|
|
|
|
|
|
|
|
Рег.: 05.08.2005
|
|
Сообщений: 1226
|
|
|
|
Рейтинг: 0
|
|
Re: help me: i ca'nt solve it. (algorithm)
[re: hml]
16.09.2005 01:04
|
|
|
Is it possible the array is sorted in any way?
|
|
|
ruel
|
|
scientist
|
|
|
|
|
|
|
Рег.: 21.12.2004
|
|
Сообщений: 1011
|
|
|
|
Рейтинг: 0
|
|
Re: help me: i ca'nt solve it. (algorithm)
[re: Stress]
16.09.2005 01:45
|
|
|
Quote:
What kind of index do you mean?
Of course I mean the index we use to access array A.
obviously its size in bits is O(log2(n)) (because array A has n elements) so if we can store/read such numbers to/from the auxiliary arrays in constant time (as we can access the bit in constant time by using logarithmic-sized index) then I know the correct algorithm.
e.g. if RAM operations is fast (as usual in generic hardware) but array A is a kind of very slow storage with per-bit access (or bit access operation is some kind of tricky constant time calculation by some tricky algorithm).
Quote:
Suppose we have alg which finds the missing number without any fetching the jth bit of some A[i]. There is such n that two numbers K and L which differ only in their jth bit exist. We can take two different sequences of numbers: one with A[i]=K and missing L and another one with A[i]=L and missing K. The alg will be unable to distinguish the difference.
your "alg will be unable to distinguish the difference" may be
obviously your "proof" is wrong because you assume that before algorithm starts you already know the position of bit we don't access which is of course not true (e.g. if we know the lower bit is 0 then we don't have to fetch other bits of those elements in array A[1..n] that has lower bit 1 - after that you may guess the correct algorithm by yourself).
to make all things clear I can just write the algorithm
Редактировал ruel (16.09.2005 02:42)
|
(1) прочтите до конца, (2) обдумайте прочитанное, (3) отвечайте по существу |
|
|
ruel
|
|
scientist
|
|
|
|
|
|
|
Рег.: 21.12.2004
|
|
Сообщений: 1011
|
|
|
|
Рейтинг: 0
|
|
Re: help me: i ca'nt solve it. (algorithm)
[re: Stress]
16.09.2005 01:52
|
|
|
Quote:
Is it possible the array is sorted in any way?
there's nothing about this stated in our problem so the answer is obviously NO
|
(1) прочтите до конца, (2) обдумайте прочитанное, (3) отвечайте по существу |
|
Список
Плоский
Дерево
