TopCoder SRM 508

I solved Easy and Medium. Since I'm not good at geometry and flow, I wasn't able to solve Hard though I had 40 minutes to try it. Anyway, my rating increased because I've solved Medium not too slow.

Rating: 2269 -> 2318 (+49)

Link to TopCoder (login required)

250 DivideAndShift

I came up with an idea that dividing operations and shifting operations can be separated as soon as I read the statement. My solution is: trying all patterns of dividing operations and then performing shifting operations to achieve the goal.

Solution in C# (in the contest)

using System; 
using System.Text; 
using System.Text.RegularExpressions; 
using System.Collections; 
using System.Collections.Generic; 

public class DivideAndShift { 
    public int getLeast(int N, int M) { 
        int res = int.MaxValue; 
        int P = 0, T = N; 
        for (int i = 2; i * i <= T; ++i) 
        { 
            while (T % i == 0) 
            { 
                P++; 
                T /= i; 
            } 
        } 
        if (T > 1) P++; 
        M--; 
        for (int i = 1; i <= N; ++i) 
        { 
            if (N % i == 0) 
            { 
                int cnt = 0; 
                int p = 0, t = i; 
                for (int j = 2; j * j <= t; ++j) 
                { 
                    while (t % j == 0) 
                    { 
                        p++; 
                        t /= j; 
                    } 
                } 
                if (t > 1) p++; 
                cnt = P - p; 
                cnt += Math.Min(M % i, i - M % i); 
                res = Math.Min(res, cnt); 
            } 
        } 
        return res; 
    } 
} 

500 YetAnotherORProblem

This problem can be solved by bit DP. The state is: dp[u][b] = the number of sequences when we determined upper b bits of all elements of A, and A[i] might be larger than R[i] if u & (1<<i) != 0.

My implementation is memoized recursion.

Solution in C# (in the contest)

using System; 
using System.Text; 
using System.Text.RegularExpressions; 
using System.Collections; 
using System.Collections.Generic; 

public class YetAnotherORProblem 
{ 
    int N; 
    int[,] dp; 
    bool[,] done; 
    long[] R; 
    public int calc(int u, int b) 
    { 
        if (b < 0) 
            return 1; 
        if (done[u, b]) 
            return dp[u, b]; 
        dp[u, b] = 0; 
        for (int i = 0; i < N; ++i) 
        { 
            if ((u & (1 << i)) == 0 || ((ulong)R[i] & (1ul << b)) != 0) 
            { 
                int v = u; 
                for (int j = 0; j < N; ++j) 
                { 
                    if (i == j) 
                        continue; 
                    if (((ulong)R[j] & (1ul << b)) != 0) 
                        v &= ~(1 << j); 
                } 
                dp[u, b] = (dp[u, b] + calc(v, b - 1)) % 1000000009; 
            } 
        } 
        int nu = u; 
        for (int j = 0; j < N; ++j) 
        { 
            if (((ulong)R[j] & (1ul << b)) != 0) 
                nu &= ~(1 << j); 
        } 
        dp[u, b] = (dp[u, b] + calc(nu, b - 1)) % 1000000009; 
        done[u, b] = true; 
        return dp[u, b]; 
    } 

    public int countSequences(long[] R_) 
    { 
        N = R_.Length; 
        dp = new int[1 << N, 64]; 
        done = new bool[1 << N, 64]; 
        R = R_; 
        return calc((1 << N) - 1, 63); 
    } 
}