We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
- Prepare
- Algorithms
- Strings
- Two Strings Game
- Discussions
Two Strings Game
Two Strings Game
+ 0 comments Here is my solution in java, C, C++ HackerRank Two Strings Game Problem Solution
+ 0 comments Here is the solution Two Strings Game Click Here
+ 0 comments https://zeroplusfour.com/two-strings-game/
Here's how I did in all languages Java 8 , C++ , C , Python 3, Python 2.
+ 1 comment Can any one explain the question ..?
+ 1 comment C++ Solution
#include <iostream> #include <vector> #include <cstdio> #include <algorithm> using namespace std; #define maxn 300000 #define limit 1000000000000000000LL long long k; int n, m, i, j, cur, bad_value, kk; char a[maxn], b[maxn]; bool was[30]; pair<int, int> srt[maxn * 2 + 3]; struct sfa { long long dp[maxn * 2 + 3], grundy_sum[30], ways[maxn * 2 + 3]; int next[maxn * 2 + 3][26], len[maxn * 2 + 3], lnk[maxn * 2 + 3], grundy[maxn * 2 + 3]; int nodes, last, j; void init () { nodes = last = 1; len[1] = lnk[1] = 0; } void push (int c) { int cur = ++nodes, p; len[cur] = len[last] + 1; for(p = last; p && !next[p][c]; p = lnk[p]) next[p][c] = cur; if (!p) lnk[cur] = 1; else { int q = next[p][c]; if (len[p] + 1 == len[q]) lnk[cur] = q; else { int clone = ++nodes; len[clone] = len[p] + 1; for(int j = 0; j < 26; j++) next[clone][j] = next[q][j]; lnk[clone] = lnk[q]; for(; p && next[p][c] == q; p = lnk[p]) next[p][c] = clone; lnk[q] = lnk[cur] = clone; } } last = cur; } void grundy_precalc () { for(i = 1; i <= nodes; i++) srt[i] = make_pair(len[i], i); sort(srt + 1, srt + nodes + 1); for(i = 1; i <= nodes; i++) { int k = srt[nodes - i + 1].second; dp[k] = 1; for(j = 0; j < 30; j++) was[j] = 0; for(j = 0; j < 26; j++) if (next[k][j]) was[grundy[next[k][j]]] = true; for(j = 0; j < 30; j++) if (!was[j]) { grundy[k] = j; break; } } } void substr_precalc () { for(i = 1; i <= nodes; i++) srt[i] = make_pair(len[i], i); sort(srt + 1, srt + nodes + 1); for(i = 1; i <= nodes; i++) { int k = srt[nodes - i + 1].second; dp[k] = 1; for(j = 0; j < 26; j++) if (next[k][j]) dp[k] += dp[next[k][j]]; } ways[1] = 1; for(i = 1; i <= nodes; i++) for(j = 0; j < 26; j++) if (next[srt[i].second][j]) ways[next[srt[i].second][j]] += ways[srt[i].second]; for(i = 1; i <= nodes; i++) grundy_sum[grundy[i]] += ways[i]; } void dp_recalc (int bad_value) { for(i = 1; i <= nodes; i++) srt[i] = make_pair(len[i], i); sort(srt + 1, srt + nodes + 1); for(i = 1; i <= nodes; i++) { int k = srt[nodes - i + 1].second; dp[k] = grundy[k] != bad_value; for(j = 0; j < 26; j++) if (next[k][j]) dp[k] += dp[next[k][j]]; } } } sfa1, sfa2; int main (int argc, char * const argv[]) { // freopen("input.txt", "r", stdin); scanf("%d %d %lld\n", &n, &m, &k); sfa1.init(); sfa2.init(); for(i = 0; i < n; i++) { a[i] = getchar(); while (a[i] < 'a' || a[i] > 'z') a[i] = getchar(); sfa1.push(a[i] - 'a'); } for(i = 0; i < m; i++) { b[i] = getchar(); while (b[i] < 'a' || b[i] > 'z') b[i] = getchar(); sfa2.push(b[i] - 'a'); } sfa1.grundy_precalc(); for(i = 1; i <= sfa2.nodes; i++) was[i] = false; sfa2.grundy_precalc(); sfa2.substr_precalc(); for(i = 1; i <= sfa1.nodes; i++) srt[i] = make_pair(sfa1.len[i], i); sort(srt + 1, srt + sfa1.nodes + 1); for(i = 1; i <= sfa1.nodes; i++) { kk = srt[sfa1.nodes - i + 1].second; sfa1.dp[kk] = sfa2.dp[1] - sfa2.grundy_sum[sfa1.grundy[kk]]; for(j = 0; j < 26; j++) if (sfa1.next[kk][j]) { sfa1.dp[kk] += sfa1.dp[sfa1.next[kk][j]]; if (sfa1.dp[kk] > limit) sfa1.dp[kk] = limit; } } if (k > sfa1.dp[1]) { puts("no solution"); return 0; } cur = 1; while (k > 0) { if (k <= sfa2.dp[1] - sfa2.grundy_sum[sfa1.grundy[cur]]) break; else k -= sfa2.dp[1] - sfa2.grundy_sum[sfa1.grundy[cur]]; for(j = 0; j < 26; j++) if (k > sfa1.dp[sfa1.next[cur][j]]) k -= sfa1.dp[sfa1.next[cur][j]]; else { putchar('a' + j); cur = sfa1.next[cur][j]; break; } } puts(""); sfa2.dp_recalc(bad_value = sfa1.grundy[cur]); cur = 1; while (k > 0) { if (sfa2.grundy[cur] != bad_value) { --k; if (k == 0) break; } for(j = 0; j < 26; j++) if (k > sfa2.dp[sfa2.next[cur][j]]) k -= sfa2.dp[sfa2.next[cur][j]]; else { putchar('a' + j); cur = sfa2.next[cur][j]; break; } } puts(""); return 0; }
Load more conversations
Sort 19 Discussions, By:
Please Login in order to post a comment