Задачки на подумать

№	Пользователь	Рейтинг
1	tourist	3880
2	jiangly	3669
3	ecnerwala	3654
4	Benq	3627
5	orzdevinwang	3612
6	Geothermal	3569
6	cnnfls_csy	3569
8	jqdai0815	3532
9	Radewoosh	3522
10	gyh20	3447

№	Пользователь	Вклад
1	awoo	161
2	maomao90	160
3	adamant	156
4	maroonrk	153
5	atcoder_official	149
6	-is-this-fft-	148
6	SecondThread	148
8	Petr	147
9	nor	144
10	cry	143

Навеяно вот этим постом, про поиск неповторяющихся элементов. Приведу две задачки типа для собеседований.

Даны два списка цифр (от 0 до 9) которые представляют собой запись длинных чисел, например список 3 -> 2 -> 6 -> 7 -> 8 это число 32678. Требуется сложить два этих числа используя O(1) дополнительной памяти. По спискам мы можем перемещаться только вперед, по спискам можно проходить несколько раз.
Заметим что никакие хаки не позволяют нам двигаться по спискам в обратном направлении, по условию задачи.
Дан однонаправленный список, где следующий элемент задается его адресом — переменной фиксированной длины, например 8 байтовой. Придумать хак, позволяющий двигаться по списку в обратном направлении. Использовать O(1) памяти. Более подробно опишу что представляет из себя элемент списка на конкретном примере кода

struct TListElement {
    int Val;
    TListElement* Next;
};

PS: Ответы прятать под спойлер (в предыдущую правку)

Комментарии (15)

Написать комментарий?

yarrr

12 лет назад, # |

← Rev. 2 →

Спойлер.

→ Ответить

goo.gl_SsAhv

12 лет назад, # ^ |

← Rev. 3 →

мы не можем изменять список. нужно использовать его в таком виде, в котором он есть.
UPD: Это гон, я ошибся

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

kb.

Я правильно понимаю, что 1 — вот эта задача?

Ну в этой задаче ничто не мешает тебе считать два числа в два мегабайтных массива, пройти по ним в любом порядке и вывести число в третий мегабайтный массив (в любом порядке опять же). А здесь у тебя память должна быть константой, идти по спискам можно только в одном направлении.

Когда я сдавал эту задачу (больше года назад), еще не знал, что можно использовать не 4-х байтовые типы данных =) Поэтому делал так.

Ну да, твое решение годится для первой задачи.

proVIDec

А что касательно времени?

ну подразумевается максимально эффективно. Первая задача решается за O(n). Во второй переход к предыдущему элементу можно делать за O(1).

Jokser

Вопрос по первой задаче. Можно ли находясь в некоторой элементе списка "поглядеть" значение следующего, но не переходя в него непосредственно.

конечно, даже если нет, ты можешь завести еще одну переменную, и хранить в ней значение прыдыдущего, это одно и то же в некотором смысле.

1-я задача. Решение в правке.

список изменять нельзя. но идея очень близка.

Правка

ответ

Блог пользователя goo.gl_SsAhv