Pull to refresh
29
0
Виталий @RussianDragon

Пользователь

Send message
Например, для чисел вполне очевидно, что 1 || 23 != (1*10+23).

Да. Просто так делать нельзя. Сама идея, что число любое число состоит из конкатенированных цифр. Т.е. 23 (например в десятичной системе) это 2‖3. Т.е. в описанном вами случае будет 1‖2‖3. В противном случае действительно ничего не сходится. Т.к. операция применяется не правильно.
257 системе счисления — будет 256 чисел.
В целом нужно просто понять какие системы нам нужны и уже из это исходить.
В целом там не получается каких-то безумных размерностей в данных
Как я уже писал в статье. Все пояснения решения через конкатенацию установляются на уровне – «смотрите, мы приписали цифру 7 справа и у нас получился ответ». Ну или пишется, что так делать нельзя.
«Почему нельзя» — никто не пишет. То я попытался рассмотреть точку зрения противников такой приписки. Мне показалось, что очевидным ответом будет — такая операция при переводе чисел в другую систему счисления ломает формулу, а такого быть не должно. И тут уже не идет речь о «красоте» формулы, сам факт – результаты подсчетов должны сохраняться. Ломается всё, по простой причине, т.к. изначально понятие «конкатенации» означало приписывание числа справа.
Вот дальше и начались мои размышления, как нам описать эту операцию т.к. что бы это еще работало. Самым простым способом показать, что расчеты не ломаются – это перевести их в другую систему счисления.
С дробями не получилось пока.
Но получилось сделать прикольную систему перевода между системами счисления.
habr.com/ru/post/566052
Прямой ссылки на «конкурс» у меня нет.
Но в заметках о проблеме числа 10958 часто встречается фраза — Массачусетский технологический институт готов выплатить 5000$!
Вообще есть информация, что за нахождение ответа в «привычном смысле» дают 5000$.
То можете попробовать)
Читал по большей части. Может это и послужило триггером для написание этой статьи. В приведенной статье, писалось, что «внешняя конкатенация» вообще является ошибочной, что собственно меня смутило/ заинтересовало. Ибо там говорится, что так вообще делать нельзя. Мне же стало интересно, переложить конкатенацию на алгебраически рельсы ибо в википедии о таком подходе вообще речи не идет, только о том, что конкатенация троки объединяет складывает.
П.с.
Просто я сталкивался эвристикой, при которой наиболее простом случае нужно было до множить на 100. Что мне крайне не нравилось из-за костыльности решения, но ничего иного в голову не приходило. И как-то видео с этим числом и мои проблемы с эвристикой на ложилось друг на друга. Сейчас в моей голове сформировался какой-то математический смысл такой эвристики, да и на задачку решение ложиться, а не просто абстрактные рассуждения)
Не совсем так. это скорее способ переключить внимание. От известных A, B, C, D, E, F в иной формат. В целом все числиную систему можно записть либыми символами, например так: 아, 애, 야, 얘, 어, 에, 여, 예, 오, 와, 왜, 외, 요, 우, 워, 웨…
Ладно, признаю. Натянули они Сову на глобус в условиях задачи. )
Да и фиг с ними.)
А зачем? Если мы так имеем разбросанные id-шники, то зачем нам при вставке нового пользователя брать минимальный? Более того, взятие минимального id — это в примере, а не в условии. В условии — взять id которого нет в базе.
— Говорю — авторы сами намудрили решением простой задачи, а потом попросили пользователей тыкнуть пальцем в небо и написать решение которое будет похоже на их мудрёное, которое не отражает суть изначально поставленной задачи.
gektor2510, я тут понял, что Вам вообще MEX не уперся по своей сути согласно постановки задачи.
Еще раз, Вы хотите:
1) Зарегистрировать нового пользователя,
2) Защифровать все текущие данные с помощью нового ключа x

Тогда вот вам код, который будет выполнять вашу задачу.

