AtCoder - 167D. Teleporter

You can practice the problem [here](https://atcoder.jp/contests/abc167/tasks/abc167_d). ## Problem statement The Kingdom of Takahashi has N towns, numbered 1 through N. There is one teleporter in each town. The teleporter in Town i (1 <= i <= N) sends you to Town A[i]. Takahashi, the king, loves the positive integer K. The selfish king wonders what town he will be in if he starts at Town 1 and uses a teleporter exactly K times from there. Help the king by writing a program that answers this question. ## Sample Input 1 ``` 4 5 3 2 4 1 ``` ## Sample Output 1 ``` 4 ``` ## Sample Input 2 ``` 6 727202214173249351 6 5 2 5 3 2 ``` ## Sample Output 2 ``` 2 ``` ## Solution 1: Math If you take a look at the sample input 2, we can see that there is no way to traverse k times by listing out the travel. We can easily obverse the pattern the loop starts at a certain point. Example: ``` 6 5 2 5 3 2 1 -> 6 -> 2 -> 5 -> 3 -> 2 -> 5 -> 3 -> 2 -> 5 .... ``` Starting from the third step, it starts the loop 2 -> 5 -> 3. We can first create a map to store the index (0-based) and the value. ```cpp m[i] = a[i] ``` Then we can find how many steps we need to make before entering the loop, let's say ``c[i]``, and how many steps to reach the first duplicate element, let's say ``step``. ``` bool duplicate = false; ll i = 0, step = 0, kk = k; while(!duplicate && kk){ step++; // step is used to find out when a town has been visited if(d[i] == 1){ // if it is visited before, that is the start of the loop duplicate = true; continue; } d[i] = 1; // set the current i to 1, in other word, this has been visited c[i] = step; // we need to store the step to another map because we need to calculate from where the looping starts i = m[i] - 1; // -1 because it s 0 based kk--; // monitor if it s out of boundary } ``` We can calculate how many times we need to teleport from the repeating pattern as we know the length of the repeating pattern till k ``k - c[i]``, and the length of the repeating pattern ``step - c[i]``. ``` 6 5 2 5 3 2 1 -> 6 -> 2 -> 5 -> 3 -> 2 -> 5 -> 3 -> 2 -> 5 .... x x |-----------step---------| |--------------k-c[i]---------------- .... |---c[i]--| |------------------------k--------------------- .... ``` It performs only if it is not out of boundary. ```cpp if(kk){ ll r = (k - c[i]) % (step - c[i]); while(r >= 0){ i = m[i] - 1; r--; } } OUT(i + 1); ``` ## Solution 2: Binary Lifting After half a year, I came up with another solution using Binary Lifting which is a technique used to find the k-th ancestor of any node in a tree in O(logn). You can use it to find out Lowest Common Ancestor(LCA) as well. We know the ``k`` can go up to 10 ^ 18, which means we only need around 60 nodes (log2(10 ^ 18)). ```cpp const int mxN = 200005; const int mxNode = 60; // ~ log2(k) int up[mxN][mxNode]; ``` First we need to preprecess the tree in O(nlogn) using dynamic programming. ```cpp void binary_lifting() { for(int i = 1; i < mxNode; i++) { for(int u = 0; u < mxN; u++) { up[u][i] = up[up[u][i - 1]][i - 1]; } } } ``` Then we can easily find the k-th ancestor of any node in a tree in O(logn). In this case, we start from node 0. ```cpp int kth_ancestor(ll u, ll k) { for(int i = 0; i < mxNode; i++) { if(k & (1LL << i)) u = up[u][i]; } return u; } ``` The answer would be ``kth_ancestor(0, k) + 1``. ## Source Code The full solution is avilable [here](https://github.com/wingkwong/competitive-programming/blob/master/atcoder/contests/abc167/D.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]); } ```