Еще две задачки

[kirpich_spb]

Еще две интересные задачки. У первой решение совсем простое, а вот над второй придется думать (я вот довольно долго решал).

1. Продолжить последовательность: 1, 11, 21, 1112, 3112, 211213, 312213, 212223, 114213, 31121314
   
2. Дан массив длины n+1, содержащий числа от 1 до n. Используя лишь O(logn) памяти, найти за линейное время какое-нибудь

Comments

Ответ и уточняющий вопрос

[anonymous]

Предполагая, что числа двоичные, можно использовать такой алгоритм:
floor(log_2 n)+1 раз пробежаться по массиву и на j-ом пробеге,
вытаскивая j-ый бит из каждого элемента, сравнивать, каких
битов больше: если 1, то j-ый бит ответа тоже 1, иначе - 0.

Время работы этого алгоритма линейно по n, если предполагать, что n
ограничено константой, но тогда достаточно константной памяти.
Если же не предполагать, что n ограничено константой, то этот алгоритм
не линеен по времени (и бегать по массиву надо floor(log_2 n)+1 раз, и
вытаскивать бит из длинного числа).
Таким образом, возникает вопрос: этот ли алгоритм имелся в виду,
или условие можно уточнить, потребовав константную память?
(Может, стоит задать вычислительную модель? :)

Заранее спасибо за ответ!

Я - http://gas-teach.narod.ru (и к последней задачке про картинку
недавно добавил комментарий тоже я).

Re: Ответ и уточняющий вопрос

[kirpich_spb]

Приятно познакомиться! =)

Этот алгоритм, на самом деле, работает не так, как хочется: если взять, например, последовательность чисел {1,1,2,2,3}, которая в двоичном виде выглядит как {01,01,10,10,11}, то ответом алгоритма будет число 3, хотя оно не повторяется.

Я, кстати, в какой-то момент тоже такой алгоритм придумал. Но я не вижу, как его быстро реализовать.

Касательно же модели, RAM-машины нам вполне достаточно будет. То есть мы умеем быстро обращаться к массиву, стандартные операции с числами делаем за 1.

problem 2

[anonymous]

how about this: implement a hash-table inside the array:

for (i=0; i < n+1; ) {
if (a[i] != i)
{
if (a[i] == a[a[i]])
print a[i] is duplicate
else
swap a[i] and a[a[i]]
}
else
i++
}

the extra space is O(logn) bits needed to store 1
number during the swap. at most one swap per
element, so the time is linear.

Re: problem 2

[kirpich_spb]

The important thing I've forgotten to mention is that the considered array is immutable.

Re: problem 2

[anonymous]

immutability wasn't part of the original question.. anyway, this needs clarification: if an element takes log(n) space (as implied by a previous answer), then it takes log(n) time to read it from the array. thus a scan of the array takes nlog(n) time. the problem cannot be solved in linear time as the array must be scanned at least once.

Re: problem 2

[kirpich_spb]

Well, we assume that to store a number from [1..n] one uses log n bits, however any operation with two such numbers takes O(1) time.

One more algorithm

[anonymous]

С прошлого года не смотрел на эту страницу, и заготовил следующий ответ

Re: One more algorithm

[kirpich_spb]

Да-да, согласен. Массив можно только читать -- про это я забыл изначально написать. Условие про память можно было бы сформулировать так: разрешается хранить лишь константное число чисел порядка n, скажем так.

Но Вы уже близки к ответу. Рассмотрение циклов -- шаг на пути к правильному ответу. Я шел так же. =)

Re: One more algorithm

[anonymous]

OK, so developing on this idea of jumping:

1) start with a[0], start jumping a[a[0]], a[a[a[0]]] and so on. if we encounter an element such that a[i] = a[a[i]], return to the beginning and repeat with a[1] and so on.

2) if we return during the jump back to a[0], proceed to a[1] and repeat.

3) duplicates will create an infinite loop and neither 1) or 2) would occur. the question is how to detect a loop efficiently. in the worst case, any infinite loop can be detected in time n by keeping a counter of jumps in O(1) space. since need to find no more than loop, total complexity is theta(n).

interestingly, it seems that if we need to find *all* duplicates, the complexity is theta(n^2). is that correct?

Re: One more algorithm

[kirpich_spb]

Hm, consider the following array of length n+1:
{2,3,4,5,...,n-2,1,n-1,n-1}. It contains a linear length loop and your algorithm will walk along this loop a linear number of times. Thus, the total number of steps will be quadratic. However you are going in the right direction. =)

I haven't thought about finding all duplicates, but I think that you are right. Just because the number of different duplicates itself can be linear.