class Item
    {
        public uint Id { get; set; }
        public Item Next { get; set; }
    }

    class Program
    {
        static Item First { get; set; }
        static Item Last { get; set; }
        static uint CountUsers { get; set; } = 0;
        static uint AcumHash { get; set; } = 0;
        static void Main(string[] args)
        {
            while (true)
            {
                Console.WriteLine("Выбирите действие");
                Console.WriteLine("1 - Добавить новго пользователя");
                Console.WriteLine("2 - Зашифровать данные");
                Console.WriteLine("3 - выйти");
                string comand = Console.ReadLine();
                switch (comand)
                {
                    case "1":
                        AddUser();
                        break;
                    case "2":
                        while (true)
                        {
                            try
                            {
                                Console.WriteLine("Введите ключ (неотрицательное число)");
                                uint key = uint.Parse(Console.ReadLine());
                                HashingUsers(key);
                                break;
                            }
                            catch (Exception)
                            {
                               Console.WriteLine("Ошибка ввода");
                            }
                        }
                        break;
                    case "3":
                        return;
                    default:
                        Console.WriteLine("Ошибка ввода");
                        break;
                }
                PrintUsers();
            }
        }

        private static void AddUser()
        {
            var newItem = new Item()
            {
                Id = (CountUsers ^ AcumHash)
            };
            CountUsers++;
            if (First == null)
            {
                Last = First = newItem;
                return;
            }
            Last = Last.Next = newItem;
        }

        private static void HashingUsers(uint hash)
        {
            AcumHash ^= hash;
            var link = First;
            while (link != null)
            {
                link.Id ^= hash;
                link = link.Next;
            }
        }

        private static void PrintUsers()
        {
            var link = First;
            while (link != null)
            {
                Console.Write($"{link.Id}, ");
                link = link.Next;
            }
            Console.WriteLine();
        }
    }


Мы вставляем записи с 0 в односвязный список O(1).
Мы производим шифрование данных O(n)
Задача решена с минимум памяти (Без оптимизации на двоичном уровне.)
Искать MEX вообще не нужно, т.к. благодаря тому, что мы храним аккумулированный хеш, каждая новая вставка будет уже с учетом того, что подобного индекса точно нет в базе (а именно этого вы и пытаетесь добиться). Выйти за пределы uint мы тоже не можем, т.к. операции битовые.

Всё — задача решена. И зачем вы столько времени посветили описанию MEX, если вам нужно просто вставить значение в базу с уникальным ключом?

lair, wataru, MichaelBorisov или хотите сказать, что я опять неправильно понял задачу?
так массив не сортирован. Тогда, сначала, его нужно отсортировать… что бы это работало. Кстати, сверху описан подобный алгоритм поиска именно на несортированном массиве.
Признаю «прикольность» идеи.
Но есть нюанс, что мы не знаем до какой степени авторы хотят, чтобы участники оптимизированы своё решение. Ибо мы эти задачи решаем в «свободное время», да и в целом не всегда такие извращения нужны. Но идея класс, это я признаю.)
Ну так надо оценить, какая последовательность как будет влиять.

А то знаете ли, (некоторые) алгоритмы сортировки тоже зависят от того, какие данные на входе, но это не мешает их анализировать.

Что-то я уже сбился о чем спор…
Я говорю, в рамках того, что через три месяца авторы дали чуть больше данных об условиях задачи — это не означает, что изначально задача сформулирована «понятным языком».
Собственно Вы сами говорите, что разные алгоритмы могут совершенно по разному работать в зависимости от условий. И тут я полностью согласен. Поэтому нужно описать условия в которых они будут проверяться.

А не говорить потом, что мы не в таких условия проверяли… И я не против сделать иное решение, если на то пошло. Я не доказываю, что мое решение — идеальное для всех случаев жизни. Более того я сам прекрасно понимаю, где и как его оптимизировать в зависимости от условий в которых оно будет.
Там, где условие задачи неполное — надо его самостоятельно дополнять. Что мы знаем из условия? Что «Озон» хочет реализовать это решение для базы своих пользователей. Много ли пользователей у «Озона»? Наверное много, это большая фирма. Настолько ли много, что вся база не помещается в ОЗУ? Это вряд ли, так как такие задачи редко дают в качестве тестовых. В тестовых заданиях обычно идёт упор на академические знания.

Там есть ограничение 256 мегабайт. т.е. 268 435 456 — байт… В int 4 байта, т.е. мы получаем число 67 108 864 пользователей забивают всю память.
67 108 864 — Это много или мало? И это я не учитываю еще «накладные расходы» C#…

А дальше мне начинают утверждать, что из задачи «предельно ясно», что нам нужна «древовидная структура» которая хранит «сколько там» еще ссылок… Ну допустим у каждого элемента по два предка. Т.е. так как минимум нужно хранить сам объект и две ссылки — 67 108 864 / 3. Ой уже 22 369 621… А нам еще нужно выполнять операции на этой структуре данных, да еще и за две секунды… Причем мы не знаем, порядок и частоту операций. Какая операция чаще проходит, какая нет. Может нам стоит использовать какой промежуточный кеш? Или вы конкретную хотите увидеть реализацию, тогда нужно говорить — сделайте «как мы хотим», но как хотим — не скажем. Т.е. от авторов решений просят тыкнуть пальцем в небо — может и угадают, что хотят авторы задачи.

А говорить — «наиболее оригинальное» решение — а кто оценивает оригинальность и по каким критериям? Быстродейственноть, количество строк кода, знание нетривиальных конструкций языка?

Где тут хоть какая-то ясность об условиях функционирования и оценки?
У вас может получиться, что операции идут подряд: вставка, шифрование, вставка, шифрование, и так далее.

Вот непонятно как они идут. Задача сформулирована криво и очень размыто. Что чаще происходит — «шифрование» или «вставка». Или мы шифруем после каждой вставки. Или только вставки 1 000 000 записей решили «шифрануть».
И от это всего будет зависит и структура данных и способ поиска. А говорить — «наиболее оригинальное» решение — а кто оценивает оригинальность и по каким критериям? Быстродейственноть, количество строк кода, знание нетривиальных конструкций языка?
Без нормально ТЗ — результат ХЗ.

При этом нет даже банальной возможности спросить или хоть каких-то автоматических тестов — которые сказали бы «что-то не так».

И утверждать, что спустя три месяца после окончания конкурса чуть более подробную формулировку — это странно.
В тексте задачи в основном описывалась, что такое MEX, на это делался огромный уклон. Т.е. фактически самое главное — быстро находить MEX… А задача «шифрования» и «вставки» просто второстепенные, что бы проверить как эффективно работает MEX «без историчности».
Да, признаю. Сейчас это алгоритм изменился в угоду быстродейственности и объему памяти в рамках задачи MEX. Изначально я находит максимально число в массиве и сам boolean-массив был длинной равный максимальному числу из множества. И мы как раз получали возможность узнать пустые значения на всем диапазоне изначального множества.
В процессе споров в комментариях я оптимизировал выборку первого элемента, сделал массив длинной с изначально множество, а значения больше это длинны игнорировал. Чем по факту “сломал” его переиспользования для поиска “второго” пустого значения. Тут я признаю, что поддался на уговоры.
Так что в целом справедливы оба решения. Если нам нужно выбрать только одно число mex из случайного множества, то текущий код в статье оптимальный. Если мы хотим переиспользовать полученный boolean-массив, то нужно вернуть вариант, где изначально ищется max на исходном множестве.

И, кстати, к разговору об O, мне здесь упорно доказали, что в данном случае операция поиска MAX, просеиванье и поиска по просеянным данным – это O(n). Что хоть и правильно с точки зрения теории, но мне в корне не нравится для оценки реальной бытродейственности.
На несортированном множестве мы ищем элемент меньше k.
Что за k? И каково будет минимальное отсутствующее число?

Information

Rating
Does not participate
Location
Тула, Тульская обл., Россия
Date of birth
Registered
Activity