We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Mathematics
  3. Probability
  4. Random Number Generator
  5. Discussions

Random Number Generator

Sort by

recency

|

6 Discussions

|

  • henry_scher_job
     + 0 comments

    The editorial is reasonably useful, but it's possible to find k in O(1) time (with O(max N) preprocessing, as in the editorial), giving an overall time of O(T + N) using a bit more math. The pattern isn't too hard to see, once you look for it.

  • emreozturk1280
     + 0 comments

    Hi everyone, I can't understand this problem. Could you explanation this problem?

  • qiangqiangli1993
     + 0 comments

    Java Import Random Number Generation, more go here

    // import java.util.Random;

public static void main(String[] args)
{    
　　Random r = new Random(1);
　　for(int i=0 ; i<5 ;  i++)
　　{
　　    // [0, 100)
　　　　int ran1 = r.nextInt(100);
　　　　System.out.println(ran1);
　　}
}

  • celicom
     + 0 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
 */

  • Marco_L_T
     + 0 comments

    Who could please tell me the solution to this problem? Maybe I'm too weak at mathematics ：）