На чем следует сосредоточиться при выполнении соревновательного программирования

Опубликовано: 30 Ноября, 2021

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

  • Составьте список функций для выполнения задач, которые часто встречаются в вопросах, и добавьте их в свой код в виде шаблона. Это экономит время во время конкурсов и помогает быстро подавать решения. В шаблон необходимо добавить следующие ценные функции:
    • Степенная функция ( N % M , где a, b, N - целые числа, а M - простое число)
    • Печать основных факторов
    • Печать простых чисел
    • Функция для поиска nCr с использованием мода
    • Функция для расчета НОД.
  • Сосредоточьтесь на ограничениях, думая о подходе к решению проблемы. Основываясь на ограничениях, проверьте, может ли разработанное решение пройти все тестовые примеры, рассчитав временную сложность вашего подхода.
  • Думайте о битовой маске или грубой силе только в том случае, если ограничения достаточно малы (скажем, 2 Н ), которые не превышают лимит времени. Таким образом, подход должен включать проверку всех возможных комбинаций результатов.
  • Если есть вопрос, связанный с сортировкой данных в форме ввода, подумайте о подходе с использованием двоичного поиска.
  • Если есть вопрос, связанный с деревьями, графиками (обнаружение цикла и другие), выработайте мышление, чтобы подумать о подходе, основанном на поиске в глубину или поиске в ширину, что является основным требованием для решения такого типа проблем.
  • Теория чисел :
    • Сложение двух или более нечетных простых чисел всегда будет четным ( например, 13 + 3 = 16, 19 + 5 = 24).
    • Гипотеза Гольдбаха - одна из хорошо известных нерешенных проблем математики (точнее, теории чисел). Примечание: для больших чисел это не доказано.
    • В теории чисел есть несколько других концепций, которые необходимо усвоить, чтобы преуспеть в CP.
  • Если состояние зависит от будущего состояния, то решить проблему жадным решением невозможно. Более того, к наивному подходу прибегать нельзя, так как он превысит срок. Следовательно, для решения всех таких проблем всегда старайтесь подходить к решению динамического программирования.
    Это очень просто, если можно написать простое рекурсивное решение, работающее с экспоненциальной сложностью. Сохранение каждого пройденного пути в памяти, который можно было бы использовать позже для продвижения в направлении решения. Это называется мемоизацией. Как только метод мемоизации изучен, постепенно изучите метод табуляции.
  • Если есть вопрос, связанный с побитовыми операторами, такими как XOR , OR и AND, он может изменять массив с помощью этих операций, тогда иногда будет работать наивный подход, поскольку будет не более 64 чисел с разными MSB (2 64 ) . Но при таком подходе основная задача - выявить базовый вариант.
    Давайте возьмем пример, в котором дан отсортированный массив в порядке возрастания, и задача состоит в том, чтобы сделать его невозрастающим, заменив два соседних элемента их побитовым исключающим ИЛИ два минимального количества раз.

    Input: arr[] = {2, 5, 6, 8}
    Output: 1
    Explanation:
    Operation 1: Choose elements 2 and 5, and replace 2 them with 2⊕5 = 7.
    Now, the array will be {7, 6, 8} which is non-increasing.
    Hence, the count of operation is 1.

    Подход: Эту проблему можно решить и наивным способом, т. Е. Найти подмассив, XOR которого меньше, чем элемент перед начальной точкой подмассива, или меньше, чем элемент после конечной точки подмассива.

    Но перед этим обработайте базовый случай: если существует 3 непрерывных элемента, для которых MSB одинаков ( например, MSB of arr [i - 1] = arr [i] = arr [i + 1] ), то результат получается заменив его на arr [i] ⊕ arr [i + 1] .

    Итак, для наивного подхода в массиве только когда N> 60, потому что 2 * (⌊log 2 10 9 ⌋ + 1) = 60 . (Пусть, a [i] <= 10 9 ). Умножьте 2, потому что это единственный возможный последний случай. Если его умножить на 3, то обязательно будет 3 непрерывных элемента с одинаковым MSB (наиболее значимым битом).

  • НОД элементов массива также можно выразить как:

    gcd(a1, a2, ⋯, an − 2, an − 1, an) = gcd(a1, a2 – a1, ⋯, an – 1 – an − 2, an − an − 1)

    Доказательство:

    gcd(a, b) = gcd(a, b  – a)
    gcd(a, b, c) = gcd(a, gcd(b, c)) = gcd(gcd(a, b), c)
    Then, it can be generalized as: 
    gcd(a1, a2, ⋯, an−1, an)   = gcd(a1, a2, ⋯, an−2, gcd(an−1, an))
                                                         = gcd(a1, a2, ⋯, an−2, gcd(an−1, an−an−1))
                                                         = gcd(a1, a2, ⋯, an−2, an−1, an−an−1)
                                                         = gcd(a1, a2, ⋯, gcd(an−2, an−1), an−an−1)
                                                         = gcd(a1, a2, ⋯, gcd(an−2, an−1−an−2), an−an−1
                                                             …
                                                         = gcd(a1, a2, ⋯, an−2, an−1−an−2, an−an−1)

  • Вот некоторые из наиболее часто используемых свойств побитового оператора:
    • a ⊕ b = a | б - а и б
    • а + б = а ⊕ б + 2 * (а и б)
    • а + Ь = а | б + а и б

    Здесь 'a' и 'b' - целые числа, ⊕ означает XOR, & означает AND и | означает ИЛИ.

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по доступной для студентов цене и будьте готовы к работе в отрасли. Получите все важные математические концепции для соревновательного программирования с курсом Essential Maths for CP по доступной для студентов цене.

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.