**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[

**] % Y == 0 at line 30 during contest.**

*i*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:
```

I am currently using http://codeformatter.blogspot.com/

ReplyDeleteto format my source code.

I know my source code looks a bit ugly in the current format, so if you know a website that can format my code better, please let me know.

Thanks a million in advance.

Maybe you could use a Javascript code prettifier? http://code.google.com/p/google-code-prettify/

ReplyDeleteThx for the suggestion :-)

DeleteY <= max(A,B)

ReplyDeleteDidn't understand where you got that constraint from. And didn't understand AT ALL how this happened:

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