За один проход

    Среди задач по программированию часто попадаются такие: дана последовательность однотипных элементов (обычно это числа), требуется за один проход по ней найти какую-нибудь характеристику (среднее квадратическое отклонение, количество минимальных элементов, непрерывный участок с наибольшей суммой...) Дополнительное ограничение — последовательность может быть очень длинной, и в память не поместится. Других ограничений на элементы последовательности, обычно, не накладывается.
    С этими задачами всё, более или менее, понятно: нужно найти то, что на мехмате МГУ называют «индуктивным расширением» искомой функции, и реализовать её вычисление. Если найти не удалось (требуемый объём памяти слишком велик), то задача не решается.
    Но попадаются и другие задачи. В них есть дополнительные ограничения на элементы последовательности в совокупности, и эти ограничения приходится существенно использовать для решения (и проверять их не надо). Простейшая такая задача выглядит так:

    Задача 1. В последовательности записаны целые числа от 1 до N в произвольном порядке, но одно из чисел пропущено (остальные встречаются ровно по одному разу). N заранее неизвестно. Определить пропущенное число

    Решение очевидно: просматриваем числа, находим их количество K и сумму S. По условию, N=K+1, значит, сумма чисел от 1 до N будет равна (K+1)*(K+2)/2, и пропущенное число равно (K+1)*(K+2)/2-S. Если вы почему-то боитесь переполнений, то работайте с беззнаковыми числами (там переполнения не страшны — но будьте осторожны при вычислении (K+1)*(K+2)/2 :) ), или вместо суммы ищите XOR всех чисел.

    Задача 2. В последовательности записаны целые числа. Одно из чисел встречается ровно один раз, остальные — по два раза. Найти число, которое встречается один раз.

    Здесь тоже всё просто: найдем XOR всех чисел — он и будет ответом. В самом деле, если какой-то бит в искомом числе равен нулю, то во всей последовательности он будет равен 1 в чётном числе элементов, и его значение в XOR равно нулю. В противном случае, аналогично, его значение в XOR равно 1. Или, проще говоря, одинаковые элементы при суммировании взаимоуничтожатся.

    Слегка усложним задачу:
    Задача 3. В последовательности записаны целые числа. Число X встречается один или два раза, остальные числа — по три раза. Найти число X. Для простоты считаем, что числа неотрицательные.
    Скрытый текст
    Поступим аналогично предыдущей задаче: переведём каждое из чисел в троичную систему: b=b[0]+3*b[1]+32*b[2]+… Для каждого разряда найдём сумму его значений по модулю 3 (обозначим суммы s[0],s[1],s[2],...). Кроме того, посчитаем сами числа.
    Если чисел в последовательности было 3*k+1, то X встретился один раз, и его значение равно s[0]+3*s[1]+32*s[2]+… Если же чисел было 3*k+2, то в наборе s[i] единицы придётся заменить на двойки и наоборот: x[i]=(3-s[i])%3, и X=x[0]+3*x[1]+32*x[2]+…


    А если сделать ещё один шаг?
    Задача 4. В последовательности записаны целые числа. Число X встречается 1,2 или 3 раза, остальные числа — по 4 раза. Найти число X.
    Скрытый текст
    Предыдущий подход здесь уже не сработает: если мы возьмём систему счисления с основанием 4, и найдём поразрядные суммы, то для случаев, когда X встретился один или три раза, всё будет хорошо. Но если X встретился дважды, мы уже не сможем узнать, была ли очередная цифра равна 0 или 2 — значение суммы si для этого разряда в обоих случаях будет равно нулю. Что делать?
    На самом деле, в прошлый раз я вас обманул. Совершенно незачем возиться с троичной системой — достаточно было посчитать сумму битов в каждом двоичном разряде, и если она делилась на 3, то в числе X соответствующий бит равнялся нулю. Если нет — то единице.
    В этой задаче делаем точно так же, но проверяем делимость на 4. Например, эти задачи можно решить так:
            static int FindNotThree(IEnumerable<int> seq) {
                int a=0,b=0;
                foreach(int c in seq) {
                    a^=~b&c;
                    b^=~a&c;
                }
                return a|b;
            }
            static int FindNotFour(IEnumerable<int> seq) {
                int a=0,b=0;
                foreach(int c in seq) {
                    a^=b&c;
                    b^=c;
                }
                return a|b;
            }
    



    Задача 5. В длинной очереди стоят люди. Для каждого из них, кроме последнего, записали его имя и имя того, кто стоит за ним. Полученные записи перемешали и записали в файл. Требуется за один просмотр файла определить имена первого и последнего человека. Известно, что эти имена различны (иначе задача неразрешима), но, в общем, имена могут повторяться. Имя каждого человека состоит из шестнадцати 8-битных символов.
    Скрытый текст
    Будем рассматривать каждое имя, как битовую строчку из 128 элементов. В каждой записи у нас две таких строчки — b[i] и c[i].
    Cначала посмотрим, что получится, если для каждого i мы найдём сумму s[i] разностей b[i]-c[i] для всех записей.
    Поскольку все имена, кроме первого и последнего, встречаются в строчках b и c однаковое число раз, то при суммировании они взаимоуничтожатся, и в сумме останется поразрядная разность первого и последнего имени. Значение s[i], таким образом, может принимать значения -1, 0 или 1.
    Если s[i]=-1, то значение b[i] для первого имени равно 0, а для второго 1. Если s[i]=1, то значения будут равны 1 и 0 соответственно. Но если s[i]=0, то мы можем сказать только, что значения этого бита в первом и последнем имени одинаковы. Как бы нам их найти?
    Предположим, что мы знаем, что для какого-то k у нас s[k] ненулевое. Что будет, если мы найдём XOR значений (b[i]&b[k])^(c[i]&c[k])?
    Для всех имён n, кроме первого и последнего, выражение n[i]&n[k] войдёт в сумму дважды (один раз как b, второй раз, как c) и даст нулевой вклад. Если f — первое имя, а p — последнее, то в сумме останется (f[i]&f[k])^(p[i]&p[k]). Нас интересуют только те биты, для которых f[i]=p[i] (значения остальных мы уже нашли). Поэтому, (f[i]&f[k])^(p[i]&p[k])=f[i]&(f[k]^p[k]), а поскольку s[k]!=0, то f[k]^p[k]=1, и итоговая сумма равна f[i].
    К сожалению, сказать заранее, в каком бите будут различаться имена, мы не можем. Поэтому, на всякий случай, будем считать суммы
    (b[i]&b[k])^(c[i]&c[k]) для всех пар i,k. Всего нам понадобится 128*127/2=8128 однобитных счётчиков и 128 двухбитных (для подсчёта s[i]).
    Например, можно написать обработку так (мы предполагаем, что оба имени в записи передаются в одном байтовом массиве, записанные подряд):
            static byte[] FindDiffNames(IEnumerable<byte[]> seq) {
                const int LName=16;
                byte[,] pairs=new byte[LName*8,LName];
                byte[] res=new byte[2*LName];
    
                foreach(byte[] name in seq) {
                    for(int i=0;i<LName;i++) {
                        res[i+LName]^=(byte)(name[i]&res[i]);
                        res[i]^=(byte)(name[i]^name[i+LName]);
                        res[i+LName]^=(byte)(name[i+LName]&res[i]);
                        for(int k=0;k<LName*8;k++) {
                            byte mask=(byte)(1<<(k&7));
                            if((name[k>>3]&mask)!=0) pairs[k,i]^=name[i];
                            if((name[LName+(k>>3)]&mask)!=0) pairs[k,i]^=name[i+LName];
                        }
                    }
                }
                for(int i=0;i<LName;i++) {
                    int b0=res[i],b1=res[i+LName],s=0;
                    for(int j=0;j<LName*8;j++) s|=pairs[j,i];
                    s&=~b0;
                    res[i]=(byte)((b0&~b1)|s); res[i+LName]=(byte)((b0&b1)|s);
                }
                return res;
            }
    


    С помощью этого приёма можно, также, найти разность множеств, одно из которых получается из другого добавлением двух или даже трёх элементов (или добавлением двух и удалением одного). Если различия более сильные, приходится хранить суммы конъюнкций не только пар, но и троек битов. И XOR там уже недостаточно — приходится считать хотя бы трёхбитные знакопеременные суммы.

    UPD: В обсуждении этой задачи в комментариях SeptiM предложил более простое решение. Рассматриваем имена как 128-битные целые числа (xi,yi), и считаем суммы S1=sum(xi-yi), S2=sum(xi^2-yi^2) (первая сумма должна быть знаковой 129-битной, вторая — знаковой 257-битной. Переполнения игнорируем, работаем по модулю 2^129 и 2^257 соответственно). Понятно, что их значения равны S1=x1-xn, S2=x1^2-xn^2, где x1 — первое имя, xn — последнее. Отсюда легко находим x1=(S1+S2/S1)/2, xn=x1-S1.


    Задача 6. В последовательности записаны целые числа, больше половины из которых равны одному и тому же числу X. За один просмотр последовательности найти это число.
    Скрытый текст
    Заметим, что если мы вычеркнем из последовательности два различных числа, то условие задачи останется верным. Поэтому мы можем вычёркивать пары различных чисел до тех пор, пока все элементы не станут равными одному и тому же числу. Это число и будет X.
    Чтобы реализовать этот метод, заведём ячейку, в которой будет храниться какой-то элемент последовательности, и счётчик — сколько копий этого элемента у нас просмотрено и пока не вычеркнуто.
    Когда мы читаем очередной элемент, у нас есть три варианта:
    — Счётчик равен нулю. Кладём прочитанный элемент в ячейку, увеличиваем счётчик на 1.
    — Элемент равен значению ячейки. Увеличиваем счётчик на 1.
    — Элемент не равен значению ячейки. Уменьшаем счётчик на 1.
    После того, как мы просмотрим всю последовательность, в ячейке окажется искомое число.

    К сожалению, обобщить это решение на случай, когда число X встречается больше, чем в 1/k случаев (k известно), не удаётся. Мы можем так же завести k-1 ячейку со счётчиком, удалять за один раз по k различных элементов, получим в конце k-1 кандидата на роль X, но опознать его нам не удастся — даже значение счётчика у него будет не самым большим. Зато если нам разрешат сделать второй проход, мы можем посчитать, сколько раз каждый из кандидатов встретился в последовательности, и выдать гарантированно самого частого.

    У исходной задачи есть ещё одно решение. Для каждого бита считаем, сколько раз он равнялся 0, а сколько — 1, и выдаём более частое значение. Возможно, его удастся обобщить на случай, когда X встречается больше, чем в 1/3 случаев — посчитаем статистику для каждой пары битов… вдруг поможет?


    Следующие две очень похожие задачи за один проход решить вряд ли получится. Но для них есть интересное решение за log(M) проходов.
    Задача 7. В последовательности записаны целые неотрицательные числа, меньшие M, причём известно, что каждое число встречается не более одного раза. Найти наименьшее число, которое в этой последовательности не встречается.
    Задача 8. В последовательности записано M+1 целое неотрицательное число, все числа меньше M. Найти какое-нибудь число, которое встречается хотя бы дважды.
    Скрытый текст
    Решения практически одинаковы. Делим диапазон 0..M-1 на две или более частей. Для каждой части подсчитываем, сколько чисел в неё попало. В первой задаче оставляем самый ранний поддиапазон, в который попало меньше чисел, чем его длина, во второй — любой из поддиапазонов, в который попало больше чисел, чем его длина. Процесс повторяем, пока не останется диапазон из одного числа. Оно и будет ответом.


    Есть ещё задачка, которая меня давно интересует, но решения которой я не знаю.
    Задача 9. В последовательности записаны числа от 1 до N в каком-то порядке. Каждое число встречается один раз. N заранее известно. Требуется за один просмотр последовательности определить чётность записанной в ней перестановки. Какой минимальный объём памяти для этого требуется?
    Парадокс заключается в том, что в любой заранее выбранный момент нам достаточно помнить 1 бит информации. Но после этого будет необходимо иметь N+1 бит — чтобы запомнить, какие элементы идут в последовательности после этого момента.
    Поделиться публикацией
    Реклама помогает поддерживать и развивать наши сервисы

    Подробнее
    Реклама
    Комментарии 54
    • +2
      Задачи похожи на задачи с codility
      • 0
        Может быть. Я туда заглядывал только пару раз, так что не знаю, что там варится.
      • 0
        Среди задач по программированию часто попадаются такие: дана последовательность однотипных элементов (обычно это числа),
        Обычно на такое я предлагаю рандомное перемешивание, вплоть до достижения.

        Задача 9. В последовательности записаны числа от 1 до N в каком-то порядке. Каждое число встречается один раз. N заранее известно. Требуется за один просмотр последовательности определить чётность записанной в ней перестановки. Какой минимальный объём памяти для этого требуется?
        Помнится, было записывание по одному байту с «дистрибутива», с помощью int21. Но смысл?
        • 0
          Смысла в поиске чётности перестановки нет вообще почти никогда. А когда она нужна, то и памяти хватает. Просто математическая задача — построить конечный автомат с минимальным числом состояний и таким-то набором откликов на заданные входные данные.
        • 0
          Интересно, для первой задачи есть удобоваримые решения, когда изъято более двух чисел из последовательности?
          • +1
            Есть. Можно действовать так же, как в задаче с именами — считать суммы отдельных битов, их попарных конъюнкций, конъюнкций троек битов и т.д. И смотреть на отличие от эталонной последовательности 1..N. Попарных конъюнкций достаточно, чтобы найти 3 изъятых числа, троек — чтобы найти до 7 чисел. Можно ли назвать эти решения удобоваримыми, не знаю. Но практичными их назвать трудно. Хотя, если это задача поиска и исправления ошибок в какой-нибудь базе — то этот подход может пригодиться.
            • 0
              О вашем решении первой задачи. Я только могу предполагать, что в последовательности целые числа. И к тому же они строго больше 0. Тогда возможно как мне кажется и так ускорить решение: эти числа же являются N натурального ряда, тогда остается применить формулу для вычисления суммы N первых членов натурального ряда n(n+1)/2 и вычесть из нее реальную сумму. При таком решении есть одна маленькая польза: нам не нжно подсчитывать их количество и сокращается количество умножений.
              • +2
                1) Явно же сказано про целые числа от 1 до N
                2) N заранее неизвестно, поэтому появляется K
                3) Идея алгоритма совпадает с той, которую привели вы
                Вы как читали вообще?
                • 0
                  Да, вот, что-то про то что N все же заранее неизвестно как-то тупанул.
            • +2
              Да, вполне. Для двух пропавших можно найти сумму всех чисел и сумму их квадратов. Получим два уравнения: x1 + x2 = S1, x1^2 + x2^2 = S2. Осталось решить систему.

              Если обобщать до k пропавших, то может возникнуть проблема с большими порядками для вычислений. Есть альтернатива: ipsit.bu.edu/documents/ieee-it3-web.ps
              • 0
                Хорошая идея. Тогда и с именами можно поступить так же — посчитать для каждого набора сумму и сумму квадратов 128-битных чисел. А система x1 — x2 = S1, x1^2 — x2^2 = S2 решается ещё проще, чем с суммами — даже корни извлекать не нужно.
                • 0
                  Это решение я и подразумевал под «неудобоваримым», потому как в итоге мы приходим к системе с матрицей, которая является минором матрицы Вандермонда. Для случая двух уравнений все решается относительно просто, а вот с подъемом степени начинаются игрища со сборкой нужных полиномиальных коэффициентов, если решать алгебраически.

                  Наверняка можно сочинить алгоритм для сведения этой системы к полиному одной переменной (фактически, ищем точку пересечения гиперповерхностей первого тире катого порядка, где к — количество изъятий), а затем найти для этого полинома корни методом Лобачевского.

                  Поэтому решение с битовыми индексами выглядит приятнее, а главное, легче обобщается.
                  • +3
                    В статье по ссылке чуть проще решение. Пусть p(x) = prod_{i = 1..n} (x — i), а q(x) = prod_{a in A} (x — a), где A — те элементы, которые есть в массиве. Можно заметить, что p(x) / q(x) = t(x) = prod_{i = 1..k} (x — y_i), где y_i как раз пропавшие элементы. Можно посчитать p и q в k + 1 точке над каким-нибудь конечным полем, проинтерполировать полином t(x) и потом его факторизовать.

                    Если подумать, то это вполне элегантное решение.
                    • 0
                      Интересно, что формула p(x) и t(x) очень родственна формуле для определителя полной матрицы Вандермонда. Это неспроста — фактически в статье и приводится хитрый алгоритм по сведению системы к полиному.
                      • 0
                        То есть, мы берём k значений a_j, не принадлежащие множеству допустимых данных на входе (например, для 32-битных чисел это будут числа, большие N=2^32 — это нужно, чтобы не пришлось делить на 0), выбираем простое p>N+k, и считаем произведения (x_m-a_j) и (y_m-a_j) по модулю p — отдельно для каждого j. Ещё проще сказать, что a_j=-j, тогда достаточно считать произведения x_m+j и y_m+j для j=1..k. Потом делим одно на другое… и что? Восстанавливаем полином по Лагранжу и ищем корни какими-нибудь квадратичными вычетами? Когда одно из множеств X является подмножеством Y, это сработает, и нам будет достаточно 65-битной арифметики (чтобы умещалось (N+k-1)^2). Но когда X и Y различаются в нескольких элементах, то придётся восстанавливать рациональную функцию… Кто-нибудь помнит, как это делается?
                        • 0
                          А если подумать… кто нас заставляет работать в конечном поле по простому модулю? Можно рассматривать исходные числа как многочлены над Z2, и работать по модулю неприводимого многочлена log2(N)+2-й степени. Интересно, будет ли это быстрее или дольше, чем с длинной арифметикой. И как потом искать корни многочлена из (Z2[x]/p(x))[y].
                          • 0
                            Методом Лобачевского, можно найти все корни с нужной точностью за десяток-другой итераций.

                            Интересно, не будет ли тогда проще внаглую решить систему из варианта решения со степенями обычным градиентным методом?
                            • +1
                              Непонятно, хватит ли точности. И какой там будет якобиан в окрестности корня (особенно, если пропущенные числа большие и близкие). Будут ли работать численные методы вообще.
                              • 0
                                Если брать применение метода Лобачевского к полиному, он на том и работает, что разносит на каждой итерации корни подальше друг от друга (заменяет полином на такой, у которого корнями — квадраты первоначального).

                                Относительно применимости градиентного метода к этой почти-Вандермондовой матрице — надо оценки выписывать и эксперименты проводить, иначе так среди допущений и останемся. Корень кстати у такой системы один (потому как она около-Вандермондова), значит проблем со сходимостью скорее всего не будет.

                                Меня очень смущает то, что система из задачи со степенями очень похожа на систему из задачи интерполяции (является ее минором по сути), как-то одна задача должна во вторую выливаться с одинаковым итогом — полиномом
                                • 0
                                  Корень будет не один. У неё будет k! корней — все перестановки значений x1,x2,...,xk.
                                  По хорошему, её бы надо перевести в базисные симметрические полиномы. Если для этого есть явные формулы — хорошо. Иначе, при больших k на их вывод потребуется слишком много времени и памяти.
                                  А если значения симметрических полиномов будут известны — останется щёлкнуть пальцами и найти корни одного многочлена k-й степени от одной переменной :) При хорошем раскладе, при вычислении коэффициентов не придётся даже выходить из кольца целых чисел.
                                  • 0
                                    Относительно перестановок — полностью согласен, упустил!

                                    Базисные симметрические полиномы задаются полиномиальными коэффициентами из 0 и 1, то есть нужно поискать возможность из наборов полиномиальных коэффициентов, соответствующих строкам системы «собрать» эти самые базисные. Интуиция мне подсказывает, что это можно сделать, на первых порах — пусть даже лобовым перебором, а потом поискать закономерности и т. п.
                          • 0
                            Искомый полином можно получить, если внимательно побиться головой о систему в методе со степенями — складывая строки или возводя их в степени.
                            • 0
                              Я для себя понял, что мы берём 2k значений. Дальше для каждого a_j получаем дробь вида p(a_j) / q(a_j) = x_j / y_j. Это можно записать как y_j * p(a_j) = q(a_j) * x_j. Дальше имеем 2k таких уравнений c 2k неизвестными. Решаем Гауссом, а потом факторизуем.
                              • 0
                                Действительно. Метод неопределённых коэффициентов обыкновенный. Безо всяких попыток записать результат в виде формул :)
                                • НЛО прилетело и опубликовало эту надпись здесь
                                  • 0
                                    Потому что, чтобы извлечь эту информацию, из этих сумм всё равно придётся строить коэффициенты того самого многочлена. А потом искать его корни. Или вы знаете более простой способ решения этой системы?
                                    • НЛО прилетело и опубликовало эту надпись здесь
                                      • 0
                                        В конечном поле есть другие методы. Если мы знаем, что у какого-то многочлена R над полем Zp нет кратных корней, и все корни принадлежат Zp, то найти корни можно так:
                                        — берём случайное число a из Zp
                                        — считаем многочлен Q=((x-a)(p-1)/2-1) mod R
                                        — находим C=gcd(Q,R).
                                        С вероятностью 1-21-deg( R ) многочлен C будет отличен от 1 и от R. Так что мы разложили R на два множителя: R=C*(R/C). Продолжаем процесс, пока не получим линейные множители.
                                        • +2
                                          А ведь это была всего лишь задача «найти k пропущенных чисел» :D
                                          • НЛО прилетело и опубликовало эту надпись здесь
                                            • 0
                                              Программисты скажут, что им математика не нужна, а нужно больше памяти — и тогда они эту задачу решат в 5 строчек. А если за O(N^2), то вообще в две.
                                            • +1
                                              Собственно, вот код. Примерно 160 строчек. По большому счёту, было совсем не страшно.
                                              Скрытый текст
                                                  class Test {
                                                      static uint P=4294967291;
                                              
                                                      static uint Add(uint a,uint b) {
                                                          return (uint)(((ulong)a+b)%P);
                                                      }
                                                      static uint Sub(uint a,uint b) {
                                                          return (uint)(((ulong)a+P-b)%P);
                                                      }
                                                      static uint Mul(uint a,uint b) {
                                                          return (uint)(((ulong)a*b)%P);
                                                      }
                                                      static uint Inv(uint a) {
                                                          uint b=P,c=1,d=0;
                                                          bool neg=false;
                                                          while(a!=1) {
                                                              uint x=b%a,y=b/a;
                                                              b=a; a=x;
                                                              x=d+c*y; d=c; c=x;
                                                              neg=!neg;
                                                          }
                                                          return neg ? Sub(0,c) : c;
                                                      }
                                              
                                                      static int K;
                                                      static uint[] PowSum;  // [K+1]
                                                      static uint[] Polynom;
                                                      static void AddPowers(uint n,bool add) {
                                                          uint r=1;
                                                          for(int i=0;i<=K;i++) {
                                                              PowSum[i]=add ? Add(PowSum[i],r) : Sub(PowSum[i],r);
                                                              r=Mul(r,n);
                                                          }
                                                      }
                                              
                                                      static void NewtonConversion() {
                                                          Polynom=new uint[K+1];
                                                          Polynom[K]=1;
                                                          for(int s=1;s<=K;s++) {
                                                              uint res=0;
                                                              for(int a=1;a<=s;a++) {
                                                                  if(a%2==0) res=Sub(res,Mul(Polynom[K-s+a],PowSum[a]));
                                                                  else res=Add(res,Mul(Polynom[K-s+a],PowSum[a]));
                                                              }
                                                              Polynom[K-s]=Mul(res,Inv((uint)s));
                                                          }
                                                      }
                                              
                                                      static uint[] MulMod(uint[] pol1,uint[] pol2,uint[] mod) {
                                                          int D=pol1.Length;
                                                          uint[]res=new uint[D];
                                                          for(int i=D-1;;i--) {
                                                              uint a=pol2[i];
                                                              for(int j=0;j<D;j++) res[j]=Add(res[j],Mul(a,pol1[j]));
                                                              if(i==0) break;
                                                              a=res[D-1];
                                                              for(int j=D-1;j>0;j--) res[j]=Sub(res[j-1],Mul(mod[j],a));
                                                              res[0]=Sub(0,Mul(mod[0],a));
                                                          }
                                                          return res;
                                                      }
                                              
                                                      static void CalcPow(uint[] pol,uint pow,uint[] mod) {
                                                          uint maxpow=1u<<31;
                                                          while(maxpow>=pow) maxpow>>=1;
                                                          uint[] res=(uint[])pol.Clone();
                                                          while(maxpow>0){
                                                              res=MulMod(res,res,mod);
                                                              if((pow&maxpow)!=0) res=MulMod(res,pol,mod);
                                                              maxpow>>=1;
                                                          }
                                                          Array.Copy(res,pol,res.Length);
                                                      }
                                              
                                                      static int Deg(uint[] pol) {
                                                          for(int i=pol.Length-1;i>=0;i--) if(pol[i]!=0) return i;
                                                          return -1;
                                                      }
                                              
                                                      static uint[] CalcGCD(uint[] pol1,uint[] pol2) {
                                                          for(;;) {
                                                              int d1=Deg(pol1),d2=Deg(pol2);
                                                              if(d2<0) return pol1;
                                                              while(d1>=d2) {                    
                                                                  uint a=Mul(pol1[d1],Inv(pol2[d2]));
                                                                  if(Mul(a,pol2[d2])!=pol1[d1]) {
                                                                      break;
                                                                  }
                                                                  pol1[d1]=0;
                                                                  for(int i=0;i<d2;i++) pol1[i+d1-d2]=Sub(pol1[i+d1-d2],Mul(a,pol2[i]));
                                                                  d1--;
                                                              }
                                                              uint[] p=pol1; pol1=pol2; pol2=p;
                                                          }
                                                      }
                                              
                                                      static void DivPol(int idx0,int pow,uint[] pol,int deg) {
                                                          uint b=Inv(pol[deg]);
                                                          for(int i=0;i<deg;i++) {
                                                              pol[i]=Mul(pol[i],b);
                                                              Polynom[idx0+pow-deg+i]=Sub(Polynom[idx0+pow-deg+i],pol[i]);
                                                          }
                                                          pol[deg]=1;
                                                          for(int j=pow-1;j>=deg;j--) {
                                                              b=Polynom[idx0+j];
                                                              int dr=idx0+j-deg;
                                                              for(int i=0;i<deg;i++) Polynom[dr+i]=Sub(Polynom[dr+i],Mul(b,pol[i]));
                                                          }
                                                      }
                                              
                                              
                                                      static void Factor(int idx0,int pow,uint shift,List<uint> ans) {
                                                          while(pow>1) {
                                                              uint[] pol=new uint[pow];
                                                              uint[] pol2=new uint[pow+1];
                                                              pol[1]=1; pol[0]=shift;
                                                              for(int i=0;i<pow;i++) pol2[i]=Polynom[i+idx0];
                                                              pol2[pow]=1;
                                                              CalcPow(pol,(P-1)/2,pol2);
                                                              if(Deg(pol)<0){ shift++; continue; }
                                                              pol=CalcGCD(pol,pol2);
                                                              int deg=Deg(pol);
                                                              if(deg==0) { shift++; continue; }
                                                              DivPol(idx0,pow,pol,deg);
                                                              for(int i=0;i<deg;i++) Polynom[i+idx0]=pol[i];
                                                              shift++;
                                                              Factor(idx0+deg,pow-deg,shift,ans);
                                                              pow=deg;
                                                          }
                                                          ans.Add(Polynom[idx0]);
                                                      }
                                              
                                                      static List<uint> Missing(IEnumerable<uint> seq,int k) {
                                                          K=k;
                                                          PowSum=new uint[K+1];
                                                          uint n=1;
                                                          foreach(uint a in seq) {
                                                              AddPowers(n++,true);
                                                              AddPowers(a,false);
                                                          }
                                                          for(int i=0;i<K;i++) AddPowers(n++,true);
                                                          NewtonConversion();
                                                          List<uint> res=new List<uint>();
                                                          Factor(0,K,0,res);
                                                          return res;
                                                      }
                                                      static void Main(string[] args) {
                                                          uint[] test3_1= { 1,5,7,2,6,8,9 };
                                              
                                                          List<uint> res=Missing(test3_1,3);
                                                          foreach(uint a in res) Console.Write("{0} ",a);
                                                          Console.WriteLine();
                                                      }
                                                  }
                                              

                              • 0
                                А нет ли идей, как за один проход найти имя второго человека в очереди? У меня пока вообще ничего не выходит.
                                • 0
                                  Если я правильно понял, у нас есть орграф, содержащий Эйлеров путь. В задаче мы ищем начало и конец. На самом деле можно решение упростить, если все вершины рассматривать как числа и по всем ребрам проссумировать значения u — v и u^2 — v^2. Вроде красивая система будет.

                                  Со второй вершиной пути не очень понятно. Если стартовая вершина лежит на нескольких циклах, то вторую вершину можно определить по разному. Если она одна, сходу ничего в голову не лезет. Подумаю.
                                  • 0
                                    Для простоты можно считать, что имена не повторяются. Получается, что нам сначала задали функцию next(x) в большом числе точек, а потом спросили next(x0). С дополнительным условием, что множество всех заданных значений next(x) отличается от множества значений x только в одной точке. Можно ли использовать это условие, чтобы не хранить все пары?
                                    • +1
                                      Может и не все, но многие. Пример в комментарии ниже показывает, что памяти потребуется много: Omega(n log n). Я может очень кратко там написал, могу здесь расписать.

                                      Пусть у нас есть алгоритм, который использует t бит памяти.

                                      Мы строим граф на основе циклической перестановки (такой, что p(x) != x для всех x). Граф двудольный, состоит из долей A и B. В каждой доле n вершин. Сначала проводим ребра из вершины a_i в вершину b_{p_i} для каждого i. Скормим эти ребра алгоритму и посмотрим на его память.

                                      Я утверждаю, что из памяти можно извлечь всю перестановку. Если это так, то для разных перестановок состояния памяти должны быть разные. Значит, должно быть, что 2^t >= (n — 1)! или t = Omega(n log n).

                                      Почему можно извлечь перестановку? Зафиксируем некоторое значение j и проведем ребра из b_i в a_i для вcех i != j. Скормим их алгоритму. Мы получили Эйлеров граф, в котором вторая вершина будет как раз b_{p_j}. Алгоритм её должен выдать. Понятно, что такую процедуру можно запустить для всякого j и восстановить перестановку.

                                      P.S. Примерно такой же конструкцией можно показать, что и вероятностные алгоритмы тоже не помогут.
                                      • 0
                                        Да, похоже на правду. Только там (n/2)! (если я правильно понял конструкцию): ведь для задания перестановки нам нужен двойной набор вершин.
                                        • 0
                                          Да, если считать, что в графе n вершин.

                                          Кстати, вот девятая задача действительно какая-то головоломная. Я знаю, как показывается нижняя оценка на подсчет числа инверсий (тоже Omega(n)). Но вот именно четность не получается пробить.
                                          • 0
                                            Про девятую у меня бродят мысли такого плана:
                                            возьмём два момента: после анализа n/3 чисел и после анализа 2*n/3. Предположим, что в каждый из этих моментов у нас есть только k бит информации. И докажем, что мы проиграли :)
                                            • НЛО прилетело и опубликовало эту надпись здесь
                                              • 0
                                                В том-то и дело, что нам не обязательно вычислять чётность элемента среди предыдущих. В любой момент мы можем обнулить всю информацию, кроме накопленной чётности перестановки (это 1 бит), и начать считать множество элементов и чётность перестановки с этого момента. В конце посчитаем чётность множества последних элементов относительно первых — и скорректируем ответ. Но это можно проделать только один раз.
                                                Вопрос — можно ли, сохраняя более одного бита на промежуточных этапах, тем не менее, уменьшить объём нужной информации?
                                                Для n=3 существует конечный автомат с тремя состояниями (т.е. 1.6 бита), который может вычислить чётность всех 6 перестановок.
                                  • 0
                                    Для определения второго человека детерминированный алгоритм потребует Omega(n log n) памяти, где n — число вершин. Можно взять двудольный граф и зашить в него циклическую перестановку. Дальше можно расположить ребра так, что после их обработки из памяти алгоритма можно извлечь всю перестановку.

                                    Ребра, которые сначала алгоритм обработает чтобы получить интересную память, будут иметь вид a_i -> b_{p_i}. Чтобы узнать, куда ползет элемент j, нужно добавить в граф ребра b_i -> a_i для всех i != j.
                                • 0
                                  Решение с битовыми индексами требует слишком много памяти — N^log(k) (точнее, C(N,log(k)), но это тоже много).
                            • +1
                              В условиях еще, как правило, указываются лимиты на память и время выполнения, иногда это ключевые критерии для выбора того или иного метода решения. Встречалась, помню, мне однажды интересная задачка примерно такого плана: даны координаты точек: x1, y1, x2, y2,… вплоть до тысячи таких координат, нужно было определить, сколько «троек» таких точек лежат на одной прямой, на выполнение, вроде 1 секунда была, т.е. проход тремя циклами с проверкой просто не проходил. Пришлось точки разбивать на пары, находить их коэффициенты a и b, сортировать по этим коэффициентам и потом уже считать тройки. Это я к тому, что на чемпионате важно «влезть» во все лимиты и пройти все тесты, а не искать самое элегантное решение (хотя часто эти вещи взаимосвязаны). Я бегло взглянул на задачи в посте и первое, что пришло в голову — если бы лимиты позволяли, я бы просто создавал массив с ключами в виде значений и значениями в виде инкрементов.
                              • +2
                                Здесь с самого начала оговорено, что последовательность может не уместиться в память. Так что можно считать, что лимит — 64 килобайта — как в старые добрые времена :D
                                А с точками можно обойтись и без полной сортировки пар. Достаточно перебрать все точки, для каждой из них отсортировать направления на остальные точки, и потом проверить, есть ли одинаковые. Время то же — N^2*log(N), а памяти нужно гораздо меньше. Да и код получится несколько проще.
                              • НЛО прилетело и опубликовало эту надпись здесь
                                • НЛО прилетело и опубликовало эту надпись здесь
                                  • 0
                                    Да, нам нужна битовая маска уже встретившихся элементов плюс 1 бит для подсчёта результата. Каждый раз, когда приходит новый элемент, мы считаем, сколько элементов, больших его, уже встретилось, и, в зависимости от чётности, меняем или не меняем результат. Похоже, что при хорошей организации битового массива можно реализовать обработку одного элемента за log(N) операций: в ячейке с индексом k=p*2^m будем хранить чётность количества обработанных элементов в диапазоне k..k+2^m-1.
                                    Но такой подход требует N+1 бита (можно обойтись N, элемент с индексом 0 нам не нужен). Не думаю, что это минимум. Я бы предположил, что хватит O(sqrt(N)), но это просто гадание ни на чём.
                                    • НЛО прилетело и опубликовало эту надпись здесь
                                • 0
                                  Что-то я не понял почему так сложно решается задача №5. Почему бы не использовать подход из второй задачи (XOR)? Все имена кроме первого встретятся по 2 раза, а последнего можно вычислить просто отслеживая человека, у которого нет никого за ним.
                                  • +1
                                    Для последнего человека записи в последовательности нет, по условию. Так что дважды встретятся все имена, кроме первого и последнего. Фактически, у нас есть два множества с одинаковым числом элементов, которые различаются ровно одним элементом — и надо найти, чему этот элемент равен в каждом из множеств.
                                  • 0
                                    По последней — за один проход, но за дофига памяти получается примерно так: Не читая вход, генерим все перестановки и раскладываем их четности по алфавитному дереву. Потом читая вход, проходим по дереву, получаем ответ.
                                    • 0
                                      Спасибо, хорошая подборка

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