Let the number of ways to choose R objects from N objects be C(N,R) where the order does not matter, which has the famous closed form N!/(R! * (N-R)!).

Let the number of ways to choose R times from N objects with repetition be S(N,R) where the order of choosing does not matter.

for example if we were to choose from A,B and C four times A,B,C,C is the same as A,C,B,C so we should not count this twice in S(N,R)

S(N,R) turns also to be the number of solutions of

a1 + a2 + … + aN = R, where ai ≥ 0, and R is some non negative integer, simply imagine ai’s as objects the number of time an object is chosen is it’s value, and we choose from those objects R times so the sum would be equals R.

The question is how do we calculate S(N,R) using C(N,R) and this is the only reason for writing this post.

Lets try to solve an instance of the problem

lets assume N = 3 , R = 4

here are some possible solutions

a1 = 0, a2 = 2, a3 = 2

a1 = 1, a2 = 2, a3 = 1

a1 = 2, a2 = 2, a3 = 0

basically we are assigning a value to each variable such that their sum is 4 (youdon’tsay!)

but lets try to interpret this using binary numbers somehow, we can somehow write a solution using a binary number of length N + R – 1 bits as the following

a zero means move on to next variable

a one means increment current variable by 1

we can write a1 = 0, a2 = 2, a3 = 2 as 011011

at the beginning we have a1 = 0, we encounter a 0 so we move on to a2 increment it twice, then move on to a3 increment it twice.

similarly we can write a1 = 1, a2 = 2, a3 = 1 as 101101

since in any solution we need to move on to next variable N-1 times (N variables), and we have to increment all variables R times then from any binary number of N-1 zeroes, R ones we can construct a valid solution.

And if we have a solution we can construct a binary number.

Then there’s a one to one correspondence between the set of solutions and the set of binary numbers with N+R-1 bits where N-1 of them are zeroes and R of them are ones.

Counting those can be easily done using normal combinations so S(N,R) = C(N+R-1,R).

