CodeJam 2011 : Gorosort의 해결책은 무엇입니까?

Question

문제는 여기에서 찾을 수 있습니다 :

3 1 2

그래서 예를 들면 다음과 같습니다
answer = no. of elements that are not in the correct position

, 나는이 배열을 정렬 할 수 있다고 가정하는 이유
http://code.google.com/codejam/contest/dashboard?c=975485#s=p3

이해가 안 다음과 같이 생각하십시오.

Array: 3 1 2 
1st: freeze 2 to sort 1 (take 2 hits) 
Array: 1 3 2 
2nd: freeze 1 to sort 2 and 3 (take another 2 hits)

따라서 내 대답은 4이지만 올바른 대답은 3입니다.
누구든지 내게이 문제를 명확하게 알려줄 수 있습니까?

Answer 1

올바르게 설명 된 솔루션은 올바르게 정렬 된 항목 만 보유하는 것입니다. 3 개의 정렬되지 않은 요소에 대해이 작업을 수행하면 첫 번째 시도 후에 1/6의 확률로 모든 항목을 정렬합니다 (즉, 한 번 완료되면 완료됩니다). 3/6으로 항목 중 하나를 정렬하면 평균 2 개의 히트가 필요합니다.) 그리고 2/6의 확률로 아무도 정렬되지 않습니다. (그리고 시작했을 때와 같은 수의 히스토그램이 필요합니다.) 이렇게하면 간단한 반복적 인 수식을 얻을 수 있습니다. 평가 후 평균적으로 3 개의 정렬되지 않은 항목을 정렬하려면 3 개의 안타가 필요합니다.

귀하의 전략이 잘못된 결과를 제공한다는 사실은 그것이 최상의 전략이 아니라는 것을 의미합니다.

비록 그 솔루션이 유일한 결과는 아니지만, 가장 간단한 것입니다. 또 다른 가능한 방법은 정렬 된 모든 항목 (있는 경우)과 정렬되지 않은 항목 중 일부를 보유하는 것입니다. 그러나 보유하지 않은 모든 항목은 보유하고있는 항목을 제외시키지 않고 올바른 위치에 도달 할 수 있어야합니다. 즉, 순열로 cycle(s)을 형성해야합니다.

는 다음과 같은 예를 생각해 구글의 솔루션은 평균 5 안타에 걸릴 있도록

는

1 3 2 5 6 4 

, 5 개 분류되지 않은 항목이 있습니다.

1이 정렬되어 있으므로이를 보유해야합니다. 5, 6 및 4도 보유하면 나머지 항목 (3 및 2)은 올바른 위치에 도달 할 수 있습니다. 우리가 해낼 때 평균 2 회 안타를 칠 것입니다. 이제 3 개의 정렬되지 않은 항목이 있으며 평균 3 개의 정렬로 정렬 할 수 있습니다. (우리는 하나의 사이클을 형성하기 때문에 모든 것을 무료로 유지해야합니다.) 따라서이 접근법은 더 복잡하지만 원래의 것보다 빠릅니다.

Answer 2

필자는 증거를 이해하는 데 시간을 투자하지 않았지만, Comp, 한순간에 나는 differnt 'cycles'에 대한 상황을 시뮬레이션 해 보았습니다. 무작위로 2의주기 동안 순열을 생성했습니다 [2,1]. 그것은 100000 시간을 나누어 평균을 구하십시오. 그것은 대략 2입니다.

그래서 나는 3 [2,3,1]의주기를 시도했습니다. 랜덤 치환, 올바른 위치 확인, 동결, 남은 임의 치환 (더 큰 사이클에서 방금 이전 시뮬레이션의 사이클 결과를 추가했습니다. 즉, 그 시점에서 2의 사이클에 2.00을 추가했습니다).

나는 컴피 중에 많은 것을 시도했기 때문에 엉망이 될 수 있었지만, 내 시뮬레이션은 그 증명이 제시 할 수있는 숫자와 다른 숫자를 주었다.

주기 3 - 3.5 (3과 반대) 주기 4 - 5.25 (4와 반대) 주기 5 - 6.4 ... (5와 반대)

???

이상한가요? 그 번호를 가지고 나는 모든 사이클을 세트에서 찾았고 발견 된 숫자를 더했습니다. 분명히 그것은 내 다른 시도처럼 잘못되었습니다. 결과의

Answer 3

증명 :

이 E[n] 보자는 순서가 n 개의 숫자 히트 예상되는 숫자입니다.

n은> = 2 E[n] 하나 더한 친 후 가중 된 수의 합 경우

 `E[n] = 1+(E[1]*count[1]+E[2]*count[2]+...+E[n] * count[n])/n!` 

이제 count[k]을 계산한다. 그것은

• C (N, k)를, n은 K 번호 복용 방법의 수의 곱이다
• (K-1)! 없음에 노출되지 않도록 K 개의 숫자를 배열하는 방법의 수는 정확한 위치
• (NK) !, 방법의 수나 배치는 다른 원소 그래서 count[k] = C(n,k)*(k-1)!*(n-k)!=n!/k

.

그럼 우리가 n에 대한

E[n] = 1+E[1]/1+E[2]/2+...+E[n-1]/(n-1)+E[n]/n (a) 
E[n-1] = 1+E[1]/1+E[2]/2+...+E[n-1]/(n-1)   (b) 
E[n]-E[n-1] = E[n]/n        (a)-(b) 
E[n]/n = E[n-1]/(n-1)       (rearranging) 
E[n-1]/(n-1) = E[n-2]/(n-2)     (substituting) 
... 
E[3]/3 = E[2]/2        (substituting) 
E[2]/2 = 1         (1/2+1/4+1/8+...) 

그래서 E[n]=n를 작성할 수> = 2 증명

그래서이 문제에 대한 답은 숫자 만 계산하지 않습니다 (BTW E[1]은 정의되지 count[1]=0) 그들의 오른쪽 위치에.

나는이 라운드의 해결책을 http://www.chaoswork.com/blog에 작성했지만이 블로그는 중국어로 작성되었으므로이 글에서는 영어로 아이디어를 다시 게시합니다.

Answer 4

는 여기에 "3 일 2"할 수있는 방법 :

은 3 개 요소를 무작위로 다시 셔플하자, 아무것도 동결하지 마십시오.

1 3 2 

3 2 1 

2 1 3 

: 올바른 장소에서 한 남자와이 잘못된 사람과 결말의

1 2 3 

3/6 기회 :

당신은 한 번에 문제를 해결 1/6 기회가 여전히 잘못된 3 사람들과 함께 결말의

2/6 기회 :

2 3 1 

3 1 2 

이 벗어나 려 고려 3-bad 상태는 확률 2/3의 동전 뒤집기입니다. 성공하려면 평균 얼마나 걸리나요? 이것은 기하학적 분포 (Google)이며, 따라서 평균적으로 3/2 (1.5) 플립이 필요합니다. 이제 당신이 나쁜 상태에서 빠져 나왔다고 가정하면 해결 될 확률 1/4와 2 명의 잘못된 사람들이있는 확률 3/4입니다. 따라서 평균적으로 나쁜 상태를 벗어나면 0 * 1/4 + 2 * 3/4 ​​단계가됩니다.

(상기 화학식에있어서를 "순서가 2 사람을 해결하기 위해 2 단계"= P와 기하학적 분포의 기대 값의 다른 응용 프로그램에서 입수 할 수있는 1/2).