Two Strings Game – HackerRank Solution

In this post, we will solve Two Strings Game HackerRank Solution. This problem (Two Strings Game) is a part of HackerRank Problem Solving series.

Solution – Two Strings Game – HackerRank Solution

C++

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

Java

import java.io.*;
import java.util.*;

public class Solution {

  static final int maxn = 300000;
  static final long limit = 1000000000000000000l;

  static boolean[] was = new boolean[30];
  static long[] srt;

  static class Sfa {

    long[] dp;
    long[] grundySum;
    long[] ways;

    int[][] next;
    int[] len;
    int[] lnk;
    int[] grundy;

    int nodes, last;

    Sfa(int n) {
      dp = new long[maxn * 2 + 3];
      grundySum = new long[30];
      ways = new long[maxn * 2 + 3];

      next = new int[26][maxn * 2 + 3];
      len = new int[maxn * 2 + 3];
      lnk = new int[maxn * 2 + 3];
      grundy = new int[maxn * 2 + 3];

      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 > 0) && (next[c][p] == 0); p = lnk[p]) {
        next[c][p] = cur;
      }
      if (p == 0) {
        lnk[cur] = 1;
      } else {
        int q = next[c][p];
        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[j][clone] = next[j][q];
          }
          lnk[clone] = lnk[q];
          for (; (p > 0) && next[c][p] == q; p = lnk[p]) {
            next[c][p] = clone;
          }
          lnk[q] = lnk[cur] = clone;
        }
      }
      last = cur;
    }

    void grundyPrecalc() {
      for (int i = 1; i <= nodes; i++) {
        srt[i] = ((long)len[i]  << 32l) | i;
      }
      Arrays.sort(srt, 1, nodes + 1);
      for (int i = 1; i <= nodes; i++) {
        int k = (int)(srt[nodes - i + 1] & 0xffffffffL);
        dp[k] = 1;
        Arrays.fill(was, false);
        for (int j = 0; j < 26; j++) {
          if (next[j][k] > 0) {
            was[grundy[next[j][k]]] = true;
          }
        }
        for (int j = 0; j < 30; j++) {
          if (!was[j]) {
            grundy[k] = j;
            break;
          }
        }
      }
    }

    void substrPrecalc() {
      for (int i = 1; i <= nodes; i++) {
        srt[i] = ((long)len[i]  << 32l) | i;
      }
      Arrays.sort(srt, 1, nodes + 1);
      for (int i = 1; i <= nodes; i++) {
        int k = (int)(srt[nodes - i + 1] & 0xffffffffL);
        dp[k] = 1;
        for (int j = 0; j < 26; j++) {
          if (next[j][k] > 0) {
            dp[k] += dp[next[j][k]];
          }
        }
      }
      ways[1] = 1;
      for (int i = 1; i <= nodes; i++) {
        int k = (int)(srt[i] & 0xffffffffL);
        for (int j = 0; j < 26; j++) {
          if (next[j][k] > 0) {
            ways[next[j][k]] += ways[k];
          }
        }
      }
      for (int i = 1; i <= nodes; i++) {
        grundySum[grundy[i]] += ways[i];
      }
    }

    void dpRecalc(int badValue) {
      for (int i = 1; i <= nodes; i++) {
        srt[i] = ((long)len[i]  << 32l) | i;
      }
      Arrays.sort(srt, 1, nodes + 1);
      for (int i = 1; i <= nodes; i++) {
        int k = (int)(srt[nodes - i + 1] & 0xffffffffL);
        dp[k] = grundy[k] != badValue ? 1 : 0;
        for (int j = 0; j < 26; j++) {
          if (next[j][k] > 0) {
            dp[k] += dp[next[j][k]];
          }
        }
      }
    }
  }

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

    StringTokenizer st = new StringTokenizer(br.readLine());
    int n = Integer.parseInt(st.nextToken());
    int m = Integer.parseInt(st.nextToken());
    long k = Long.parseLong(st.nextToken());

    srt = new long[maxn * 2 + 3];

    Sfa sfa1 = new Sfa(n);

    char[] a = br.readLine().toCharArray();
    for (int i = 0; i < n; i++) {
      sfa1.push(a[i] - 'a');
    }

    Sfa sfa2 = new Sfa(n);

    char[] b = br.readLine().toCharArray();
    for (int i = 0; i < m; i++) {
      sfa2.push(b[i] - 'a');
    }

    sfa1.grundyPrecalc();
    for (int i = 1; i <= (sfa2.nodes > 29 ? 29 : sfa2.nodes); i++) {
      was[i] = false;
    }

    sfa2.grundyPrecalc();
    sfa2.substrPrecalc();

    for (int i = 1; i <= sfa1.nodes; i++) {
      srt[i] = ((long)sfa1.len[i]  << 32l) | i;
    }
    Arrays.sort(srt, 1, sfa1.nodes + 1);
    for (int i = 1; i <= sfa1.nodes; i++) {
      int kk = (int)(srt[sfa1.nodes - i + 1] & 0xffffffffL);
      sfa1.dp[kk] = sfa2.dp[1] - sfa2.grundySum[sfa1.grundy[kk]];
      for (int j = 0; j < 26; j++) {
        if (sfa1.next[j][kk] > 0) {
          sfa1.dp[kk] += sfa1.dp[sfa1.next[j][kk]];
          if (sfa1.dp[kk] > limit) {
            sfa1.dp[kk] = limit;
          }
        }
      }
    }

    if (k > sfa1.dp[1]) {
      bw.write("no solution");
      bw.newLine();

      bw.close();
      br.close();
      return;
    }
    int cur = 1;
    while (k > 0) {
      if (k <= sfa2.dp[1] - sfa2.grundySum[sfa1.grundy[cur]]) {
        break;
      } else {
        k -= sfa2.dp[1] - sfa2.grundySum[sfa1.grundy[cur]];
      }
      for (int j = 0; j < 26; j++)
        if (k > sfa1.dp[sfa1.next[j][cur]])
          k -= sfa1.dp[sfa1.next[j][cur]];
        else {
          bw.write('a' + j);
          cur = sfa1.next[j][cur];
          break;
        }
    }
    bw.newLine();

    int badValue = sfa1.grundy[cur];
    sfa2.dpRecalc(badValue);
    cur = 1;
    while (k > 0) {
      if (sfa2.grundy[cur] != badValue) {
        --k;
        if (k == 0) {
          break;
        }
      }
      for (int j = 0; j < 26; j++) {
        if (k > sfa2.dp[sfa2.next[j][cur]]) {
          k -= sfa2.dp[sfa2.next[j][cur]];
        } else {
          bw.write('a' + j);
          cur = sfa2.next[j][cur];
          break;
        }
      }
    }

    bw.newLine();

    bw.close();
    br.close();
  }
}

Note: This problem (Two Strings Game) is generated by HackerRank but the solution is provided by CodingBroz. This tutorial is only for Educational and Learning purpose.