Leetcode наступает. 896. Выяснить, является ли последовательность монотонной. Штурмуем топ.
Вопрос из категории Easy:
https://leetcode.com/problems/monotonic-array/description/comments/2077484/
На входе функции - массив. Нужно вернуть true, если он монотонно не возрастает или не убывает (могут быть равные соседние элементы), и false, если порядок в массиве - такой же, как на данном ресурсе, т.е. отсутствует. В массиве - до 100000 чисел в диапазоне [-100000, +100000].
Нет ничего проще, чем перебрать все элементы в цикле и найти первое нарушение порядка, либо доказать отсутствие нарушения. Это обойдётся нам в O(n) операций. Но мы же не хотим "почётное" место среди 46% дилетантов ( https://leetcode.com/submissions/detail/1061885493/ ). Поэтому пробуем "боевые" решения.
Попытка №1. 64ms. https://leetcode.com/problems/monotonic-array/submissions/1061952031/
#pragma GCC optimize ("unroll-loops")
bool isMonotonic(vector<int>& nums) {
int prev = nums[0];
unsigned char flags = 0;
for (unsigned i = 1; i < nums.size() && flags != 3; i++) {
const int curr = nums[i];
flags |= (curr < prev) | ((curr > prev) << 1);
prev = curr;
}
return flags != 3;
} Убраны все джампы, кроме цикла. Добавлена прагма для развёртки цикла.
Давим синхронизацию с stdio, это не привожу для экономии места.
Предыдущий рекордсмен получил 61 ms на ужасной реализации такого же решения, но я не смог его обойти.
Попытка №2. 55 ms. https://leetcode.com/problems/monotonic-array/submissions/1062141454/
Код не пролезает по размеру, но доступен по ссылке.
Пробуем 3 элемента из середины массива и 1 из конца в расчёте на то, что если данные плохие, то это выяснится сразу. Положительный сценарий придётся пробежать полностью. Сложность: O(n + 4) = O(n), в хороших случаях - константа.
Попытка №3. 53 ms. https://leetcode.com/problems/monotonic-array/submissions/1062558817/
#pragma GCC optimize ("unroll-loops")
#define COMPARE(prev, curr) ((curr < prev) | ((curr > prev) << 1))
bool isMonotonic(vector<int>& nums) {
const unsigned n = nums.size();
if (n < 2) return true;
int prev = nums[0], sec = nums[1];
unsigned char flags = COMPARE(prev, sec);
for (unsigned i = 1; i < n && flags != 3; i <<= 1) {
const int curr = nums[i];
flags |= COMPARE(prev, curr);
prev = curr;
}
if (flags != 3) {
const int last = nums.back();
flags |= COMPARE(prev, last);
prev = nums[0];
}
for (unsigned i = 1; i < n && flags != 3; i++) {
const int curr = nums[i];
flags |= COMPARE(prev, curr);
prev = curr;
}
return flags != 3;
} Это - обобщение предыдущего решения. Используем экспоненциальный поиск в надежде быстро обнаружить нарушение порядка. Сложность: O(n + log(n)) = O(n), в хороших случаях - логарифм или константа.
Что ещё можно сделать для снижения асимптотики "в среднем"?
Использовал указатели
class Solution {
public:
const int* trend(const int* const p, const int* const end, int& mono) noexcept {
auto a = p;
auto b = p + 1;
while (b != end && *a == *b) {
++a;
++b;
}
if (b != end) mono = *b > *a ? 1 : -1;
return b;
}
bool increasing(const int* p, const int* const end) noexcept {
while (p < end) {
if (*p < *(p - 1) || *p > *(p + 1)) {
return false;
}
p += 2;
}
return p == end ? *p >= *(p - 1) : true;
}
bool decreasing(const int* p, const int* const end) noexcept {
while (p < end) {
if (*p > *(p - 1) || *p < *(p + 1)) {
return false;
}
p += 2;
}
return p == end ? *p <= *(p - 1) : true;
}
bool isMonotonic(const vector<int>& nums) noexcept {
ios::sync_with_stdio(false);
cin.tie();
cout.tie();
const auto length = nums.size();
if (length < 3) return true;
auto p = nums.data();
const auto end = nums.data() + length - 1;
auto mono = 0;
p = trend(p, end, mono);
if (mono < 0) return decreasing(p, end);
else if (0 < mono) return increasing(p, end);
return true;
}
}; И получил такой результат:
>Что ещё можно сделать для снижения асимптотики "в среднем"?
Пытаться угадать алгоритм и данные проверки, поэтому подозреваю, что в лидерах должны быть люди, закинувшие туда сгенерированный нейросетями код, брутофорсящий закономерности в тестовых данных
Можно пытаться экономить на спичках, заменяя ассемблером, mmx'овыми интринсиками для сравнения или многопоточностью, если там это доступно, не в курсе правил проекта; исходники тоже не открываются без регистрации
Алгоритмически - только если там тесты проходят программы, которые могут возвращать неправильный ответ.
А что насчет использования двух потоков для больших массивов, или слишком высокие накладные расходы даже для такой задачи?
Здравствуйте,я вас видел в сообщениях на маиле и у меня к вам просьба,дайте ваш совет,как профессионала для меня по олимпиадному программированию - https://otvet.mail.ru/question/236682882