TopCoder SRM 537 DIV1 and DIV2

DIV 1

250 - KingXNewCurrency

Approach
It's a math problem.
A = X * a + Y * b
B = X * c + Y * d
where  a,b,c,d are non-negative integers.
In other words, A and B are integers that can be made by adding multiples of X and Y.

Then we can rewrite above formula as follow
A = X * a + Y * b
Y*b = A - X * a

B  = X * c + Y * d
Y * d = B -  X * c

Let's define
As = positive values of (A - X*a) where 0 <= a
Bs = positive values of (B - Y*c) where 0 <= c
Then we are looking for integers Y that satisfy
As[i] % Y == 0 and Bs[j] % Y == 0

Constraint (1 <= A,B <= 200) is small enough to try all possible values of Y

Source code

1:  class KingXNewCurrency {  
2:  public:  
3:       int howMany(int, int, int);  
4:  };  
5:    
6:    
7:  int KingXNewCurrency::howMany(int A, int B, int X) {  
8:         
9:    if(A % X == 0 && B % X == 0)  
10:      return -1;  
11:      
12:    int ans = 0;  
13:    vector<int> As;  
14:    vector<int> Bs;  
15:      
16:    int k = 0;  
17:    while( A - X*k >= 0)  
18:      As.push_back(A - X * (k++));  
19:      
20:    k = 0;  
21:    while(B - X*k >= 0)  
22:      Bs.push_back(B - X * (k++));  
23:      
24:    for(int Y=1; Y <= max(A,B); Y++)  
25:    {  
26:      if(X == Y) continue;  
27:      bool found = false;  
28:      for(int i=0; !found && i < As.size(); i++)  
29:        for(int j=0; !found && j < Bs.size(); j++)  
30:          if(As[i] % Y == 0 && Bs[j] % Y == 0)  
31:          {  
32:            ans++;  
33:            found = true;  
34:          }  
35:    }  
36:      
37:    return ans;  
38:  }  
39:    

Note:
I actually failed system test for this problem because I wrote
As[i] % Y == 0 && Bs[i] % Y == 0  at line 30 during contest.
Stupid mistake. I know.




500 - KingXMagicSpells

Note : I couldn't solve this problem on my own, so I searched the internet, and found a blog explaining this problem very well. It is written by vexorian, and here's the link to his blog : vexorian.blogspot.com 

I made minor modifications to variables names and code structure to help me better understand his algorithm, but I didn't make any major changes to his algorithm. So I am basically paraphrasing vexorian's algorithm here.
Feel free to go to vexorian's blog, and only come back here if you are still confused after reading vexorian's blog and need MORE DETAILS.

Approach

Each day, there are two possible operations
1) XOR  operation caused by SpellOne
2) SWAP operation caused by SpellTwo

In other words, there are 2 possible outcomes every day.
There are K days, and 1 <= K <= 50
So there can be 2^50 = (2^10)^5 = (10^3)^5 = 10^15  possible outcomes at most.
10^15 tells us that trying all possible outcomes will undoubtedly go over time limit.

Note that the result of each day (number of ducks at room 0 on the current day ) depends on the previous day.  It is a counting problem with a recurrence, which means it is a dp-problem.

The tricky part of this problem is XOR operation. My initial reaction when I first saw this problem was to define dp as
dp[i][j] = expected number of ducks at room i after j operations.
And recurrence is
dp[i][j] = 0.5 * (spellOne[i] ^ dp[i][j-1]) + 0.5 * (dp[ prev[i] ][j-1])
where prev[i] = previous position of room i before a SWAP operation.


However, I failed miserably because XOR operation can be performed only between integers. Since dp[i][j] stores a double, XOR operation cannot be used in a recurrence.

The solution to the problem caused by XOR is to redefine dp.
dp[bit][bitPos][roomPos][ops]
= probability of the number of ducks in "roomPos" room having "bitPos"th bit set to "bit" after "ops" number of operations.

Recurrence
dp[bit][bitPos][roomPos][ops]
= 0.5 * dp[( bit ^ (spellOne[roomPos]>>bitPos) & 1)][bitPos][roomPos][ops-1]
+ 0.5 * dp[bit][bitPos][prev[roomPos][ops-1]

Base case
if(ops == 0)
{
      if( (ducks[roomPos] >> bitPos) & 1) == bit ) return 1.0;
      else return 0.0;
}

