BOJ 1890 - 점프

# 문제 N×N 게임판에 수가 적혀져 있다. 이 게임의 목표는 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프를 해서 가는 것이다. 각 칸에 적혀있는 수는 현재 칸에서 갈 수 있는 거리를 의미한다. 반드시 오른쪽이나 아래쪽으로만 이동해야 한다. 0은 더 이상 진행을 막는 종착점이며, 항상 현재 칸에 적혀있는 수만큼 오른쪽이나 아래로 가야 한다. 한 번 점프를 할 때, 방향을 바꾸면 안 된다. 즉, 한 칸에서 오른쪽으로 점프를 하거나, 아래로 점프를 하는 두 경우만 존재한다. 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 이동할 수 있는 경로의 개수를 구하는 프로그램을 작성하시오. # 입력 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 오른쪽 아래 칸에는 항상 0이 주어진다. # 출력 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 문제의 규칙에 맞게 갈 수 있는 경로의 개수를 출력한다. 경로의 개수는 263-1보다 작거나 같다. # 예제 입력 ``` 4 2 3 3 1 1 2 1 3 1 2 3 1 3 1 1 0 ``` # 예제 출력 ``` 3 ``` # 정답 ```cpp const int mxN = 105; ll n, dp[mxN][mxN], vis[mxN][mxN], g[mxN][mxN]; int dx[2] = {1, 0}, dy[2] = {0, 1}; ll dfs(int x, int y) { vis[x][y] = 1; if(x == n - 1 && y == n - 1) return 1; if(dp[x][y] || g[x][y] == 0) return dp[x][y]; for(int i = 0; i < 2; i++) { int next_x = x + g[x][y] * dx[i]; int next_y = y + g[x][y] * dy[i]; if(next_x < 0 || next_x >= n || next_y < 0 || next_y >= n || vis[next_x][next_y]) continue; dp[x][y] += dfs(next_x, next_y); vis[next_x][next_y] = 0; } return dp[x][y]; } void solve() { cin >> n; REP(i, n) REP(j, n) cin >> g[i][j]; OUT(dfs(0, 0)); } int main() { FAST_INP; solve(); return 0; } ```

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; } ```

Finding all occurrences of a pattern in a given string in linear time using Z Algorithm

Given a string S and a pattern P, find all occurences of P in S. Supposing the length of S is m and that of P is n, we can find the answer using Z Algorithm in linear time. First, we need to construct a Z array where Z[i] is the length of longest common prefix between S and the suffix starting from S[i]. If Z[i] = 0, it means that S[0] != S[i] and the first element of Z is generally not defined. ``` vector<int> z_function(string s) { int n = (int) s.length(); vector<int> z(n); for (int i = 1, l = 0, r = 0; i < n; ++i) { if (i <= r) z[i] = min (r - i + 1, z[i - l]); while (i + z[i] < n && s[z[i]] == s[i + z[i]]) ++z[i]; if (i + z[i] - 1 > r) l = i, r = i + z[i] - 1; } return z; } ``` For this standard string match problem, we can use Z Algorithm to solve it in O(m + n) on the string P + (something won't be matched in both string) + S. If there is an indice i with Z[i] = n, then we find one occurence. Example: S = zabcabdabc P = abc m = 10 n = 3 Let K = P + (something won't be matched in both string) + S K = P + $ + S = abc$zabcabdabc Z would be {0, 0, 0, 0, 3, 0, 0, 2, 0, 0, 3, 0, 0} There are 2 indices ``i`` with Z[i] = n. Hence, there are 2 occurences of a pattern P in S. Here's the code implemented in C++. ``` void solve() { string p, s; cin >> p >> s; string k = p + "$" + s; vector z = z_function(k); int n = p.size(), m = k.size(), cnt = 0; REP(i, m) if(z[i] == n) cnt++; OUT(cnt); } ```

Hashing values using SHA-2 in PySpark

SHA stands for Secure Hashing Algorithm and 2 is just a version number. SHA-2 revises the construction and the big-length of the signature from SHA-1. You may also see SHA-224, SHA-256, SHA-384 or SHA-512. Those are referring the bit-lengths of SHA-2. It's a bit confusing. SHA-2 produces irreversible and unique hashes as it is a one-way hash function. The original data remains secure and unknown. However, given than a SHA-2 function with L message digest bits, you can have maximum 2^L possibilities, which means somebody can perform a brute force search even though it is not quite practical. Moreover, with a precomputed table, called rainbow table for caching the output of hash functions, simple input can be easily cracked. Therefore, to prevent precomputation attacks, we need salting. Salting is just an additional input concatenating to the original input. It should be long and random every time calling the hash function. ``` saltedhash(input) = hash_function(salt + input) ``` In PySpark, ``sha2`` was implemented since version 1.5. ``` def sha2(col, numBits): """Returns the hex string result of SHA-2 family of hash functions (SHA-224, SHA-256, SHA-384, and SHA-512). The numBits indicates the desired bit length of the result, which must have a value of 224, 256, 384, 512, or 0 (which is equivalent to 256). >>> digests = df.select(sha2(df.name, 256).alias('s')).collect() >>> digests[0] Row(s=u'3bc51062973c458d5a6f2d8d64a023246354ad7e064b1e4e009ec8a0699a3043') >>> digests[1] Row(s=u'cd9fb1e148ccd8442e5aa74904cc73bf6fb54d1d54d333bd596aa9bb4bb4e961') """ sc = SparkContext._active_spark_context jc = sc._jvm.functions.sha2(_to_java_column(col), numBits) return Column(jc) ``` First, we need to import the functions. ``` from pyspark.sql.functions import concat, col, lit, bin, sha2 ``` This is an example using ``withColumn`` with ``sha2`` function to hash the salt and the input with 256 message digest bits. ``` df = df.withColumn( col_name, sha2(concat(lit(generate_salt()), bin(col(col_name))), 256) ) ``` The hash value looks like ``8ba06918c277ee2e9b6eecb798fe64dc4a8c34d95b4514ecc267487aee9b84b9``.