Почему при сериализации uint128 сначала сериализуют hi, потом lo, а не наоборот?

даешь ссылку - а там только про биты.

По ссылке:

Поэтому порядок байтов от старшего к младшему часто называют «сетевым порядком байтов»

Какое будет время работы алгоритма?

Bavashi,

Выше по ветке комментариев вижу условие "Отрезок должен пересекать обе оси". Условие на пересекающиеся отрезки, не вижу.

Какое будет время работы алгоритма?

Bavashi,

Исходя из такой реализации это может быть и два метода или два прохода, что не будет являться линейной сложностью.

Вы это серъезно? Вы либо что-то непоняли, либо совсем не понимаете сложности алгоритмов. Делаете ли вы 2, 3 или 1 проход по списку - сложность все-равно линейная. Можно разбить цикл на 2, иногда - объединить 2 последовательных цикла. Один фиг - сложность будет линейная. Только реализация с несколькими циклами будет немного медленее, потому что проверки конца цикла и инкриминирование счетчика будет происходить в 2 раза больше. Но это замедление на константное количество процентов, не зависящее от n. По умному говоря, у решений будут разные константы. Хоть и различающиеся на несколько процентов.

Какое будет время работы алгоритма?

Bavashi, Ну блиин, даже такую тривиальщину расписывать?!

int CountSegments(const vector<int> &x, const vector<int> &y) {
  int counters[2][2] = {{0,0}, {0,0}};
  for (size_t i = 0; i < x.size(); ++i) {
    if (x[i] == 0 || y[i] == 0) continue;
    size_t xs = x[i] > 0 ? 1 : 0;
    size_t ys = y[i] > 0 ? 1 : 0;
    ++counters[xs][ys];
  }
  return coutners[0][0]*counters[1][1] + counters[0][1]*counters[1][0];
}

Почему при сериализации uint128 сначала сериализуют hi, потом lo, а не наоборот?

Ничего себе предъявы! Да еще и так грубо.
Порядок байт, бит - без разницы. Еще раз повторю свой ответ - нет особо никаких причин именно такого порядка, кроме как - автор библиотеки сделал так, и все. Мог куски в другом порядке записать. Мог разбить на 16 байт и записать их в прямом или обратном порядке. Мог биты записать.

Какое будет время работы алгоритма?

Bavashi, 12LiCaNtRoP12, раз уж меня призвали, то отвечу. Согласно условию "ни один конец не лежит на оси, отрезок пересекает обе оси" - однозначно следует что все 4 координаты у искомого отрезка ненулевые. Раз он пересекает ось x - то знаки у y-координат разные. Так же по оси y. В итоге получаем, что надо подсчитать пары точек, у которых знаки x и y разные. Это делается за линейную сложность просто подсчитав 4 числа - сколько точек в каждом из квадрантов (строго внутри, не считая осей). После надо сложить произведения чисел для противостоящих квадрантов.

Как переставить элементы массива из конца в начало?

Зачем делать за квадрат на ровном месте?

Какое будет время работы алгоритма?

Можно точно подсчитать количество итераций. Когда i=1 - их будет N-1. i=2 - N-2, i=3 - N-3, и так далее до i=N-1 - 1 итерация, i=N - 0 итераций.

Сумма всего этого добра (n-1)+(n-2)+...+2+1, что есть арифметическая прогрессия. Школьная формула дает n(n-1)/2. При n=1000 это даст 499500 итераций.

> Там, ведь, получается, что цикл внутри цикла вызывается на 1 раз меньше каждый раз, когда происходит первый цикл.

Ну, ровно на N итераций меньше. Если до этого была сумма O(N^2), то таковой и останется.

Почему я получаю неверный ответ?

dalbio, еще раз, прочитайте мой ответ целиком, пожалуйста. Если в старшем разряде четное количество единиц в массиве, то в этом разряде результаты двух игроков различаться НЕ МОГУТ. Вообще, никак! Вы хоть все числа в массиве одному отдайте, хоть только одно, хоть левую половину, хоть каждое четное. Математически в этом разряде числа у двух игроков будут равны.

Ну как пример, если у вас таких 2 числа имеют старший разряд, то или оба пойдут к первому игроку и результат xor будет 0 и там и там, или по одному числу каждому игроку и результат xor будет 1 и там и там, или оба числа отойдут второму игроку, что также даст нули везде.

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

Почему я получаю неверный ответ?

