You are viewing a single comment's thread. Return to all comments →
I have solved it and passed all tests. Here is my draft way, which can be understood only for those who really tried to solve it:
/*max 2*sum(Pi-Pi^2)*i ---> 2*sum(0.5-Pi)^2*i,i=K+1....N * F(K,N) = (N-K)*(N+K+1)/4 - 2*((K+1)*X[1]^2-...-N*X[N-K]^2) < 2*N-1 * X[1]+-...+X[N-K] = (N-K)/2 - 1, X[i] < 0.5 * X[N-K] = X[N-K](X1,X2,...X[N-1]), DX[N-K]/DXi = -1 * DF/DXi = -4*(K+i)*X[i] + 4*N*X[N-K] = 0, X[i] = N*X[N-K]/(K+i) < 0.5 * X[1]+-...+X[N-K] = X[N-K]*N*(1/(K+1)+...+1/N) = X[N-K]*N*(H(N)-H(K)) = (N-K)/2 - 1 * =>0.5 > X[1] = N*X[N-K]/(K+1) = ((N-K)/2 - 1)/((1/(K+1)+...+1/N)*(K+1)) * minK= K(N) * For BIG K,N find minK for given N: * (N-K-2)/(K+1) <= H(N)-H(K) =~ ln(N/K) + 0.5/N - 0.5/K - 1/12*(1/N^2-1/K^2) * (N-1-(K+1))/(K+1) <= H(N)-H(K+1)+1/(K+2),L=K+1 * (N-1-L)/L <= H(N)-H(L)+1/(L+1) * * N=L+a*L, 0 < a <<1 * ln(N/L) = ln(1+a) ~ = a-a^2/2 * a - 1/L ~= a-a^2/2 + 1/(L+1) * a ~= 2/sqrt(L) * N ~= L+2*sqrt(L) * N+1 ~= (sqrt(L)+1)^2 * L ~= (sqrt(N+1) - 1)^2 = N+2-2*sqrt(N+1) * * F(K,N) = (N-K)*(N-K+1)/4 - 2*((K+1)*X[1]^2+...+N*X[N-K]^2) = * (N-K)*(N+K+1)/4 - 2*(N^2*X[N-K]^2/(K+1)+...+N*X[N-K]^2) = * (N-K)*(N+K+1)/4 - 2*N^2*X[N-K]^2*(1/(K+1)+...+1/N) = * (N-K)*(N+K+1)/4 - 2*N^2*X[N-K]^2*(H(N)-H(K)) = * (N-K)*(N+K+1)/4 - N*X[N-K]*(N-K-2) * check: (N-K)*(N+K+1)/4 - (K+1)*(N-K-2)/2 -> 2*N-1? * (a*L+1)*(a*L+2*L) - 2*(K+1)*(N-K-2) -> 8*N - 4 * (a*L+1)*(a+2)*L - 2*L*(a*L-1) -> 8*L*(1+a) - 4 * (a*L+1)*(a+2) - 2*(a*L-1) -> 8*(1+a) - 4/L * 8+a -> 8+8*a - 4/L ----> ok, as both sides-->8 */
Seems like cookies are disabled on this browser, please enable them to open this website
Random Number Generator
You are viewing a single comment's thread. Return to all comments →
I have solved it and passed all tests. Here is my draft way, which can be understood only for those who really tried to solve it: