일치 결과 집합이 주어지면 O (n) 시간에 최대 10 개의 손실을 가진 팀을 어떻게 얻을 수 있습니까?

Question

다음 문제를 해결하기 위해 의사 코드를 작성하려고합니다.

입력 : 농구 경기의 n 팀. 각 팀 TI는, TJ 재생과 승리/손실 기록이 매트릭스에있는
그들이 돈 경우

는 팀이 메달을 얻는다 (TI는 TJ 이기면 내가 < J, A [I, J = 1) ' 10 회 이상 잃지 마라.

출력 : 메달을받는 모든 팀. O (n) 시간에 찾으십시오.

이것은 지금까지 내 의사 코드입니다. 가짜 코드는 지금은 충분하지만 나는 이것이 올바르게 작동하지 않는다고 생각하지 않는다. 또한 선형 시간에 작동하지 않는다.

//input: matrix A of win/losses 
//output: list of teams with medals 
set S to an array of length n, with value 0 for all indices //keeps track of number of losses 
for each team: 
    for each game played in the team's row in M: 
     if the team won: 
      increment the opponent’s number of losses in the opponent’s index of S 
     else: 
      increment the team's number of losses in team's index of S 
      if at any point a value in the array S reaches 11, remove that team from the list of teams we consider //so basically ignore all the games they play from hereon out 
    end for loop 
end for loop 
take this new potential list of teams with medals 
iterate through each team's row in M, counting losses  //to check if they lost against any of the teams we removed from the previous for loop 
if losses > 10, remove the team from list 
return final list 

Answer 1

건물, 우리는 O(n)에서이 문제를 해결 할 수 있습니다

는

• (나머지 팀의 추적 할 각 팀
• 에 대한 손실의 수를 추적 즉 10 이하의 사람 손실 - 우리는 나머지 팀에서 가능한 모든 매치업 이상)

• 루프 인덱스의 배열을 유지하고 일정 시간 제거를위한 주변 요소를 교환하여이 작업을 수행 할

  • 은 손실 ​​계수가 10보다 큰 경우, 패배 한 팀
  • 의 손실 수를 증가 나머지 팀에서 팀을 제거
  • 참고 :이 루프는 O(n²)를 취할 나타날 수 있지만, 남아있는 팀의 수는 빠르게 감소 이것만으로도 O(n) 걸릴 수 있습니다.
    손실 계수가 계속 증가하고 손실 계수의 최대 합계가 11*n 인 것을 볼 수 있습니다 (손실 계수가 11이되면 고려에서 제외하고 더 이상 증가시키지 않기 때문에) 따라서이 루프는 많아야 11*n = O(n) 번 실행됩니다.

• 이제 최대 21 개의 팀이 남아 있습니다.
  이미 제거 된 팀에 대한 나머지 팀의 손실을 알지 못하는 경우 (이것이 가장 좋은 경우임을 쉽게 알 수 있음) 나머지 각 팀은 남은 나머지 팀 20 개 중 10 개를 획득했습니다. 22 개 팀은 불가능합니다. 왜냐하면 각 팀은 10 개 이하의 손실을 유지하기 위해 최소한 11/21 게임을 획득해야하기 때문에 손실보다 더 많은 승리를 이끌어 낼 수 있기 때문입니다. 이는 각 게임에 1 개의 승자와 1 개의 패배를 고려하면 불가능합니다.

• 나머지 팀의 경우 해당 팀의 모든 게임을 실행하고 손실 수 (21 루프는 O(n) = O(n))를 계산하고 10 개 이하의 손실로 팀을 산출합니다.

자바 같은 코드 : (읽기 쉽도록 약간 수정 작업 버전)

// returns true if i beat j or false if j beat i 
boolean beat(int i, int j); 
// return the loser in the game between i and j 
int loser(int i, int j); 
// swaps i with the last element in indices and decreases index count, takes O(1) 
void removeIndex(int i); 

// x = indices[y] corresponds to a remaining team x 
int[] indices = new int[n]; 
// number of elements in indices, decreased in removeIndex 
int indicesCount = n; 

---

// initialise our array of indices 
for (int i = 0; i < n; i++) 
    indices[i] = i; 

// initialise our array of losses 
losses = new int[n]; 

// loop over all possible match-ups and eliminate (some) teams with > 10 losses 
for (int a = 0; a < indicesCount;) 
{ 
    for (int b = a+1; losses[indices[a]] <= 10 && b < indicesCount;) 
    { 
     losses[loser(indices[a], indices[b])]++; 

     if (losses[indices[b]] > 10) 
      removeIndex(b); 
     else 
      b++; 
    } 
    if (losses[indices[a]] > 10) 
     removeIndex(a); 
    else 
     a++; 
} 

// find teams with <= 10 losses 
for (int i = 0; i < indicesCount; i++) 
{ 
    int lossCount = 0; 
    for (int j = 0; j < n; j++) 
     if (indices[i] == j) 
      continue; 
     else if (beat(j, indices[i])) 
      lossCount++; 
    if (lossCount <= 10) 
     // output indices[i] 
} 

Live demo.

Answer 2

O (n)에서이를 수행하는 것은 매우 흥미로운 질문입니다.

우리는 10 번 이상을 잃지 않는 팀에만 관심이 있기 때문에 가능할 수도 있습니다.

그러나이 제약 조건에서도 O (n) 알고리즘을 찾고 O (n)임을 증명하는 것은 쉽지 않습니다.

---

첫째, 여기 작동하지 않습니다 무언가이다 :, 곧 우리가 11 손실 발생으로 하나의 요소 일에보고, (하나 개의 팀을 대표하는) 행렬의 각 행을에서, 휴식 이 팀의 나머지 루프를 건너 뛰십시오.

이것은 여전히 ​​O (n^2)입니다. 예를 들어 색인이 낮은 팀이 항상 색인을 생성 한 더 높은 팀에 대해 상실한 경우를 생각해보십시오. 결과 행렬은 더 낮은 삼각형 (대각선 아래에서 우리는 오직 1을 가질 것이고 그 위에는 0만을 가짐)이 될 것입니다.

이 경우 언급 된 알고리즘은 대각선 아래의 모든 요소를 ​​조사해야합니다 (행의 시작 부분에서 모두 1이기 때문에 11 개의 손실에 도달하지 않아 루프가 끊어집니다) . 그래서 적어도 (n^2 - n)/2 요소가 여기에서 조사되었으므로이 접근법은 O (n)에 없습니다.

언급 한 의사 코드는 이보다 나은 시도이지만 O (n)에도 없습니다. 이것은 동일한 반대 예제를 사용하여 볼 수 있습니다. (의사 코드는 때때로 손실을 두 배로 계산하기 때문에 정확하지 않지만 각 팀의 마지막 처리 일치를 나타내는 추가 배열을 사용하여 수정할 수 있습니다.

---

지금 이을 작동하는 것 같다 있다는 생각을 설명 할 것이다. 이것은 올바른 방향 인 것으로 보이지만 아직 해결할 수없는 몇 가지 합병증이 있습니다.

O (n)가되기 위해서는 우리가 보았던 결과를 신중하게 선택해야합니다.

11 개 팀 (L0, L1, ..., L11)을 유지 관리합니다.

• L0은 현재 손실에 대해 인식하지 못하는 팀입니다. 처음에는 모든 팀이이 세트에 있습니다.
• L1은 현재 손실이 1 개임을 알고있는 팀의 집합입니다.
• ...
• L10은 현재 10 개의 손실이 있었다고 알고있는 팀입니다.
• L11은 현재 10 개 이상의 손실을 겪었다는 것을 알고있는 팀의 집합입니다.

처음에는 L0에 모든 팀이 포함되고 나머지 세트는 비어 있습니다.

이제 팀을 L0으로 만듭니다. 일치하는 항목을 조사하고 L1에서 패자를 이동하십시오. 여기에는 n/2 작업이 포함되며, L0 및 n/2 팀의 약 n/2 팀이 L1 ("약 n/2")으로 남게됩니다. n이 이상 할 수도 있기 때문에 한 팀은 지금 짝을 지어야 함). L0에 남아있는 n/2 팀에 대한 프로세스를 반복하고 L1에서 패자를 다시 이동하십시오. 이렇게하려면 n/2/2 = n/4 조작이 필요합니다. L0에 팀이 하나만 남을 때까지 계속하십시오. 이 작업에는 O (n)에 n/2 + n/4 + ... + 1 작업이 필요합니다.

집합 L0에 대한 후보가 하나만 남았으므로 O (n)에서 실제로 손실이 10 개 미만인지 여부를 조사 할 수 있습니다.

분명히 우리는 계속해서 L2를 향해 L1, O (n), L3 등등의 L2 팀으로 이동할 수 있습니다. 대부분의 팀이 L11 (우리가 신경 쓰지 않는 곳) 그들에 대해 더 이상). 그러나 L1에서 팀을 밀어내는 것은 L0만큼 간단하지 않습니다. 이전 단계에서 이미 조사 된 일부 팀이있을 수 있으므로 조심해야합니다. 다음과 같이 qwertyman의 접근 방식에