dalbio, Я вам расписал правильное, логически обоснованное решение. Оно вообще не такое, как ваше и ему противоречит.
Старший ненулевой разряд может вообще значения не имеет, если там четное количество единиц. Я могу вам составить тест, когда будет выгодно брать 5 вместо 6, или 6 вместо 5 - все зависит от остальных чисел в массиве.

Почему я получаю неверный ответ?

dalbio, Опишите ваше решение. Без этого сложно найти ошибку в коде.

Как выбрать начальное число (задача по бинарному поиску)?

Тут мало выбирать только первое число и гнать обычный бинарный поиск. Важное ограничение - вы не можете использовать один и тот же цвет дважды. Есть еще спецэффект, что случаи c=n-1 и с=n можно разделить только перекрасившисть с 1 на n или наоборот. Т.е. вы не имеете права краситься в 1 или n-1, только если не знаете точно, что C меньше n или что С одно из двух крайних значений.

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

Как обойти граф не зацикливаясь на связи одного узла с другим?

> А зачем у электростанций? Электростанции не присоединяются друг к другу.

Дом может быть подключен ко многим электростанциям. Какие-то из них могут быть в последствии выключены. Счетчик активных электростанций в компоненте связности позволяет быстро определять, есть ли в этой компоненте электричество или нет.

> овсем не понятен этот момент. Какого именно множества должен быть массив ссылок, предположительно массив Домов?

У вас граф из домов и электростанций. Заведите массив, в котором ключем может быть id дома или id электростанцыы. Фактически - для всех вершин в графе.

Далее, почитайте ссылку в ответе на DSU в вики. Там заводится массив для всех вершин в графе и хранит ссылку на предстваителя множества или на себя, если эта вершина предствляет свое множество. Это массив root. Можно делать это полем в классе вершины (но электростанции и дома должны описыватся одним и тем же классом). Для счетчиков заведите второй массив с теми же ключами, ну или, опять же, поле в классе вершин. Хранится это все в классе мира.

> Имеется ввиду присоединение дома к дому? Надо объединить два массива электростанций подключенных к этим домам?

Прочтите статью в вики про DSU! Все должно стать понятно. Там для каждой вершины (дом, электростанция) хранится ссылка на представителя множества (или ссылка на себя). Чтобы объеденить 2 множества вы находите их представителей, или корни множеств (рекурсивно пройдясь по ссылкам до цикла). Потом для одного корня сделайте ссылку на второй корень.

Фактически это то же самое, как если бы в графе каждая компонента связности была раскрашенна в свой цвет, и при добавлении ребра (связи дом-дом или дом-электростанция) вы бы перекрашивали одну из объедененных компонет в цвет другой. Но DSU делает это сильно быстрее чем проход по всему массиву и заменение цвета1 на цвет2.

> Имеется ввиду присоединение дома к дому? Надо объединить два массива электростанций подключенных к этим домам?

Вы не сделали самого главного - вы не реализовали DSU.

Советуб сделать так:
- в классе дома храните ссылку на HouseId представителя (изначально равно houseid самого дома).

- напишите рекурсивную функцию типа:

GetRoot(id) {
  h = households.get(householdID)
  if (h.root != id)
    h = GetRoot(h.root);
  h.root = h.id; // эвристика сжатия путей
  return h
}

Она по id дома выдает какой-то дом связанный с этим домом. При этом для всех домов в одной компоненте связности она будет выдвавть один и тот же дом (предствитель множества).

- Для всех станций храните список домов, с которыми они напрямую связанны.

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

- при соединении двух домов найдите из корни функцией GetRoot.
Если корни - один и тот же дом, то можно ничего не делать. Вы соединили уже связанные дома. Если они разные, то сделайте h1.root = h2; h2.counter += h1.counter. Опять же, важно, что тут вы не сами соединяемые дома меняете, а то, что GetRoot вернуло.

- при запросе на статус дома - найдите корень через GetRoot и посмотрите у него counter.

- при изменении статуса электростанции пройдитесь по всем связанным с ней напрямую домам (вы их в списке должны хранить уже), найдите представителя через GetRoot, и у него инкриментируйте/декрементируйте счетчик.

Как обойти граф не зацикливаясь на связи одного узла с другим?

glem1337, Ну тогда или медленно с обходом в глубину/ширину на каждом запросе или с DSU делайте, как я описал.

