Какова логика алгоритма

Question

Я пытаюсь решить проблему с codility

«Даже суммы»

, но я не в состоянии сделать это. Вот вопрос ниже.

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

Вы играете в эту игру против своего оппонента, и хотите узнать, сможете ли вы выиграть, предполагая, что вы и ваш оппонент играете оптимально. Сначала двигаешься.

Написать функцию:

string solution(vector< int>& A);

, что при нулевой индексированный массив А, состоящий из N целых чисел, возвращает строку формата «X, Y», где Х и У, соответственно, первую и последнюю позиции (включительно) разреза, которую вы должны удалить при первом ходу, чтобы выиграть, если у вас есть выигрышная стратегия. Если есть более одного такого выигрышного фрагмента, функция должна вернуть тот, который имеет наименьшее значение X. Если имеется более одного среза с наименьшим значением X, функция должна возвращать кратчайший. Если у вас нет выигрышной стратегии, функция должна вернуть «NO SOLUTION».

Например, если следующий массив:

А [0] = 4 А [1] = 5 А [2] = 3 А [3] = 7 А [4] = 2

Функция должна возвращать «1,2». После удаления среза из позиций 1 - 2 (с четной суммой 5 + 3 = 8) оставшийся массив равен [4, 7, 2]. Тогда противник сможет удалить первый элемент (четной суммы 4) или последний элемент (четной суммы 2). Впоследствии вы можете сделать ход, который оставляет массив, содержащий только [7], поэтому ваш оппонент не будет иметь законный ход и проиграет. Одна из возможных игр показана на following picture

Обратите внимание, что удаление среза «2,3» (с четной суммой 3 + 7 = 10) также является выигрышным движением, но срез «1,2» имеет меньший значение X.

Для следующего массива:

А [0] = 2 А [1] = 5 А [2] = 4

функция не должна возвращать «нет решения », так как нет стратегии, которая гарантирует вам победу.

Предположим, что:

N представляет собой целое число в диапазоне [1..100,000]; каждый элемент массива A является целым числом в диапазоне [1..100000000]. Сложность:

Ожидаемая наихудшая временная сложность - O (N); ожидаемая наихудшая сложность пространства - это O (N), за пределами входного хранилища (не считая хранения, необходимого для входных аргументов).Элементы входных массивов могут быть изменены. Я нашел решение онлайн в python.

def check(start, end): 
    if start>end: 
     res = 'NO SOLUTION' 
    else: 
     res = str(start) + ',' + str(end) 

    return res 

def trans(strr): 
    if strr =='NO SOLUTION': 
     return (-1, -1) 
    else: 
     a, b = strr.split(',') 
     return (int(a), int(b)) 


def solution(A): 
    # write your code in Python 2.7 

    odd_list = [ ind for ind in range(len(A)) if A[ind]%2==1 ] 

    if len(odd_list)%2==0: 
     return check(0, len(A)-1) 


    odd_list = [-1] + odd_list + [len(A)] 
    res_cand = [] 
    # the numbers at the either end of A are even 
    count = odd_list[1] 
    second_count = len(A)-1-odd_list[-2] 
    first_count = odd_list[2]-odd_list[1]-1 
    if second_count >= count: 
     res_cand.append( trans(check(odd_list[1]+1, len(A)-1-count))) 

    if first_count >= count: 
     res_cand.append( trans(check(odd_list[1]+count+1, len(A)-1))) 

    twosum = first_count + second_count 
    if second_count < count <= twosum: 
     res_cand.append( trans(check(odd_list[1]+(first_count-(count-second_count))+1, odd_list[-2]))) 

    ########################################### 
    count = len(A)-1-odd_list[-2] 
    first_count = odd_list[1] 
    second_count = odd_list[-2]-odd_list[-3]-1 
    if first_count >= count: 
     res_cand.append( trans(check(count, odd_list[-2]-1))) 

    if second_count >= count: 
     res_cand.append( trans(check(0, odd_list[-2]-count-1))) 

    twosum = first_count + second_count 
    if second_count < count <= twosum: 
     res_cand.append( trans(check(count-second_count, odd_list[-3]))) 



    res_cand = sorted(res_cand, key=lambda x: (-x[0],-x[1])) 

    cur = (-1, -2) 
    for item in res_cand: 
     if item[0]!=-1: 
      cur = item 

    return check(cur[0], cur[1]) 

Этот код работает, и я не могу понять код и поток одной функции на другую. Однако я не понимаю логику алгоритма. Как он подошел к проблеме и решил ее. Это может быть долгой задачей, но кто-нибудь может позаботиться о том, чтобы объяснить мне алгоритм. Заранее спасибо.

Answer 1

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

Теперь мне нужно понять логику сравнения, например «если first_count> = count», и если «second_count < count < = twosum».

Обновление: Эй, ребята, я выяснил решение моего вопроса и, наконец, понял логику алгоритма.

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

Если есть четное количество шансов, мы можем напрямую выиграть игру.

Если есть странное количество коэффициентов, мы всегда должны пытаться сделать массив симметричным. Это то, что алгоритм пытается сделать.

Теперь есть два случая. Остается либо последний нечетный, либо первый нечетный. Я буду рад объяснить больше, если вы, ребята, этого не поняли. Благодарю.