계산

Question

문제 : 우리는 크기 n의 배열을 가지고 우리는 각각의 작업이

1. 가의 수를 감소 할 수있는 가장 K 작업에서 수행 할 수 있어요된다
2. 전체 배열을 임의로 뒤섞습니다.

내 문제는 최종 배열의 예상 반전 수가 최소화되도록 K 작업을 수행하는 것입니다.

제약 :
1 < N < 100
1 < K < N (N-1)/2

내 접근 방식을 testcases의
100 단위 : 나는 동적 프로그래밍에 대해 생각하고 해결책. 마호가니 숫자를 사용하여 n 크기의 배열에서 정확히 e 역변환의 확률을 계산할 수 있습니다. 배열 dp[k+1][1+n(n-1)/2] 배열을 채우십시오. dp[i][j]은 i 작업이 수행 된 후 j 변환이있는 배열의 최소 예상 반전을 나타내고 배열을 사용하여 가능한 모든 반전에 대해 (i+1)<sup>th</sup> 작업의 최소 예상 값을 생성 할 수 있습니다.

이 접근법의 문제점은 C++에서 double의 제한으로 인해 확률이 정확하지 않으며이 알고리즘은 매우 느린 각 테스트 케이스에 대해 O(kn<sup>2</sup>)입니다. 예를를 들어

: 크기 100 = 1.0/factorial(100) ~ 10<sup>-160</sup>의 배열에 어떤 반전이없는의
확률 (I 정밀도의 부족이 여기에 있다고 생각합니다).

정확하고 효율적인 접근 방법이 있다고 생각합니다. 아이디어를 제안 해주십시오.

당신이 K 이동 남아있는 가정 및 k 번째 이동에 당신이 셔플 가정 예상 #inversions을 계산 할 수 있어야가는

Answer 1

귀하의 질문에 대답하기 위해서는 주셔서 감사합니다 그리고 당신은에 결정 셔플을 멈추고 (그리고 나서 1을 뺍니다) 셔플 후에 얼마나 많은 반전을하는지에 따라 셔플을 계속하십시오. 두 번의 이동 만 남았고 현재 # 전환 수가 n (n-1)/4보다 큰 경우 이것은 쉽습니다. 기본적으로 셔플을 시작한 다음 셔플을 중지하고 첫 번째 셔플을 한 후 반전 수가 n (n-1)/4 이하이면 두 번째 이동을 1을 뺀 후 뒤집기 횟수가 n보다 큰 경우 다시 셔플합니다 (n-1)/4가됩니다. 2 개 이상의 움직임에 대해서, k 번째 이동에서 상황이 더 복잡해진다. 왜냐하면 만약 당신이 뒤섞이면 상한 Nk를 역 Nk의 수에 대해 선택할 수 있기 때문이다. 그 중 Nk를 멈추고 1을 빼면이 Nk를 최적화해야한다. 예상되는 반전 횟수는 전체적으로 최소화됩니다. 분명히 k가 더 크다면, Nk는 더 작게 선택되어야하지만, 질문은 얼마나 많은가에 달려있다. 그 Nk (각 k에 대해)를 계산할 수 있다면, 당신은 당신의 문제를 풀 것입니다.

내 직감은 당신이 모든 k = 1,2, ...에 대해 Nk를 풀 수 있다는 것입니다., K는 근본적으로 O (nK) 시간에 재귀 적 공식을 사용합니다. 나는 세부 사항을 해결하면 업데이 트됩니다. 사실이라면, 본질적으로 O (nK) 시간에서 예상 된 역전 횟수를 풀 수 있다는 것을 의미합니다.