Update: it turns out that this post has a similar content to whats written here at topcoder tutorial :(, so you might want to check it out.

## Archive for the ‘**Mathematics**’ Category

## Combinations with repetitions Leave a comment

## NIM Game Leave a comment

In NIM Game you have n piles each contains ai (0≤i<n) stones, two players alternate turns in each turn a player may remove any positive number of stones from a single pile, the player who cannot make a move loses the game.

Here’s an example n = 1,a0 = 30

First player take 29 stones.

Second player take 1 stone.

First player loses (a0 = 0).

However First player could’ve won if he took 30 stones in the first turn.

Another example n = 2,a0 =3,a1 = 3.

First player take 3 stones from a0.

Second player take 3 stones from a1.

Try playing the game here Stone game reading the next part

If **both** players play **optimally** who will win the game?

We can easily find who will win the game by calculating the bitwise XOR of all pile sizes(NIM sum) if this number is zero then second player wins otherwise first player wins.

So why does this work ? You can spend sometime trying to get some intuition by applying this rule on games with N ≤ 2, however when n grows a mathematical proof works best.

Here’s **a sketch of a proof** (Note: ^ is the bitwise xor)

lets assume we have piles a0,a1,…,an we prove that if a0^a1^…^an = 0 then we are in a losing position, otherwise we are in a winning position.

we prove the following

- A-base case if all piles contain 0 stones then we are in a losing state (0 ^ 0 ^ .. ^ 0 = 0)
- B-being in a losing state means that any move we make will put the opponent in a winning state

proof:

first being in a losing state means

a0 ^ a1 ^ a2 … ^ an = 0

lets assume without the loss of generality that we picked pile a0 to make our move and removed k (0<k≤an) stones from it

we need to prove that

(a0 – k) ^ a1 ^ a2 … ^ an != 0

starting from

a0 ^ a1 ^ a2 … ^ an = 0 xor both sides by a0 ^ (a0 – k)

we get

(a0 – k) ^ a1 ^ a2 … ^ an = a0 ^ (a0 – k)

but a0 ^ (a0 – k) will always be non zero for positive values of k.

- C-being in a wining state means that there exists a move that will put the opponent in a losing state

proof:

assume that

a0 ^ a1 ^ a2 … ^ an = x

lets write x in binary, and look at the highest bit set there exists at least one pile that has that bit set assume without the loss of generality that this pile a0

we need to prove that there’s some POSITIVE k such that

(a0-k) ^ a1 ^ a2 … ^ an = 0

but (a0-k) ^ a1 ^ a2 … ^ an = x ^ a0 ^ (a0 – k)

thus we need to solve x ^ a0 ^ (a0 – k) = 0

xor both sides by a0 – k

we get

x ^ a0 = a0 – k which means

k = a0 – (x ^ a0) and with the assumption that a0 has the highest bit in x means that x ^ a0 is strictly less than a0 thus k is positive and we’re done.

using A,B,C we can use induction to obtain the complete proof.

**Useful links**

**Sample Problems**

Box Game (Not direct NIM but try to get an observation and prove it in a similar way)

## UVA – 11732 – “strcmp()” Anyone? Leave a comment

At first I thought this problem can be solved using trie, which would be an easy way however the simple trie would use a lot of memory 4000 * 1000 * 26 integers or so, Then I had to use another way which would be sorting, using any comparison based sorting algorithm as quick sort or merge sort would also cause Time limit exceeded so instead I used my not-so-efficient radix sort which runs in O(num_words*max_length), then using the sorted words you can easily calculate the result, see the solution for more information.

#include <stdio.h> #include <string.h> #include <stack> using namespace std; typedef long long ll; char words[4005][1005]; int len[4005]; int loc[4005]; int temp[4005]; int word_count; int freq[128]; int charAt(int i, int j) { return (j < len[loc[i]]) ? words[loc[i]][j] : 0; } void count_sort(int j) { memset(freq, 0, sizeof freq); for (int i = 0; i < word_count; i++) freq[charAt(i, j)]++; for (int i = 1; i < 128; i++) freq[i] += freq[i - 1]; for (int i = word_count - 1; i >= 0; i--) temp[--freq[charAt(i, j)]] = loc[i]; memcpy(loc, temp, word_count * 4); } void radix_sort() { int max_len = 0; for (int i = 0; i < word_count; i++) { loc[i] = i; if (len[i] > max_len) max_len = len[i]; } for (int i = max_len - 1; i >= 0; i--) count_sort(i); } int main(int argc, char *argv[]) { int cc = 1; while (scanf("%d", &word_count) && word_count) { getchar(); for (int i = 0; i < word_count; i++) { gets(words[i]); len[i] = strlen(words[i]); } radix_sort(); stack<int> s; s.push(0); s.push(word_count - 1); s.push(0); ll res = 0; memset(freq, 0, sizeof(freq)); while (s.size()) { int j = s.top(); s.pop(); int r = s.top(); s.pop(); int l = s.top(); s.pop(); int all = r - l + 1; for (int i = l; i <= r; i++) freq[charAt(i, j)]++; res += freq[0] * (freq[0] - 1); res += freq[0] * (all - freq[0]); freq[0] = 0; for (int i = l; i <= r; i++) { char c = charAt(i, j); if (!c) continue; if ((i > l && c == charAt(i - 1, j)) || !c) continue; res += freq[c] * (freq[c] - 1); res += freq[c] * (all - freq[c] - i + l); s.push(i); s.push(i + freq[c] - 1); s.push(j + 1); freq[c] = 0; } } printf("Case %d: %lld\n", cc++, res); } return 0; }

## UVA – 11534 – Say Goodbye to Tic-Tac-Toe Leave a comment

grundy numbers + dynamic programming

you can read about grundy numbers here.

#include <iostream> #include <algorithm> #include <vector> #include <string> #include <stdio.h> #include <string.h> #include <stdlib.h> #include <set> using namespace std; char game[105]; int n; int dp[3][3][105]; int grundy(int p, int len, int nx) { if (len == 0) return dp[p][nx][len] = 0; else if (dp[p][nx][len] != -1) return dp[p][nx][len]; set<int> s; for (int k = 1; k <= len; k++) { if (!((k == 1 && p == 1) || (k == len && nx == 1))) s.insert(grundy(p, k - 1, 1) ^ grundy(1, len - k, nx)); if (!((k == 1 && p == 2) || (k == len && nx == 2))) s.insert(grundy(p, k - 1, 2) ^ grundy(2, len - k, nx)); } dp[p][nx][len] = 0; while (s.count(dp[p][nx][len])) dp[p][nx][len]++; return dp[p][nx][len]; } int main(int argc, char **argv) { int tc; scanf("%d", &tc); for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++) for (int k = 0; k < 105; k++) dp[i][j][k] = -1; getchar(); while (tc--) { gets(game); n = strlen(game); int pl = 0; for (int i = 0; i < n; i++) if (game[i] != '.') pl ^= 1; int res = 0; for (int i = 0; i < n; i++) { if (game[i] != '.') continue; int pr = (i - 1 < 0) ? 0 : (game[i - 1] == 'X') ? 1 : 2; int j = i; while (j < n && game[j] == '.') j++; int nx = (j == n) ? 0 : (game[j] == 'X') ? 1 : 2; int len = j - i; res ^= grundy(pr, len, nx); i = j; } if ((!pl && res) || (pl && !res)) puts("Possible."); else puts("Impossible."); } return 0; }

## UVA – 12487 – Midnight Cowboy Leave a comment

Let p(i) be the probability of reaching the inexpensive hotel given that we are currently at the ith node

we have

p(b) = 1

p(c) = 0

p(x) = 1/k * p(n0) + 1/k * p(n1) + 1/k * p(n2) + … + 1/k * p(nk-1)

where n0,n1,..,nk-1 are the neighbors of the node x, so we have a system of equations to solve with variables p(1),p(2),…p(N) and the result is p(a) we can easily solve it using gaussian elimination.

#include <iostream> #include <algorithm> #include <vector> #include <string> #include <stdio.h> #include <string.h> #include <stdlib.h> #include <math.h> using namespace std; double* mat[105]; int indx[105]; double val[105]; int main(int argc, char **argv) { int n, a, b, c; for (int i = 0; i < 105; i++) mat[i] = (double *) malloc(105 * sizeof(double)); while (scanf("%d %d %d %d", &n, &a, &b, &c) == 4) { for (int i = 0; i < n; i++) for (int j = 0; j < n + 1; j++) mat[i][j] = 0; a--; b--; c--; for (int i = 0; i < n - 1; i++) { int x, y; scanf("%d %d", &x, &y); x--; y--; mat[x][y] = 1; mat[y][x] = 1; } for (int i = 0; i < n; i++) { indx[i] = i; double sum = 0; for (int j = 0; j < n; j++) sum += mat[i][j]; for (int j = 0; j < n; j++) mat[i][j] /= sum; mat[i][i] = -1; } for (int i = 0; i < n; i++) mat[c][i] = mat[b][i] = 0; mat[c][c] = 1; mat[b][b] = 1; mat[b][n] = 1; for (int i = 0; i < n - 1; i++) { for (int j = i + 1; j < n; j++) if (fabs(mat[j][i]) > fabs(mat[i][i])) { swap(mat[i], mat[j]); swap(indx[i], indx[j]); } for (int j = i + 1; j < n; j++) { double factor = mat[j][i] / mat[i][i]; for (int k = i; k <= n; k++) mat[j][k] = mat[j][k] - mat[i][k] * factor; } } for (int i = n - 1; i >= 0; i--) { val[i] = mat[i][n]; for (int j = i + 1; j < n; j++) val[i] -= mat[i][j] * val[j]; val[i] /= mat[i][i]; } printf("%.6lf\n", fabs(val[a])); } return 0; }

## UVA – 12396 – Remoteland Leave a comment

A number has is a perfect square if and only if all the powers of it’s prime factors are even.

#include <iostream> #include <algorithm> #include <vector> #include <bitset> #include <stdio.h> using namespace std; #define N 10000005 #define MOD 1000000007 typedef long long ll; bitset<N> parity; int pfactor[N]; int res[N]; void calc() { parity.reset(); for (int i = 0; i < N; i++) pfactor[i] = 0; pfactor[0] = pfactor[1] = -1; for (int i = 2; i * i < N; i++) { if (!pfactor[i]) for (int j = i * i; j < N; j += i) pfactor[j] = i; } for (int i = 2; i < N; i++) if (!pfactor[i]) pfactor[i] = i; res[0] = res[1] = 1; for (int i = 2; i < N; i++) { ll current = res[i - 1]; int k = i; while (pfactor[k] != -1) { parity.flip(pfactor[k]); if (!parity[pfactor[k]]) { current = (current * pfactor[k]) % MOD; current = (current * pfactor[k]) % MOD; } k /= pfactor[k]; } res[i] = (int) current; } } int main() { calc(); while (1) { int n; scanf("%d", &n); if (!n) break; cout << res[n] << endl; } return 0; }

## UVA – 1189 – Find The Multiple 1 comment

Can be solved also using BFS reducing the number of states to MOD only :).

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStream; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class Multiples { static int MOD; static int[][] dp; static int[][] choice; public static int go(int i, int mod) { if (mod == 0) return i; else if (i > 100) return 1 << 25; else if (dp[i][mod] != -1) return dp[i][mod]; int a = go(i + 1, (mod * 10 + 1) % MOD); int b = go(i + 1, (mod * 10 + 0) % MOD); if (a <= b) choice[i][mod] = 1; else choice[i][mod] = 0; return dp[i][mod] = (a < b) ? a : b; } public static void main(String[] args) throws Exception { InputReader in = new InputReader(System.in); while (true) { MOD = in.nextInt(); if (MOD == 0) break; dp = new int[101][MOD]; choice = new int[101][MOD]; for (int i = 0; i < dp.length; i++) Arrays.fill(dp[i], -1); go(1, 1 % MOD); String res = "1"; int i = 1; int m = 1 % MOD; while (m != 0) { res = res + choice[i][m]; m = (m * 10 + choice[i][m]) % MOD; i++; } System.out.println(res); } } static class InputReader { private BufferedReader reader; private StringTokenizer tokenizer; public InputReader(InputStream stream) { reader = new BufferedReader(new InputStreamReader(stream)); tokenizer = null; } public String next() { while (tokenizer == null || !tokenizer.hasMoreTokens()) { try { tokenizer = new StringTokenizer(reader.readLine()); } catch (IOException e) { throw new RuntimeException(e); } } return tokenizer.nextToken(); } public int nextInt() { return Integer.parseInt(next()); } } }