Как найти все возможные комбинации чисел от 1 до n-1 чтобы их сумма была равна n?

Евгений, Вам надо понять как работает рекурсия и стек вызовов. Вам не надо ничего запоминатать, оно само откатится куда надо. Код, что я привел - почти рабочее решение на C++, надо только if() в начале функции поменять местами.

Вот пример для n=2. Тут по вертикали время, а количество отступов соответствует глубине рекурсии.

Generate(1,0, {0}). 
  Вызывает Generate (2, 2, 0, {})
    Вызывает Generate(2, 3, 0, {})
    Вызывает Generate(2, 3, 2, {2})
  Вызывает Generate(2, 2, 1, {1})
    Вызывает Generate(2, 3, 1, {1})
    Вызывает Generate(2, 3, 3, {1,2})

Сначала функция с парматрами (2, 1, 0, {}) вызовет (2,2,0, {}). Эта функция что-то там рекурсивно повызывает, подсчитает и вернется. Потом будет вызов функции с параметрами (2,2,1,{}) двумя строчками ниже в коде. Обратите внимание, эти 2 вызова с одинаковым количеством отступов. Все, что правее их - вызвано ими рекурсивно. При этом на каждом уровне все локальные переменные и параметры хранятся в стеке. Поэтому когда фукция (2,2,0, {}) закончится, исполнение в функции будет иметь пустой массив taken, несмотря на то, что несколько циклов процессора назад переменная taken содержала число 2. Но это была другая копия taken, ниже по стеку, в другом вызове! В общем, я не могу вам нагляднее объяснить как работает рекурсия и функции. Гуглите, читайте книжки.

Ну или альтернатива, если так понятнее - перебирайте все подмножества как битовые числа без рекурсии (если чисел всего не более 64). Типа вот есть 3 числа {1,2,3} - назначьте каждому числу разряд. 1 - еденицы, 2 - двоичные десятки, 3 - сотни. Тогда любое подмножество соответсвует строке из 0 и 1 или битовому числу. Где стоят еденицы в двоичной записи числа - те числа и есть в множестве.

Вроде как {} = 0, {1} = 001(2) = 1, {2} = 010(2) = 2, {1,2} = 011(2) = 3, {3} = 4, {1,2,3} = 7.
При этом строка 11010 или число 26 будет соответствовать множеству {2,4,5}.

Теперь можно все подмножества перебирать просто циклом от 0 до 2^n - 1. Потом битовыми операциями извлечь биты из переменной-индекса, преобразовать их в список чисел, просуммировать и сравнить с n.
Тут нужно будет или с битовыми сдвигами и пробитовыми и работать или с операциями взятия остатка от деления на 2. Если чисел больше 64 - то надо реализовывать битовую арифметику на строке из 0 и 1 и столбиком прибавлять в нее 1.

Но это решение не оптимизировать, оно будет всегда перебирать все подмножества, даже заведомо бесполезные. Типа если вам надо собрать 100, то вы будете перебирать 2^97 подмножеств с {99, 98}, хотя там сумма точно будет больше 100. В рекурсивной реализации, которая собирает множества постепенно можно впихнуть всякие оптимизации, типа раннего выхода, если сумма уже слишком большая.

Как найти максимум в бинарном дереве Java?

res2001, Это если бинароное дерево поиска. У автора ничего не сказано о том, что дерево упорядоченое.

Как решить задачу с CodeWars Simple Fun #159: Middle Permutation?

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

Но это в питоне. В какой-нибудь java пришлось бы использовать специальный BigInt, потому что стандартные целые тоже фиксированной длины.

Какой алгоритм можно применить для задачи размещения числа в фиксированные контейнеры?

Не знаю, проще ли будет код, но можно сделать полный перебор с рекурсивной функцией.
Но это переписать все. С одной стороны - там не будет заумного динамического программирования. с другой стороны, там будет рекурсия.

Из предложенного решения ничего не выкинуть, даже для 10-ти контейнеров.

Как решить задачу с CodeWars Simple Fun #159: Middle Permutation?

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

Если символов четно - то ответ средний символ, а за ним все остальные по убыванию. Например, "cfedba"
Если символов нечетно, то овтет средний символ, предыдущий, а за нимим все остальные по убыванию. например "nmzyxwvutsrqpolkjigfedcba"

Какой алгоритм можно применить для задачи размещения числа в фиксированные контейнеры?

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