Codility Counting Lesson

Question

나는 Codility Counting Lesson (https://codility.com/media/train/2-CountingElements.pdf)을 공부하고 있으며, 가장 빠른 해결책을 이해하는 데 도움이 필요합니다.

왜 8 라인에서 차이가 2로 나뉘어 지는지 궁금합니다 d //= 2? 우리가 배열간에 교환 할 수있는 요소를 찾기에 차이가 없어야합니까?

문제점 :

당신이 정수 m (1 < m < 1000000)와 두 개의 비어, 제로 인덱스 배열 A 및 Bn의 정수, a0, a1를 부여, ..., an−1b0, b1, ..., bn−1 (0 < ai, bi < m). 배열 A의 요소 합계가 스왑 후 배열 B의 요소 합계와 같도록 이러한 배열에서 이 될 수있는 스왑 연산이 있는지 확인하는 것이 목표입니다. 스왑 연산이란 배열 A에서 하나의 요소를 선택하고 배열 B에서 요소 하나를 가져 와서 교환하는 것을 의미합니다.

용액 :

def fast_solution(A, B, m): 
    n = len(A) 
    sum_a = sum(A) 
    sum_b = sum(B) 
    d = sum_b - sum_a 
    if d % 2 == 1: 
     return False 
    d //= 2 
    count = counting(A, m) 
    for i in xrange(n): 
     if 0 <= B[i] - d and B[i] - d <= m and count[B[i] - d] > 0: 
      return True 
    return False 

Answer 1

A[i 간의 스왑] 및 B[j] 덧붙인다 B[j]-A[i]sum(A) 및 가 감산 sum(B)에서 동일한 값; 그러므로 그것은 합계의 차이에 두 번B[j]-A[i] 의해 영향을 미칩니다.

결과적으로 원래의 차이점을 반으로 줄이면 (올바른지 확인한 후 - 스왑이 작동하지 않으면! -) 가능한 스왑 대상을 구성합니다.

참고 또한 그들이 제공하는 counting 기능은 최적의 현대 파이썬이 아니라고 - "계산 항목"의 특정 바퀴를 재발 방지하기 위해, Ea = a0 + a1 + .. + a(n-1)하자 파이썬 3에 대한

Answer 2

를 파이썬 2 https://docs.python.org/2/library/collections.html#collections.Counter, 또는 https://docs.python.org/3/library/collections.html#collections.Counter를 참조하십시오. Eb = b0 + b1 + .. + b(n-1)으로 설정하십시오. 그런 다음 요소 ai과 bj을 교환하면 해당 합계에 다음과 같은 효과가 발생합니다. Ea - ai + bj, Eb + ai - bj. 문제 설명에 따르면 그 합은 동일해야하므로 Ea - ai + bj = Eb + ai - bjd = bj - ai을 지정합시다. 그 다음 우리는 다음과 같은 동등성을 가지고 있습니다 : Ea + d = Eb - d 이것은 2d = Eb - Ea 또는 d = (Eb - Ea)/2을줍니다. 케이스를 들어 EB (- EA) 알렉스 마르 텔리

유일한 것은 왼쪽은 bj 및 ai 그래서 bj - ai = d을 찾을 수 있습니다에서 comment를 참조하십시오 홀수이다.