A Fun Problem - Math

# Problem Statement JATC's math teacher always gives the class some interesting math problems so that they don't get bored. Today the problem is as follows. Given an integer $n$, you can perform the following operations zero or more times: mul $x$: multiplies $n$ by $x$ (where $x$ is an arbitrary positive integer). sqrt: replaces $n$ with $sqrt(n)$ (to apply this operation, $sqrt(n)$ must be an integer). You can perform these operations as many times as you like. What is the minimum value of 𝑛, that can be achieved and what is the minimum number of operations, to achieve that minimum value? Apparently, no one in the class knows the answer to this problem, maybe you can help them? Input The only line of the input contains a single integer $n$ $(1 <= 𝑛 <= 10^6)$ — the initial number. Output Print two integers: the minimum integer 𝑛 that can be achieved using the described operations and the minimum number of operations required. # Solution We can prime-factorize $n$ and get $p_1^{a_1} * p_2^{a_2} * ... * p_k^{a_k}$. At the end, we won't be able to remove the prime factors so the answer must be in the form of $p_1 * p_2 * ... * p_k$. If $a_i$ is a power of 2, then we can apply sqrt operation and make $a_n := \frac{a_n}{2}$. Otherwise, we can use the first operation to make all $a_i$ equal to $2 ^ X$. Therefore, the number of operations is either $X$ or $X + 1$. ```cpp vector<long long> factorize(int x) { vector<long long> res; for (int y = 2; y * y <= x; y++) { if (x % y) continue; while(x % y == 0) { res.push_back(y); x /= y; } } if (x > 1) res.push_back(x); return res; } void solve() { int n; cin >> n; vector<long long> f = factorize(n); map<long long , long long > m; for (auto x : f) m[x]++; long long mx = 0; for (auto x : m) mx = max(mx, x.second); long long b = 0; while ((1 << b) < mx) b += 1; long long ops = b, all_same = 1; for (auto x : m) { if (x.second != (1 << b)) { all_same = 0; break; } } ops += all_same == 0; long long p = 1; for (auto x : m) p *= x.first; cout << p << " " << ops << endl; } ```

Same GCD?

Find the number of x that satisfies $ gcd(a, m) = gcd(a + x, m) $ where $ 0 <= x < m $. For example, if $ a = 4 $ and $ m = 9 $, there would be 6 $x$ which are $0, 1, 3, 4, 6, 7$. From Euclidean algorithm, we know that $ gcd(a, b) = gcd(a \bmod b, b) $. For example, if $ a = 4 $ and $ b = 8 $, we know that $ gcd(12, 8) = gcd(12 \bmod 8, 8)$, in this case, which is $4$. Back to our question, we know that $ 0 <= x < m $, which means that the range of $ a + x $ would be $ a .. m + a $, it can be divided by $ m $. Let $ k $ be $ (a + x) \bmod m $, the range of $ k $ is $ 0 .. m $. Now we can rewrite it to $ gcd(a, m) = gcd(k, m) $. Let's say $ gcd(a, m) = gcd(k, m) = g $, it then can be rewritten as $ gcd(\frac{k}{g}, \frac{m}{g}) = 1 $. In this case, we can use Euler's totient function to find out how many numbers from $ 1 $ to $ \frac{k}{g} $ are co-prime to $ \frac{k}{g} $. The function is defined as $$ \varphi(n) = n \displaystyle \prod_{n= p | n}^{} (1 - \frac{1}{p}) $$ For example, for $\varphi(36)$, it can be factoralized as $\varphi(2^2 * 3^2)$ = $36 * (1 - \frac{1}{2}) * (1 - \frac{1}{3}) = 12 $. Those 12 numbers are $1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31$ and $ 35$. Here's the implementation of Euler's totient function in C++. ``` long long phi(long long n) { long long result = n; for (long long i = 2; i * i <= n; i++) { if (n % i == 0) { while (n % i == 0) n /= i; result -= result / i; } } if (n > 1) result -= result / n; return result; } ``` Therefore, back to our question, the solution is relatively simple. ``` long long a, m; cin >> a >> m; cout << phi(m / gcd(a, m)) << endl; ```