Our answer is
1 * probability of 0th bit of duck[0] being 1 after K operations
+ 2 * probability of 1th bit of duck[0] being 1 after K operations
+ 4 * probability of 1th bit of duck[0] being 1 after K operations
+ 8 * probability of 1th bit of duck[0] being 1 after K operations
...
==> sum of (1<<bitPos * dp[1][bitPos][0][K] where 0 <= bitPos <= 30
The constraint for bitPos came from here.
0 <= ducks[i] <= 10^9
10^9 = (10^3)^3 = (2^10)^3 = 2^30
So the leftmost bit we have to check is at 30th position.


Source Code

1:  class KingXMagicSpells {  
2:  public:  
3:       double expectedNumber(vector <int>, vector <int>, vector <int>, int);  
4:  };  
5:    
6:  const int maxN = 51;  
7:  const int maxDig = 31;  
8:  vector<int> s1;  
9:  vector<int> s2;  
10:  vector<int> dk;  
11:    
12:  int prev[maxN]; //prev[i] = previous position of room i before a swap  
13:  double dp[2][maxDig][maxN][maxN];  
14:  bool chk[2][maxDig][maxN][maxN];  
15:    
16:  double rec(int,int,int,int);  
17:    
18:  double KingXMagicSpells::expectedNumber(vector <int> ducks, vector <int> spellOne, vector <int> spellTwo, int K) {  
19:    s1 = spellOne; //XOR operation  
20:    s2 = spellTwo; //swap operation  
21:    dk = ducks;  
22:    int N = s1.size();  
23:      
24:    for(int i=0; i < N; i++)  
25:      prev[ s2[i] ] = i;  
26:      
27:    memset(chk, false, sizeof(chk));  
28:      
29:    double ans = 0.0;  
30:    for(int bitPos=0; bitPos < maxDig; bitPos++)  
31:      ans += (1<<bitPos) * rec(1, bitPos, 0, K);  
32:      
33:    return ans;  
34:  }  
35:    
36:  double rec(int bit, int bitPos, int roomPos, int ops)  
37:  {  
38:    double& res = dp[bit][bitPos][roomPos][ops];  
39:      
40:    if(chk[bit][bitPos][roomPos][ops])  
41:      return res;  
42:      
43:    res = 0.0;  
44:    chk[bit][bitPos][roomPos][ops] = true;  
45:      
46:    if(ops == 0) //end of operation  
47:    {  
48:      if( ((dk[roomPos]>>bitPos) & 1) == bit ) res = 1.0;  
49:      return res;  
50:    }  
51:      
52:    //XOR : spellOne  
53:    res += 0.5 * rec( bit ^ ((s1[roomPos]>>bitPos) & 1), bitPos, roomPos, ops - 1);  
54:      
55:    //permutation : spellTwo  
56:    res += 0.5 * rec(bit, bitPos, prev[roomPos], ops - 1);  
57:      
58:    return res;  
59:  }  

DIV 2


250 - KingXNewBaby

Approach
We do exactly what the problem asks us.
1. Check if the name is of length 8.
2. Check if the name contains exactly two vowels.
3. Check if the two vowels are the same.

Source Code

1:    
2:  class KingXNewBaby {  
3:  public:  
4:       string isValid(string);  
5:  };  
6:    
7:  bool isVowel(char);  
8:    
9:  string KingXNewBaby::isValid(string name) {  
10:       int N = name.size();  
11:      
12:    if(N != 8) return "NO";  
13:      
14:    char vowels[8];  
15:    int sz = 0;  
16:    for(int i=0; i < N; i++)  
17:      if(isVowel(name[i]))  
18:        vowels[sz++] = name[i];  
19:      
20:    if( sz == 2 && vowels[0] == vowels[1])  
21:      return "YES";  
22:    return "NO";  
23:  }  
24:    
25:  bool isVowel(char ch)  
26:  {  
27:    string str = "aeiou";  
28:    for(int i=0; i < 5; i++)  
29:      if(ch == str[i]) return true;  
30:    return false;  
31:  }  
32:    

500 - KingXNewCurrency
It is the same problem as DIV 1 250. Please go to DIV1 - 250 at the beginning of this blog.



1000 - PrinceXToastbook

I will shortly post a full approach for this problem.
I can tell you right now that this requires
1) permutation
2) combination

In other words, this is a math problem, and it can be solved in O(n) time.

Source Code

1:  class PrinceXToastbook {  
2:  public:  
3:       double eat(vector <int>);  
4:  };  
5:    
6:  vector<int> pre;  
7:  vector<int> topSort(50, -1);  
8:    
9:  ll pascal[51][51];  
10:  int N;  
11:    
12:  /*  
13:   numPrev(i,j) = number of books to be read (prerequisite books)  
14:   to understand book i.  
15:   j is a bitmask representing books read so far.  
16:   */  
17:  int numPrev(int, ll);   
18:  void combiPascal(); //pascal's table for combination  
19:    
20:  double PrinceXToastbook::eat(vector <int> prerequisite) {  
21:    pre = prerequisite;  
22:       N = pre.size();  
23:      
24:    combiPascal();  
25:      
26:    double permu[51]; //permutation  
27:    permu[0] = permu[1] = 1.0;  
28:    for(double i = 2.0; i <= 50; i+=1.0)  
29:      permu[int(i)] = i * permu[int(i-1)];  
30:      
31:    double ans = 0;  
32:      
33:    REP(i,0,N)  
34:    {  
35:      topSort[i] = numPrev(i, 0ll);  
36:      if(topSort[i] >= N) continue; //cycle exists  
37:      ans += double(pascal[N][topSort[i]+1]) * permu[N-topSort[i]-1];  
38:    }  
39:      
40:    return ans/permu[N];  
41:  }  
42:    
43:  int numPrev(int idx, ll visited)  
44:  {  
45:    int& res = topSort[idx];  
46:    if(res != -1) return res;  
47:      
48:    if(pre[idx] == -1)  
49:      return 0;  
50:      
51:    if( ((visited>>idx) & 1) == 1) //cycle found  
52:      return N;  
53:      
54:    visited += (1ll<<idx);  
55:    res = 1 + numPrev(pre[idx], visited);  
56:      
57:    return res;  
58:  }  
59:    
60:  //makes pascal table. It can be used to get a combination.  
61:  //For example, pascal[10][5] is the same as number of ways to pick 5 items out of 10 items  
62:  void combiPascal()  
63:  {  
64:       memset(pascal, 0, sizeof(pascal));  
65:         
66:       pascal[0][0] = 1;  
67:       for(int i=0; i <=50; i++)  
68:            pascal[i][0] = 1;  
69:         
70:       for(int i=1; i <= 50; i++)  
71:            for(int j=1; j <= 50; j++)  
72:                 pascal[i][j] = pascal[i-1][j-1] + pascal[i-1][j];  
73:  }  
74: