Comments 54
Может быть. Я туда заглядывал только пару раз, так что не знаю, что там варится.
Среди задач по программированию часто попадаются такие: дана последовательность однотипных элементов (обычно это числа),
Обычно на такое я предлагаю рандомное перемешивание, вплоть до достижения.

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

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

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

Поэтому решение с битовыми индексами выглядит приятнее, а главное, легче обобщается.
В статье по ссылке чуть проще решение. Пусть 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) и потом его факторизовать.

Если подумать, то это вполне элегантное решение.
Интересно, что формула p(x) и t(x) очень родственна формуле для определителя полной матрицы Вандермонда. Это неспроста — фактически в статье и приводится хитрый алгоритм по сведению системы к полиному.
То есть, мы берём 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 различаются в нескольких элементах, то придётся восстанавливать рациональную функцию… Кто-нибудь помнит, как это делается?
А если подумать… кто нас заставляет работать в конечном поле по простому модулю? Можно рассматривать исходные числа как многочлены над Z2, и работать по модулю неприводимого многочлена log2(N)+2-й степени. Интересно, будет ли это быстрее или дольше, чем с длинной арифметикой. И как потом искать корни многочлена из (Z2[x]/p(x))[y].
Методом Лобачевского, можно найти все корни с нужной точностью за десяток-другой итераций.

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

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

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

Базисные симметрические полиномы задаются полиномиальными коэффициентами из 0 и 1, то есть нужно поискать возможность из наборов полиномиальных коэффициентов, соответствующих строкам системы «собрать» эти самые базисные. Интуиция мне подсказывает, что это можно сделать, на первых порах — пусть даже лобовым перебором, а потом поискать закономерности и т. п.
Искомый полином можно получить, если внимательно побиться головой о систему в методе со степенями — складывая строки или возводя их в степени.
Я для себя понял, что мы берём 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 неизвестными. Решаем Гауссом, а потом факторизуем.
Действительно. Метод неопределённых коэффициентов обыкновенный. Безо всяких попыток записать результат в виде формул :)
UFO landed and left these words here
Потому что, чтобы извлечь эту информацию, из этих сумм всё равно придётся строить коэффициенты того самого многочлена. А потом искать его корни. Или вы знаете более простой способ решения этой системы?
UFO landed and left these words here
В конечном поле есть другие методы. Если мы знаем, что у какого-то многочлена 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). Продолжаем процесс, пока не получим линейные множители.
А ведь это была всего лишь задача «найти k пропущенных чисел» :D
UFO landed and left these words here
Программисты скажут, что им математика не нужна, а нужно больше памяти — и тогда они эту задачу решат в 5 строчек. А если за O(N^2), то вообще в две.
Собственно, вот код. Примерно 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();
        }
    }

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

Со второй вершиной пути не очень понятно. Если стартовая вершина лежит на нескольких циклах, то вторую вершину можно определить по разному. Если она одна, сходу ничего в голову не лезет. Подумаю.
Для простоты можно считать, что имена не повторяются. Получается, что нам сначала задали функцию next(x) в большом числе точек, а потом спросили next(x0). С дополнительным условием, что множество всех заданных значений next(x) отличается от множества значений x только в одной точке. Можно ли использовать это условие, чтобы не хранить все пары?
Может и не все, но многие. Пример в комментарии ниже показывает, что памяти потребуется много: 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. Примерно такой же конструкцией можно показать, что и вероятностные алгоритмы тоже не помогут.
Да, похоже на правду. Только там (n/2)! (если я правильно понял конструкцию): ведь для задания перестановки нам нужен двойной набор вершин.
Да, если считать, что в графе n вершин.

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

Ребра, которые сначала алгоритм обработает чтобы получить интересную память, будут иметь вид a_i -> b_{p_i}. Чтобы узнать, куда ползет элемент j, нужно добавить в граф ребра b_i -> a_i для всех i != j.
Решение с битовыми индексами требует слишком много памяти — N^log(k) (точнее, C(N,log(k)), но это тоже много).
В условиях еще, как правило, указываются лимиты на память и время выполнения, иногда это ключевые критерии для выбора того или иного метода решения. Встречалась, помню, мне однажды интересная задачка примерно такого плана: даны координаты точек: x1, y1, x2, y2,… вплоть до тысячи таких координат, нужно было определить, сколько «троек» таких точек лежат на одной прямой, на выполнение, вроде 1 секунда была, т.е. проход тремя циклами с проверкой просто не проходил. Пришлось точки разбивать на пары, находить их коэффициенты a и b, сортировать по этим коэффициентам и потом уже считать тройки. Это я к тому, что на чемпионате важно «влезть» во все лимиты и пройти все тесты, а не искать самое элегантное решение (хотя часто эти вещи взаимосвязаны). Я бегло взглянул на задачи в посте и первое, что пришло в голову — если бы лимиты позволяли, я бы просто создавал массив с ключами в виде значений и значениями в виде инкрементов.
Здесь с самого начала оговорено, что последовательность может не уместиться в память. Так что можно считать, что лимит — 64 килобайта — как в старые добрые времена :D
А с точками можно обойтись и без полной сортировки пар. Достаточно перебрать все точки, для каждой из них отсортировать направления на остальные точки, и потом проверить, есть ли одинаковые. Время то же — N^2*log(N), а памяти нужно гораздо меньше. Да и код получится несколько проще.
UFO landed and left these words here
UFO landed and left these words here
Да, нам нужна битовая маска уже встретившихся элементов плюс 1 бит для подсчёта результата. Каждый раз, когда приходит новый элемент, мы считаем, сколько элементов, больших его, уже встретилось, и, в зависимости от чётности, меняем или не меняем результат. Похоже, что при хорошей организации битового массива можно реализовать обработку одного элемента за log(N) операций: в ячейке с индексом k=p*2^m будем хранить чётность количества обработанных элементов в диапазоне k..k+2^m-1.
Но такой подход требует N+1 бита (можно обойтись N, элемент с индексом 0 нам не нужен). Не думаю, что это минимум. Я бы предположил, что хватит O(sqrt(N)), но это просто гадание ни на чём.
UFO landed and left these words here
Что-то я не понял почему так сложно решается задача №5. Почему бы не использовать подход из второй задачи (XOR)? Все имена кроме первого встретятся по 2 раза, а последнего можно вычислить просто отслеживая человека, у которого нет никого за ним.
Для последнего человека записи в последовательности нет, по условию. Так что дважды встретятся все имена, кроме первого и последнего. Фактически, у нас есть два множества с одинаковым числом элементов, которые различаются ровно одним элементом — и надо найти, чему этот элемент равен в каждом из множеств.
По последней — за один проход, но за дофига памяти получается примерно так: Не читая вход, генерим все перестановки и раскладываем их четности по алфавитному дереву. Потом читая вход, проходим по дереву, получаем ответ.
Only those users with full accounts are able to leave comments. Log in, please.