Lagrange Interpolation

There are some well-known formulas $$ \sum_{i=1}^n i = 1 + 2 + \dots + n = \frac{n * (n + 1)}{2} $$ $$ \sum_{i=1}^n i^2 = 1^2 + 2^2 + \dots + n^2 = \frac{n * (n + 1) * (2n + 1)}{6} $$ $$ \sum_{i=1}^n i^3 = 1^3 + 2^3 + \dots + n^3 = (\frac{n * (n + 1)}{2}) ^ 2 $$ Then what is the value of the following sum of the k-th power? $$ \sum_{i=1}^n i^k = 1^k + 2^k + \dots + n^k \mod 10^9 + 7 $$ given $1 <= n <= 10^9$ and $0 <= k <= 10^6$ The target sum will be a degree $ (k + 1) $ polynomial and we can interpolate the answer with $ (k + 2) $ data points, i.e. $degree(f) + 1$ points. In order to find the data points, we need to calculate $f(0) = 0$, $f(x) = f(x - 1) + x ^ k$. If there is less than $k + 2$ data points, we can calculate the answer directly. ``` if (x <= k + 1) { int s = 0; for (int i = 1; i <= x; i++) { s = (s + qpow(i, k)) % mod; } return s; } ``` Otherwise, let's say $f(x_1) = y_1, f(x_2) = y_2, ..., f(x_n) = y_n$ and $f$ is the unique $(n - 1)$ degree polynomial and we are interested in $f(x) = \sum_{i=1}^n f_i(x)$ where $f_i(x) = y_i * \prod_{j=1, j!=i}^n \frac{x - x_j}{x_i - x_j} $. Therefore, we have our Lagrange interpolation as $ f(x) = \sum_{i=1}^n y^i \prod_{j=1, j!=i}^n \frac{x - x_j}{x_i - x_j} $. However, we need $O(n^2)$ to calculate $f(x)$. Let's substitute $x_i = i$ and $y_i = f(i)$ and we got $ f(x) = \sum_{i=1}^n f(i) \frac{\prod_{j=1, j!=i}^n x - j}{\prod_{j=1, j!=i}^n i - j} $. What can we do for numerator and denonminator here? For numerator, we can per-calculate the prefix and suffix product of $x$, for each $i$, we can calculate the nubmerator in $O(1)$. $$ \prod_{j=1, j!=i}^n x - x_j = [(x - 1)(x - 2)...(x-(i-1))] * [(x - (i + 1))*(x - (i + 2))...(x - n)] $$ ``` vector pre(k + 2), suf(k + 2); pre[0] = x; suf[k + 1] = x - (k + 1); for (int i = 1; i <= k; i++) pre[i] = pre[i - 1] * (x - i) % mod; for (int i = k; i >= 1; i--) suf[i] = suf[i + 1] * (x - i) % mod; ``` For denominator, we can precompute the factorials using their inverse in $O(1)$ also. $$ \prod_{j=1, j!=i}^n i - j = [(i - 1)(i - 2)(i - 3)...(i - (i - 1))] * [i - (i + 1)(i - (i + 2)...(i - n)] = (-1)^{n - i} (n - i)!(i - 1)! $$ ``` int qpow(int base, int exp) { int res = 1; while (exp) { if (exp & 1) res = (res * base) % mod; base = (base * base) % mod; exp >>= 1; } return res; } unordered_map<int, int> rv_m; int rv(int x) { if (rv_m.count(x)) { return rv_m[x]; } return rv_m[x] = qpow(x, mod - 2); } vector inv(k + 2); inv[0] = 1; for (int i = 1; i <= k + 1; i++) inv[i] = inv[i - 1] * rv(i) % mod; ``` Overall, we can calculate $f(x)$ in $O(n)$. Complete Code: ``` #include <bits/stdc++.h> using namespace std; #define int long long const int mod = 1e9 + 7; int qpow(int base, int exp) { int res = 1; while (exp) { if (exp & 1) res = (res * base) % mod; base = (base * base) % mod; exp >>= 1; } return res; } unordered_map<int, int> rv_m; int rv(int x) { if (rv_m.count(x)) { return rv_m[x]; } return rv_m[x] = qpow(x, mod - 2); } int lagrange_interpolate(int x, int k, bool bf = false) { if (k == 0) return x; // find 1 ^ k + 2 ^ k + ... + x ^ k // (k + 1) degree polynomial -> (k + 2) points if (x <= k + 1 || bf) { int s = 0; for (int i = 1; i <= x; i++) { s = (s + qpow(i, k)) % mod; } return s; } vector<int> pre(k + 2), suf(k + 2), inv(k + 2); inv[0] = 1, pre[0] = x; suf[k + 1] = x - (k + 1); for (int i = 1; i <= k; i++) pre[i] = pre[i - 1] * (x - i) % mod; for (int i = k; i >= 1; i--) suf[i] = suf[i + 1] * (x - i) % mod; for (int i = 1; i <= k + 1; i++) inv[i] = inv[i - 1] * rv(i) % mod; int ans = 0; int yi = 0; // 0 ^ k + ~ i ^ k int num, denom; for (int i = 0; i <= k + 1; i++) { yi = (yi + qpow(i, k)) % mod; // interpolate point: (i, yi) if (i == 0) num = suf[1]; else if (i == k + 1) num = pre[k]; else num = pre[i - 1] * suf[i + 1] % mod; // numerator denom = inv[i] * inv[k + 1 - i] % mod; // denominator if ((i + k) & 1) ans += (yi * num % mod) * denom % mod; else ans -= (yi * num % mod) * denom % mod; ans = (ans % mod + mod) % mod; } return ans; } void solve() { int n, k; cin >> n >> k; cout << lagrange_interpolate(n, k) << endl; } int32_t main() { ios_base::sync_with_stdio(false), cin.tie(nullptr); // int T; cin >> T; // while(T--) solve(); solve(); return 0; } ```

De Bruijn Sequence

De Bruijn Sequence is a binary sequence of order $ n $ of bits $b_i \in {0, 1} $ where $ b = {b_i, ..., b_{2^n}}$ such that every string of length $ n $ ${a_1, ..., a_n} \in $ {0, 1} $ ^ n $ occurs exactly once consecutively in $b$. To generate a De Bruijn Sequence, we need to get the Euler circuit for the graph for all $ n - 1 $ possible stringds. For example, given $ n = 4 $ & $ k = 2 $,  We would have a sequence of length $2 ^ 4 = 16$ using Eulerian $k$-D de Bruijn graph cycle where $k = n - 1$ which is 3 in this case. Each edge will be traversed exactly once to use each of the 16 4-digit sequences exactly once. The Eulerian path is $$ 000, 000, 001, 011, 111, 111, 110, 101, 011, 110, 100, 001, 010, 101, 010, 100, 000. $$ The de Bruijn sequence is $$ 0 0 0 0 1 1 1 1 0 1 1 0 0 1 0 1 $$ For output sequences of length $ k = 4 $, we got ``` {0 0 0 0} 1 1 1 1 0 1 1 0 0 1 0 1 0 {0 0 0 1} 1 1 1 0 1 1 0 0 1 0 1 0 0 {0 0 1 1} 1 1 0 1 1 0 0 1 0 1 0 0 0 {0 1 1 1} 1 0 1 1 0 0 1 0 1 0 0 0 0 {1 1 1 1} 0 1 1 0 0 1 0 1 0 0 0 0 1 {1 1 1 0} 1 1 0 0 1 0 1 0 0 0 0 1 1 {1 1 0 1} 1 0 0 1 0 1 0 0 0 0 1 1 1 {1 0 1 1} 0 0 1 0 1 0 0 0 0 1 1 1 1 {0 1 1 0} 0 1 0 1 0 0 0 0 1 1 1 1 0 {1 1 0 0} 1 0 1 0 0 0 0 1 1 1 1 0 1 {1 0 0 1} 0 1 0 0 0 0 1 1 1 1 0 1 1 {0 0 1 0} 1 0 0 0 0 1 1 1 1 0 1 1 0 {0 1 0 1} 0} 0 0 0 1 1 1 1 0 1 1 0 0 {1 0 1 ... ... 0 0} 0 0 1 1 1 1 0 1 1 0 0 1 {0 1 ... ... 0 0 0} 0 1 1 1 1 0 1 1 0 0 1 0 {1 ... ``` To find Euler circuit, we can use Hierholzer’s algorithm to get it in linear time. If we randomly traverse the graph without repeating edges, it will eventually end up on the same vertex but the path may not include all the edges. Therefore, we have to remove those visited edges from the graph, which will split into several components. All the components contain Euler Circuit. ## [Cracking the Safe (Hard)](https://leetcode.com/problems/cracking-the-safe/) There is a safe protected by a password. The password is a sequence of n digits where each digit can be in the range [0, k - 1]. The safe has a peculiar way of checking the password. When you enter in a sequence, it checks the most recent n digits that were entered each time you type a digit. For example, the correct password is "345" and you enter in "012345": After typing 0, the most recent 3 digits is "0", which is incorrect. After typing 1, the most recent 3 digits is "01", which is incorrect. After typing 2, the most recent 3 digits is "012", which is incorrect. After typing 3, the most recent 3 digits is "123", which is incorrect. After typing 4, the most recent 3 digits is "234", which is incorrect. After typing 5, the most recent 3 digits is "345", which is correct and the safe unlocks. What is the string of minimum length that will unlock the safe at some point of entering it? For example, $ n = 2, k = 2 $, one of the possible answers is $01100$ because we can type $01$ from the $1st$ digit, $11$ from the $2nd$ digit, $10$ from the $3rd$ digit, and $00$ from the $4th$ digit. ## Solution ```cpp class Solution { public: string ans; vector> vis; int n, k, v; void dfs(int u) { for(int i = 0; i < k; i++) { if(!vis[u][i]) { vis[u][i] = 1; dfs((u * k + i) % v); ans += '0' + i; } } } string crackSafe(int n, int k) { if(k == 1) return string(n, '0'); this->n = n, this->k = k; v = pow(k, n - 1); // vis[k ^ (n - 1)][k] vis.resize(v, vector(k)); dfs(0); return ans + ans.substr(0, n - 1); } }; ```

Codeforces Round #720 - 1521B. Nastia and a Good Array

This is an unofficial editorial for [Nastia and a Good Array](https://codeforces.com/contest/1521/problem/B). ## Problem Statement Nastia has received an array of n positive integers as a gift. She calls such an array a good that for all i ($ 2 <= i <= n $) takes place $ gcd(a_i − 1, a_i )$ = 1, where $ gcd(u, v) $ denotes the greatest common divisor (GCD) of integers u and v. You can perform the operation: select two different indices $i$, $j$ ($1 <= i, j <= n, i \neq j$) and two integers $x$, $y$ ($1 <= x,y <= 2 * 10^9$) so that $ min(a_i, a_j) = min(x, y)$. Then change $a_i$ to $x$ and $a_j$ to $y$. The girl asks you to make the array good using at most $n$ operations. It can be proven that this is always possible. ## Approach From the statement, we can have our first obversation which is $ a_i - 1 $ and $a_i$ are coprime, denoted by $ gcd(a_i − 1, a_i )$ = $1$. Two integers are coprime if the only positive integer that is a divisor of both of them is 1, mathematically $ gcd(a, b) = 1 $. Therefore, this question can be rephrased as "how to make a_i - 1 and a_i coprime using at most $n$ operations". ### Solution 1 We can use the fact that an integer $x$ and $ x \pm 1 $ are coprime. First let's find the min value $x$ and its position $pos$ in array $a$ as we have to use this value to perform the operations. For all integer $i$ where $ 1 <= i <= n $, we can perform $ (pos, i, x ,abs(pos - i)) $ to replace $a_i$ to $x$ + $abs(pos - i)$. For the first test case, we can make $ [9, 6, 3, 11, 15] $ to $ [5, 4, 3, 4, 5] $ using $ n - 1 $ operations. ### Solution 2 We can put a prime number, let's say $ 1e9 + 7$ on every odd index if the minimum value is on even index and vice versa. In this case, we just need $ (n + 1) / 2 $ operations to turn $ [9, 6, 3, 11, 15] $ to $ [9, 1e9 + 7, 3, 1e9 + 7, 15] $.

Nezzar and Symmetric Array

This is an unofficial editorial for [Nezzar and Symmetric Array](https://codeforces.com/problemset/problem/1478/C). ## Problem Statement Long time ago there was a symmetric array $a_1$, $a_2$, ... ,$a_{2n}$ consisting of $2n$ distinct integers. Array $a_1$, $a_2$, ... ,$a_{2n}$ is called symmetric if for each integer $1 <= i <= 2n$, there exists an integer $1 <= j <= 2n$ such that $a_i = -a_j$. For each integer $1<=i<=2n$, Nezzar wrote down an integer $d_i$ equal to the sum of absolute differences from $a_i$ to all integers in $a$, i. e. $d_i$ = $\sum_{j=1}^{2n} |a_i - a_j|$. Now a million years has passed and Nezzar can barely remember the array $d$ and totally forget $a$. Nezzar wonders if there exists any symmetric array 𝑎 consisting of $2n$ distinct integers that generates the array $d$. ## Input The first line contains a single integer $t$ ($1 <= t <= 10^5$) — the number of test cases. The first line of each test case contains a single integer 𝑛 ($1 <= n <= 10^5$). The second line of each test case contains $2n$ integers $d_1, d_2, ..., d_{2n}$ ($1 <= d_i <= 10^{12}$). It is guaranteed that the sum of 𝑛 over all test cases does not exceed $10^5$. ## Output For each test case, print "YES" in a single line if there exists a possible array 𝑎. Otherwise, print "NO". You can print letters in any case (upper or lower). ## Approach Here's the simulation of the first example. ``` a = [1 -3 -1 3] i = 0 : 0 + 4 + 2 + 2 = 8 i = 1 : 4 + 0 + 2 + 6 = 12 i = 2 : 2 + 2 + 0 + 4 = 8 i = 3 : 2 + 6 + 4 + 0 = 12 d = [8, 12, 8, 12] ``` Each element has a positive and negative value. Supposing the positive value is $ x $, and the absolute difference to $(y, -y)$ would be $| x - y | + | x + y | $. Similarly, for $ -x $, that would be $ |-x - y | + |-x + y |$, which is also $|x - y| + |x + y|$. Therefore, for each $ d[i] $, there would be a pair as well. For $|x - y| + |x + y|$, we have two different cases. For $x > y$, $|x - y| + |x + y|$ would be $ 2 * x $. For $x > y$, $|x - y| + |x + y|$ would be $ 2 * y $. Now we know that $|x - y| + |x + y|$ = $2 * max(x, y)$. For each $ d[i] $, it is the sum of each absolute differences from $a[i]$ to all integers. Combined with the previous finding, we got $$ d[i] = \sum_{j=1}^{2n} max(abs(a[i]), abs(a[j])) $$ Given the array $d$, how can we generate the array $a$ back? Supposing the maximum element in $a$ is called $max_1$, the corresponding $d[i]$ would be $max_1 * 2 * n$. Therefore, we now have $max_1 = d[i] / 2 / n$. For the second maximum element, let's say $max_2$, as there is only $max_1$ which is greater than $max_2$, all other $(n - 1)$ elements are less than or equal to $max2$. The sum of absolute differences to them would be $max_2 * 2 * (n - 1)$. As $max_2 < max_1$, we need to add $max_1 * 2$ back to $d[i]$. Similarly, we can do the same thing one by one to get the original array $a$ back. We can induce that $$ max_1 = d[i] / 2 / n $$ $$ max_2 = (d[i] - max_1 * 2) / 2 / (n - 1) $$ $$ max_3 = (d[i] - max_2 * 2) / 2 / (n - 2) $$ $$ max_4 = (d[i] - max_3 * 2) / 2 / (n - 3) $$ $$ \vdots $$ $$ max_m = (d[i] - max_{m - 1} * 2) / 2 / (n - k) $$ For each elelment $x$, we need to check the occurence of its absolute value. If $x$ is odd or its occurence is odd, then the answer is $NO$. Also, if $x$ appears more than 2 times, that would be also $NO$. For each $max_m$, we can verify that if we can retrieve an integer, i.e. $(d[i] - max_{m - 1} * 2) / 2 % (n - k) $ is $0$ or not. If not, that is also $NO$. if $(d[i] - max_{m - 1} * 2) / 2 / (n - k) $ appears before or it is less than or equal to $0$, that is also not a correct answer. Therefore, we have 6 cases to check in total. For other cases, that would be $YES$. ## Solution ``` void solve() { long long n; cin >> n; map<long long, long long> vis, m; for(int i = 0; i < 2 * n; i++) cin >> d[i], m[-d[i]]++; long long cur_sum = 0, k = 0; EACH(it, m) { long long abs_difference = -it.fi, occurrence = it.se; if(abs_difference % 2 || occurrence % 2 || occurrence > 2) { cout << "NO" << "\n"; return; } long long p = (abs_difference - cur_sum * 2) / 2; long long q = n - k; if(p % q) { cout << "NO" << "\n"; return; } p /= q; if(vis.count(p) || p <= 0) { cout << "NO" << "\n"; return; } vis[p] = 1, cur_sum += p, k++; } cout << "YES" << "\n"; } ```

Chinese Remainder Theorem

A linear congruence can be displayed as $$ ax \equiv b (\text{mod } m ) $$ By definition of congruence, $ ax \equiv b (\text{mod } m ) $ iff $ax - b$ is disible by $m$. According to Wikipedia, the earliest known statement of the Chinese Remainder Theorem is by the Chinese mathematician Sun-tzu in the Sun-tzu Suan-ching in the 3rd century AD. $$ 今有物不知其數，三三數之剩二，五五數之剩三，七七數之剩二，問物幾何？ $$ We can rewrite the above statement into below congruence equations. $$ x \equiv 2 (\text{mod } 3 ) $$ $$ x \equiv 3 (\text{mod } 5 ) $$ $$ x \equiv 2 (\text{mod } 7 ) $$ and the answer is $23$. In fact, this is the minimum possible solution. Starting from 23, you can get another possible answer by adding 105, i.e. $$ x = 23 + 105 * n $$ where $$ n \in {0, 1, 2, 3, \cdots} $$ Given a set of congruence equations, we are interested to find $a$ that produces the given remainders. $$ a \equiv a_1 (\text{mod } p_1 ) $$ $$ a \equiv a_2 (\text{mod } p_2 ) $$ $$ \cdots \\ $$ $$ a \equiv a_k (\text{mod } p_k ) $$ where every pair $p_i$ are pairwise coprime, $a_i$ are given constants.

## Problem: [Oversleeping](https://atcoder.jp/contests/abc193/tasks/abc193_e) In this problem, we are interested in finding the minimum non-negative integer t such that $$ X \le t \text{ mod } (2X + 2Y) \lt X + Y $$ $$ P \le t \text{ mod } (P + Q) \lt P + Q $$ We can solve this problem using Chinese Remainder Theorem. $$ t \equiv t_1 (\text{mod } 2X + 2Y ) $$ $$ t \equiv t_2 (\text{mod } P + Q ) $$ AtCoder has provided a crt library [here](https://github.com/atcoder/ac-library/blob/master/atcoder/math.hpp#L34), which makes the implementation relatively simple. ```cpp #include <atcoder/math> using namespace atcoder; const ll mx = numeric_limits<ll>::max(); void solve() { ll X, Y, P, Q; cin >> X >> Y >> P >> Q; ll ans = mx; for(ll t1 = X; t1 < X + Y; t1++) { for(ll t2 = P; t2 < P + Q; t2++) { auto [t, lcm] = crt( { t1, t2 }, // rem { 2 * X + 2 * Y, P + Q } // mod ); if(lcm == 0) { // no solution continue; } MIN(ans, t); } } if(ans == mx) OUT("infinity"); else OUT(ans); } ``` The full solution is available [here](https://github.com/wingkwong/competitive-programming/blob/master/atcoder/contests/abc193/E.cpp).

AtCoder - ABC185C. Duodecim Ferra

You can practice the problem Duodecim Ferra [here](https://atcoder.jp/contests/abc185/tasks/abc185_c). ## Problem Statement There is an iron bar of length ``L`` lying east-west. We will cut this bar at 11 positions to divide it into 12 bars. Here, each of the 12 resulting bars must have a positive integer length. Find the number of ways to do this division. Two ways to do the division are considered different if and only if there is a position cut in only one of those ways. Under the constraints of this problem, it can be proved that the answer is less than 2^63. ## Solutions This problem can be solved using Stars and Bars Theorem. Given the lenght ``L``, we have a Diophantine equation ``x[0] + x[1] + ... + x[11] = L`` where x[i] are the lengths of the bars after the division. We need to select 11 positions out of ``L - 1`` positions. For example, if ``L`` is 14, we will have the following possible points to cut. ``` 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 ``` Therefore, the answer is ``` C(n, r) = C(L - 1, r - 1) = C(14 - 1, 12 - 1) = C(13, 11) = 78 ``` We can solve it in O(r) time complexity and O(1) space complexity . nCr can be written as ``` (n)! / (r)!( / (n - r)! = (n * (n - 1) * (n - 2) * ... * 1 ) / (r * (r - 1) * (r - 2) * ... * 1) / ((n - r) * (n - r - 1) * (n - r - 2) * ... * 1) = n * (n - 1) * (n - 2) * ... * (n - (r - 1)) / (r * (r - 1) * (r - 2) * ... * 1) ``` ```cpp // AC - 3 ms void solve() { ll L; cin >> L; ll ans = 1; FOR(i, 1, 12) { ans *= L - i; // n * (n - 1) * (n - 2) * ... * (n - (r - 1)) ans /= i; // r * (r - 1) * (r - 2) * ... * 1 } OUT(ans); } ``` We can turn it to a template for similar problems ```cpp template< typename T > T comb(int64_t N, int64_t K) { if(K < 0 || N < K) return 0; T ret = 1; for(T i = 1; i <= K; ++i) { ret *= N--; ret /= i; } return ret; } // AC - 7 ms void solve() { ll L; cin >> L; OUT(comb<ll>(L - 1, 11)); } ``` We can also use dynamic programming to solve this problem. The recursive formula is ``` C(n, r) = C(n - 1, r - 1) + C(n - 1, r) ``` For ``r == 0`` and ``n == r``, the result would be 1. ```cpp // AC - 10 ms const int mxN = 205; ll c[mxN][mxN]; void solve() { ll L; cin >> L; REP(i, l) { c[i][0] = c[i][i] = 1; FOR(j, 1, i) { c[i][j] = c[i - 1][j - 1] + c[i - 1][j]; } } OUT(c[L - 1][11]); } ```

TLX - TROC17A. Firework Festival

You can practice the question [here](https://tlx.toki.id/contests/troc-17/problems/A). Given two arrays A and B, each of size N. Determine whether the sum of A[i]^B[i] for all 1 <= i <= N, is odd or even. Display the output 0 if the sum is even, or 1 if the sum is odd. Input Format ``` N A[1] A[2] ... A[N] B[1] B[2] ... B[N] ``` Sample Input ``` 5 2 4 6 8 2 1 2 3 4 5 ``` Sample Output ``` 0 ``` Constraints ``` 1 <= N <= 100 1 <= A[i], B[i] <= 100 ``` Usually for Problem A, most of the solutions are brute-force. However, if we take the edge case 100, A[0] ^ B[0] + A[1] ^ B[1] + ... + A[99] ^ B[99] where A[i] and B[i] are 100, the overall result would occur overflow. We can notice that this problem is all about parity. The exponent B[i] of A[i] does not change the parity of A[i] ^ B[i]. Hence, we can conclude that ``` even ^ odd -> even even ^ even -> even odd ^ even -> odd odd ^ even -> odd ``` and we know that ``` even + even -> even odd + odd -> even even + odd -> odd ``` Therefore, we can simply sum all the values and check if it is even or odd. ```cpp int main() { int n; cin >> n; vi a(n), b(n); READ(a); READ(b); int sum = 0; REP(i, n) sum += a[i]; OUT((sum & 1)); return 0; } ```

Project Euler #001 - Multiples of 3 and 5

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3,5,6 and 9. The sum of these multiples is 23. Find the sum of all the multiples of 3 or 5 below N. Sample Input ``` 2 10 100 ``` Sample Output ``` 23 2318 ``` To sum from 1 to i, it is ``` s = 1 + 2 + 3... + (i - 1) + i ``` if you reverse the order ``` s = 1 + 2 + 3... + (i - 1) + i s = i + (i - 1) + (i - 2) + ... + 2 + 1 ``` summing each value, we got ``` 2 * s = (i + 1) + (i + 1) + ...(i + 1) + (i + 1) ``` and there are ``i`` ``(i + 1)`` in above formula ``` 2 * s = i * (i + 1) ``` at the end, we got ``` s = i * (i + 1) / 2 ``` We can use ``s = i(i + 1) / 2`` to caculate the sum from 1 to ``i``. However, the question just needs us to calculate the sum of the multiples of 3 or 5. Take 3 as an example ``` s = 3 + 6 + 9 + ... + 3i s = 3(1 + 2 + 3 + ... + i) ``` We know that ``1 + 2 + 3 + ... + i`` can be calculated using ``s = i * (i + 1) / 2``. Therefore, we now know ``` s = 3 * (1 + 2 + 3 + ... + i) s = 3 * (i * (i + 1) / 2) ``` where ``` 3 * i <= n i <= n / 3 ``` it becomes ``` s = n * ((n / k)((n / k) + 1) / 2) ``` The question states that it only requires the multiples of K below N, that means it does not include N, hence we should substract N from 1. However, if we sum up multiples of 3 and multiples of 5, we can get duplicate values, i.e. 15 in below example ``` multiples of 3: 3, 6, 9, 15, 18... multiples of 5: 5, 10, 15, 20,... ``` Hence, we need to subtract the series of their least common multiple (LCM) which is 15. The final answer is ``` S(3) + S(5) - S(15) ``` Final Solution: ```cpp ll t,i,x; ll s(ll n,ll k){ x = n / k; return (k * (x * (x + 1))) / 2; } int main() { FAST_INP; cin >> t; TC(t){ cin >> i; cout << s(i - 1, 3) + s(i - 1, 5) - s(i - 1, 15) << "\n"; } return 0; } ```

Make Good

You can practice the problem [here](https://codeforces.com/contest/1270/problem/C). ## Problem An array a[0], a[1], ... , a[n - 1] of nonnegative integer numbers is said to be good if ``` a[0] + a[1] + ... + a[n - 1] = 2 * (a[0] ^ a[1] ^ ... ^ a[n - 1]) ``` Given that an array of length n, append at most 3 elements to it to make it good. ## Solution Let S be the sum of the array, which is a[0] + a[1] + ... + a[n - 1] and X be their XOR value. Then we'll have ``` S = 2 * X ``` A simple solution here is to add X and X + S to the array. ``` S = 2 * X S + X + (X + S) = 2 * (X ^ X ^ (X + S)) // X ^ X = 0 2 * (X + S) = 2 * (X + S) ``` C++ Implementation ``` ll S = 0, X = 0; REP(i, n) { ll a; cin >> a; S += a; X ^= b; } cout << 2 << "\n"; cout << X << " " << X + S << "\n"; ```