Expectation : Random Sort Riddles.

Meaning:  In probability theory, the expected value (or expectation, or mean, or the first moment) of a random variable is the weighted average of all possible values that this random variable can take on.

Suppose random variable ‘X‘ can take value x1 with probability p1, value x2 with probability p2, and so on, up to value xk with probability pk. Then the expectation of this random variable ‘X’ is defined as:

E[X] = x1*p1 + x2*p2 + x3*p3 + ……………. + xk*pk;

Example : For the six faced dice with faces, 1, 2, 3, 4, 5, 6 : the expectation is: (assuming equal probability of getting all faces).

E[X] = 1* 1/6 + 2 * 1/6 + 3 * 1/6 + 4 * 1/6 + 5 * 1/6 + 6 * 1/6

E[X] = 3.5

Thus the expectation is 3.5.

Problem Section :   Random Sort Riddles using Expectation.

After having a bit of theory of expectation, we will now solve one very tricky riddles using expectation and Dynamic Programming.

Problem Statement:  Problem description can be found at:

http://community.topcoder.com/stat?c=problem_statement&pm=8590&rd=12174&rm=&cr=7452866

Don’t go for navie recursive code. It will for sure exceed the limit of 2second. So think of memoisation technique.

Here below is the implementation for the same using Dynamic Programming (recursion + memoisation approach):

Map <int[], Double> map = new TreeMap <int[], Double>(new Comparator<int[]>()
{
    public int compare(int[] p1, int[] p2)
    {
        for(int i = 0; i < p1.length; i++)
        {
            if(p1[i] != p2[i]) return p1[i] - p2[i];
        }
        return 0;
    }
});
public double solve(int[] p)
{
    double deno = 0, num = 0;
    int[] arr = new int[p.length];
    if(map.containsKey(p)) return map.get(p);
    for(int i = 0; i < p.length; i++)
    {
        for(int j = i + 1; j < p.length; j++)
        {
            if(p[i] > p[j])
            {
                arr = (int[])p.clone();
                int temp =p[i]; p[i] = p[j]; p[j] = temp;

                num += 1 + solve(p);
                deno++;
                temp =p[i]; p[i] = p[j]; p[j] = temp;
            }
        }
    }
    if(deno == 0) num = 0;
    else num /= deno;
    map.put(arr, num);
    return num;
}
public double getExpected(int[] p)
{
 return solve(p);
}

FieldDiagrams : count total number of FIELD diagrams.

Complete description about the problem can be found at:

http://community.topcoder.com/stat?c=problem_statement&pm=8776&rd=12173&rm=&cr=10574855

The most important aspect of this problem is how do u calculate those many possible field diagrams. One way is using recursion. But is that feasible. Here, I have come up with Dynamic Programming approach to solve this riddle.

Below is the implementation of this problem in Java.

private long[][] dp;
public long countDiagrams(int N)
{
    dp = new long[N + 1][N + 1];
    dp[0][0] = 1;
    for(int i = 1; i <= N; i++)
    {
        long sum = 0;
        for(int j = 0; j <= i; j++)
        {
            sum += dp[i - 1][j];
            dp[i][j] = sum;
        }
    }
    long res = 0;
    for(int i = 0; i <= N; i++) res += dp[N][i];
    return res - 1;
}

StrongPrimePower

Problem Statement: You are given number in the range up to 10 ^ 18. Can this number be expressed as P to the power q. ie. P ^q , where P is prime number and q is greater than 1.

Complete problem definition can be found in this site.

http://community.topcoder.com/stat?c=problem_statement&pm=8763

Constraints: This number can be up to 10 ^ 18. So rule out brute force approach. Even if you use improved mathematics, how will you keep track of overflow. This is the most important aspect of this problem.

Here below is the solution for this problem, but better first think yourself. And for overflow case(to handle for large numbers refer my code).

Method 1:

Using BigInteger Class of Java

public boolean isPrime(int n)
{
    if(n == 2) return true;
    if(n % 2 == 0) return false;
    for(int i = 3; i * i <= n; i += 2)
        if(n % i == 0) return false;
    return n > 1;
}
public int[] baseAndExponent(String n)
{

    int[] res = new int[0];
    long n1 = Long.parseLong(n);

    long sqrt = (long)Math.sqrt(n1 * 1.);
    if((long)(sqrt * sqrt) == n1 && isPrime((int)sqrt))
    {
        res = new int[2]; res[0] = (int)sqrt; res[1] = 2;
        return res;
    }

    long cbrt = (long)Math.cbrt(n1);
    if((long)(cbrt * cbrt * cbrt) == n1 && isPrime((int)cbrt))
    {
        res = new int[2]; res[0] = (int)cbrt; res[1] = 3;
        return res;
    }

    BigInteger init = new BigInteger(n);
    outer:
    for(int i = 2; i <= 100000; i++)
    {
        for(int pow = 4; pow <= 63; pow++)
        {
            BigInteger ans = BigInteger.valueOf(i).pow(pow);
            if(ans.compareTo(init) > 0) break;
            if(ans.equals(init) && BigInteger.valueOf(i).isProbablePrime(3))
            {
                res = new int[2];
                res[0] = i; res[1] = pow;
                break outer;
            }
        }
    }
    return res;
}

Method 2

Using Advanced Mathematics concepts(trick to prevent overflow)

The code below is written in C++.

typedef long long LL;
LL toLL(string s)
{
    stringstream ss;
    ss << s;
    LL n;
    ss >> n;
    return n;
}

bool isPrime(int n)
{
    if(n == 2) return true;
    if(n % 2 == 0) return false;
    for(int i = 3; i * i <= n; i += 2)
        if(n % i == 0) return false;
    return n > 1;
}

vector <int> baseAndExponent(string s)
{
    LL n = toLL(s);
    vector <int> v;
    for(int i = 2; i <= 64; i++)
    {
       LL base = (int)pow(n, 1. / i);
       base = max((LL)2, (LL)(base - 1));
       for(int a = base; a <= base + 2; a++)
       {
           LL N = n; int cnt = 0;
           while(N % a == 0)
           {
               N /= a;
               cnt++;
           }
          if(N == 1 && cnt == i && isPrime(a))
          {
              v.push_back(a);
              v.push_back(i);
              goto there;
          }
       }
    }
    there:
    return v;
}

Find Corporation Salary

The problem statement can be found at :

http://community.topcoder.com/stat?c=problem_statement&pm=9824&rd=12179&rm=&cr=19849563

It expects you to find the salary of an corporation but using the efficient Graph Theory Technique. Here below I am explaining how to solve to using DFS Graph concepts.

long[] dp;
String[] s;
public long solve(int source)
{
    if(dp > 0) return dp;
    for(int i = 0; i < s.length; i++) if(s.charAt(i) == 'Y') dp = dp + solve(i);
    if(dp == 0) dp = 1;
    return dp;
}
public long totalSalary(String[] s)
{
    dp = new long[100];
    this.s = s;
    long ans = 0;
    for(int i = 0; i < s.length; i++) ans += solve(i);
    return ans;
}