1. C++ / Говнокод #24024

    +1

    1. 01
    2. 02
    3. 03
    4. 04
    5. 05
    6. 06
    7. 07
    8. 08
    9. 09
    10. 10
    11. 11
    12. 12
    13. 13
    14. 14
    15. 15
    16. 16
    17. 17
    18. 18
    19. 19
    20. 20
    21. 21
    22. 22
    23. 23
    24. 24
    25. 25
    bool almostIncreasingSequence(std::vector<int> sq) {
        bool b2 = true; 
        int s = sq.size(); 
        if (s > 2) {                                           // Последовательность меньше трех чисел дает истину.                          
            int i = 1;                                         // Проверка начинается со второго элемента.                                             
            int x = -1;                                      // Для записи индекса элемента <= предыдущего, а еще "флаг".           
            while ((b2) && (i < s)) {              // При нахождении 2-го лишнего происходит выход из цикла.                                 
                if (x != -1) {                               // Проверка "флага".                                                                                             
                    if (sq[i] <= sq[i - 1]){           // Сравнение с предыдущим элементом.                                                             
                        b2 = false;                        // Если условие истинно, то это уже второй элемент,                                
                    }                                             // "конфликтующий" с предыдущим, следовательно, выход и "ложь".
                    if ((sq[i] <= sq[x - 1]) && (x != 1) && (sq[i - 1] <= sq[x - 2])) {  // над этим условием я думал слишком долго
                        b2 = false;                       // Если элемент был "убран", индекс конфликтного                                   
                    }                                            // элемента записан в "x".                                                                                   
                }     
                else {                                        // Если условие ложно, то записываем индекс элемента, который
                        if (sq[i] <= sq[i - 1]) {     // "конфликтует" с предыдущим.
                            x = i;                             // Нам не известно лишний он или нет.
                        } 
                    }
                i++;
                }
            }
          return b2;
    }

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

    Запостил: noserdan, 28 Марта 2018

    Комментарии (44) RSS

    • cbf5a8e5968f9c3af26e737a5a4f87e3
      Ответить
      • сложна. заинтриговал, скажи хоть на чем это
        Ответить
        • md5?
          Ответить
          • Сначала тоже задавался этим вопросом, но потом ещё джва послания марсиан появились: http://govnokod.ru/24025#comment410419, и я уже начал подозревать, что это за рептилоиды.

            http://govnokod.ru/22738#comment409233

            Думаю, ничего полезного в этих комментариях нет, разгадавший их максимум найдёт уязвимость в говнокоде inho или получит IP от какого-нибудь прокси, через который спамит g0_***.
            Ответить
            • гугл говорит, что разгадывать подобное - хардкор
              Ответить
            • Опенсурс же, можно не гадать а тупо прочитать как инхо этот хеш делает.
              Ответить
              • в чем смысл сего действия?
                в плане - нах энтот спам, я не разумею
                Ответить
                • У Вас ссылки некликабельные? Заведите PRO аккаунт.
                  http://govnokod.ru/22738#comment409233

                  Этот спам нужен, чтобы можно было на другом сайте подтвердить свою учётную запись с этого сайта - чтобы в будущем все точно знали, что вот это Борманд, вот это спамер g0_циферки.
                  ссылка доступна для владельцев платных аккаунтов
                  Ответить
              • > Опенсурс же, можно не гадать а тупо прочитать как инхо этот хеш делает.

                Код не читал, но подозреваю, что это тест трансфера аккаунтов на .xyz, мы как-то обсуждали похожий способ в комментах.
                Ответить
                • Ну тогда это просто рандомный токен и скрытого смысла в нём нет.
                  Ответить
                  • Скрыл свой двадцатиметровый смысл в твоём анусе, проверь.
                    Ответить
    • ?
      bool almostIncreasingSequence(const std::vector<int> & sq)
      {
          bool elRemoved = false;
          for (size_t i = 1; i < sq.size(); i++) {
              if (sq[i] <= sq[i - 1]) {
                  if (elRemoved) {
                      return false;
                  } else {
                      elRemoved = true;
                  }
              }
          }
          return true;
      }
      Ответить
      • А нет.
        Ответить
        • bool almostIncreasingSequence(const std::vector<int> & sq)
          {
              bool elRemoved = false;
              for (ptrdiff_t i = 1; i < sq.size(); i++) {
                  if (sq[i] <= sq[i - 1]) {
                      if (elRemoved) {
                          return false;
                      } else {
                          if (i - 2 >= 0 && sq[i] <= sq[i - 2]) {
                              return false;
                          }
                          elRemoved = true;
                      }
                  }
              }
              return true;
          }

          Хм, интересно, а можно короче?
          Ответить
          • > Хм, интересно, а можно короче?

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

            almostIncreasingSequence({1, 2, 0, 3}) => false
            Ответить
    • Нужно больше алгоритмов
      // https://ideone.com/jeuT8j
      template <class It, class Less>
      bool almost_increasing_seq(It begin, It end, Less cmp) {
        const auto lbound = std::adjacent_find(begin, end, std::not2(cmp));
        if (lbound == end) {
          return true; // already sorted
        }
        const auto rbound = lbound + 1;
        if (rbound == end || (rbound + 1) == end) {
          return true; // can just drop the last one
        }
        return std::adjacent_find(rbound, end, std::not2(cmp)) == end &&
               (lbound == begin || cmp(*lbound, *(rbound + 1)) ||
                cmp(*(lbound - 1), *rbound));
      }
      Ответить
      • я еще слишком слаб, для меня это пока эльфийская грамота =^_^=
        Ответить
        • сосбна, глянув ответы других участников(codefights), сдается мне, что я один из немногих, кто додумался нахреначить сложных проверок. Но чем проще решение, тем сложнее дойти до него
          Ответить
          • > нахреначить сложных проверок

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

            Основная часть проверок нужна для того, чтобы обработать подпоследовательности из одного элемента.

            Если в голове последовательности приклеить виртуальную минус-бесконечность, которая меньше всех элементов массива, а к хвосту ­— виртуальную плюс-бесконечность, которая больше всех элементов массива, то примерно половина проверок не нужна, т.к. тогда каждая подпоследовательность либо будет пустой, либо будет состоять из двух элементов и более. Вот только для инта таких бесконечностей не существует.
            Ответить
            • Что-то вроде
              // https://ideone.com/LCUKpY
              data ExtInt = NegInfty | Normal Int | PosInfty deriving (Show, Eq, Ord)
              
              adjacentZipper :: (a -> a -> Bool) -> [a] -> ([a], [a])
              adjacentZipper cmp items = go [] items
                where go front [] = (front, [])
                      go [] (x:rest) = go [x] rest
                      go [email protected](y:_) [email protected](x:rest) = if cmp x y then go (x:ys) rest else (ys, xs)
              
              almostIncreasing :: [Int] -> Bool
              almostIncreasing nums = check ([NegInfty] ++ map Normal nums ++ [PosInfty])
                where check items = case adjacentZipper (>) items of
                                      (_, []) -> True
                                      ((x2:x1:_), [email protected](y1:y2:_)) -> (x1 < y1 || x2 < y2) && sorted right
                      sorted = null . snd . adjacentZipper (>)
              Ответить
              • > исходная последовательность должна быть конкатенацией двух строго возрастающих подпоследовательностей, которые можно склеить вместе, выкинув хвост первой или голову второй.

                вот если так говорить, это только еще больше запутывает, особенно дальнейшее объяснение)
                Ответить
                • Посмотрите мой ответ ниже.

                  Алгоритм в общих чертах такой:
                  Проходим по последовательности и проверяем, что каждый следующий член строго (или нестрого, в зависимости от условий задачи) больше предыдущего. Если нашли такой, который меньше -- увеличиваем счетчик на единицу. Если после прохода по последовательности оказывается, что такой член только один, значит можно убрать его из последовательности, и она станет возрастающей. Можно вернуть положительный ответ.
                  Ответить
                  • 1 2 3 4 5 2 3 4
                    Ответить
                    • А ты посмотри на код ниже, там же если возник элемент меньше предыдущего, то current не перезаписывается. На твоей последовательности вернет False.
                      Ответить
                    • Если на словах говорить точнее, можно рассматривать последовательность как график дискретной функции. Нас интересуют такие графики невозрастающие графики, из которых можно убрать одну точку так, чтобы они стали возрастающими. То есть проходим по точкам и убеждаемся, что для точки ai должно выполняться: количество точек aj при j > i, таких, что aj < ai должно быть не больше единицы, и точек, для которых это число не равно нулю тоже не больше одной.

                      Но при такой модели напрашивается квадратный алгоритм, (проверять для каждой точки оставшуюся часть последовательности), хотя можно за один проход, как я написал ниже.
                      Ответить
              • > Идея решения на самом деле простая: исходная последовательность должна быть конкатенацией двух строго возрастающих подпоследовательностей, которые можно склеить вместе, выкинув хвост первой или голову второй.

                Чо-то хуйня какая-то. Вот же:
                def check(a):
                    current = a[0]
                    count = 0
                    for i in range(1, len(a)):
                        if a[i] < current:
                            count += 1
                            if count > 1:
                                return False
                        else:
                            current = a[i]
                    
                    return count == 1

                Котировки валют видели когда-нибудь, где рост относительно предыдущего значения обозначается зеленым столбиком, падение -- красным. Так вот достаточно за один проход по последовательности проверить, что красных столбиков не более или в точности равно одному, в зависимости от задачи.
                Ответить
                • я ща проверю там на тестах
                  Ответить
                • Валится на тесте "1,3,2". Я неверно переписал?

                  int current = a[0];
                      int count = 0;
                      for (int i = 1; i < a.size(); i++)
                      {
                          if (a[i] < current)
                          {
                              count += 1;
                              if (count > 1)
                                  return false;
                          }
                          else
                              current = a[i];
                      }
                      return (count == 1);
                  Ответить
                  • ошибся, на примере "1,2,1,2"
                    10, 1, 2, 3, 4, 5
                    Ответить
                    • На [1, 2, 1, 2] не должно валиться. Проверь условия задачи, тебе нужна строго возрастающая или неубывающая последовательность. В зависимости от этого, возможно нужно поправить сравнение в условии на <=.

                      Про случай, когда надо выкинуть первый элемент [10, 1, 2, 3, 4, 5] я совсем не подумал. Но должно хватить костылика:
                      int current = min(a[0], a[1]);
                      Понимаешь, почему это сработает, да?
                      Ответить
                  • 1, 2, 3, 4, 5, 3, 5, 6
                    1, 2, 3, 4, 99, 5, 6
                    123, -17, -5, 1, 2, 3, 12, 43, 45
                    Ответить
                    • [1, 2, 3, 4, 99, 5, 6]

                      А, да, этот пример показывает, что мой метод полная хуйня.
                      Забудь его, и делай, как сказал Роман.
                      Ответить
                      • да я уже сделал) мой пример из поста.
                        переписывать стоит, если понял решение, а там есть вещи мне незнакомые
                        Ответить
                      • > А, да, этот пример показывает, что мой метод полная хуйня.

                        Я не понимаю, почему все хотят решить задачу в одном цикле, это же неудобно, надо хранить какие-то лишние состояния (removed/count/b2/etc).
                        Если решать так, как я объяснял, то никакой мутабельности и сложных переходов: находим, где одна подпоследовательность рвётся и начинается другая, пытаемся приклеить. Не надо трекать в уме никакие состояния. Код лучше декомпозируется, разделяется на простые функции:
                        • функция поиска первого места, где подпоследовательность перестаёт быть возрастающей;
                        • функция, проверяющая, можно ли объединить две возрастающие подпоследовательности, возможно, выкинув один элемент из одной из них.
                        Ответить
                        • > Я не понимаю, почему все хотят решить задачу в одном цикле, это же неудобно
                          > Если решать так, как я объяснял, то никакой мутабельности и сложных переходов
                          Вероятно, Вы просто лучше продвинулись по лестнице абстракции. Там у Вас хорошо, дует ветерок, всё просто и понятно.
                          У нас внизу всё гораздо печальней. Получается либо сложный цикл, либо простой, но за квадратичное время. А написать сложный цикл всё ещё легче, чем подняться на ту же ступеньку абстракции и написать простой цикл.
                          Ответить
                          • >У нас внизу всё гораздо печальней. Получается либо сложный цикл

                            Что если сохранить начальные индексы отсортированных subsequence in array?

                            А потом просто сравнить значения по индексам-брейкерам?

                            //arr= [1, 2, 3, 4, 99, 5, 6]
                            Сохраняем:
                            indx=[0, 4, 5]
                            Делаем все сложные проверки (массив не больше 3х, indx[2]-indx[1]==1, arr[indx[2]]>arr[indx[1]-1]).
                            Ответить
                            • Подумал над этим. Мне это не кажется сильным упрощением, просто некоторые проверки перешли в другой цикл. Столь сильного математического смысла, как у Романа, чтобы можно было думать в новых категориях, тут вроде бы нет.
                              Ответить
                        • >Я не понимаю, почему все хотят решить задачу в одном цикле

                          Потому что Царь живёт в каждом.
                          В смысле 1 проход оптимальнее.
                          Любое разумное существо на интиутивном уровне стремится делать что-то за 1 раз.
                          Ответить
                          • > 1 проход оптимальнее
                            Ну 2 цикла ещё не подразумевают 2 прохода (и тем более — квадратичность). К примеру, первый по первой половине последовательности пробежал, а второй ­— по оставшейся.
                            Ответить
                          • > В смысле 1 проход оптимальнее.

                            Оптимально не делать лишних проверок. Например, когда печатаешь список, разделённый запятыми, оптимально сразу проверить на пустоту и вывести первый элемент, а потом написать простой цикл, а не долбить if (first) в цикле.
                            Ответить
                            • > не долбить if (first) в цикле
                              Бранчпредиктор зарешает.
                              Ответить
    • const ordered = (a, b) => a < b;
      
      function almostIncreasingSequence(xs) {
        for(var i=0, removed = false; i<xs.length - 1; ++i) {
          if(!ordered(xs[i], xs[i+1])) {
            
            // если раньше убирали, а теперь непоследовательность второй раз
            // или уберём сейчас левый или правый, а последовательности не будет
            if(removed ||
               i > 0 && !ordered(xs[i-1], xs[i+1]) &&
               i + 2 < xs.length && !ordered(xs[i], xs[i+2])) return false;
            
            // если выкинуть один, xs[0]..xs[i+1] - упорядочена
            removed = true;
          }
        }
        
        return true;
      }


      Вроде работает. Сравнивал с наивной квадратичной питушнёй:
      const least = -Infinity;
      
      const isIncreasingSequence1 = (_, n, xs) => xs.reduce((r, x, i) =>
        i == n ? r : [r[0] && ordered(r[1], x), x], [true, least])[0];
      
      const almostIncreasingSequenceNaive = xs =>
        isIncreasingSequence1(null,-1, xs) || xs.some(isIncreasingSequence1);

      Сравнение:
      function seqInc(xs) {
        const dmin = -3, dmax = 3;
        for(var i=0; i<xs.length; ++i) {
          if(++xs[i] > dmax) xs[i] = dmin;
          else break;
        }
        if(i >= xs.length) {
          for(var i=0; i<xs.length; ++i) xs[i] = dmin;
          xs.push(dmin);
        }
      }
      
      var seq = [];
      
      while(seq.length < 7) {
        var a = almostIncreasingSequence(seq);
        var an = almostIncreasingSequenceNaive(seq);
        if(a != an) console.error(seq, a, an);
        seqInc(seq);
      }

      https://ideone.com/Dba2sx
      Ответить
      • def almostIncreasingSequence(seq):
        	border = -1;
        	for i in range(0, len(seq) - 1):
        		if seq[i] > seq[i + 1]:
        			if border > -1:
        				return False
        			else:
        				border = i + 1
        
        	return border == 1 or \
        		   border == len(seq) - 1 or \
        		   seq[border - 1] <= seq[border + 1] or \
        		   seq[border - 2] <= seq[border]
        Ответить
        • Эта питушня работает, или я не прав?

          Поправил ordered на <= (кстати, в моём коде можно только < на <= в ordered поменять, чтобы поддерживались и неубывающие питухи). Загнал её в своё сравнение с наивным питухом - в итоге даже выдаёт false на массивах длины два.
          https://ideone.com/G2RQgO
          Ответить

    Добавить комментарий