HackerRank Two Strings Game Problem Solution

HackerRank Two Strings Game Problem Solution

Yashwant Parihar,

In this post, we will solve HackerRank Two Strings Game Problem Solution.

Consider the following game for two players:

There are two strings A and B. Initially, some strings A’ and B’ are written on the sheet of paper. A’ is always a substring of A and B’ is always a substring of B. A move consists of appending a letter to exactly one of these strings: either to A’ or to B’. After the move the constraint of A’ being a substring of A and B’ is a substring of B should still be satisfied. Players take their moves alternately. We call a pair (A’, B’) a position.

Two players are playing this game optimally. That means that if a player has a move that leads to his/her victory, he/she will definitely use this move. If a player is unable to make a move, he loses.

Alice and Bob are playing this game. Alice makes the first move. As always, she wants to win and this time she does a clever trick. She wants the starting position to be the Kth lexicographically winning position for the first player (i.e. her). Consider two positions (A’1, B’1) and (A’2, B’2). We consider the first position lexicographically smaller than the second if A1 is lexicographically smaller than A2, or if A1 is equal to A2 and B1 is lexicographically smaller than B2.

Please help her to find such a position, knowing the strings A, B and the integer K.

Note: An empty string has higher precedence than character "a"

Input Format

The first line of input consists of three integers, separated by a single space: N, M and K denoting the length of A, the length of B and K respectively. The second line consists of N small latin letters, corresponding to the string A. The third line consists of M small latin letters, corresponding to the string B.

Constraints

1 <= N, M <= 3 * 105
1 <= K <= 1018

Output Format

Output A’ on the first line of input and B’ on the second line of input. Please, pay attention that some of these strings can be empty. If there’s no such pair, output “no solution” without quotes.

Sample Input 0

2 1 3
ab
c

Sample Output 0

a
c

Explanation 0
The given strings are ab and c. So there are (2 * 2) * (2) = 8 ways to fill a starting position (each character has two options, either to be present or not present).
1.[“”,””]: If this is the start position, Alice will append a to A’. So, the next two moves will
consist of appending b and c to A’ and B’ respectively. So, Bob will suffer lack of moves
and hence Alice wins.

  1. [“”,””]: If this is the start position, Alice will append b to A’. Now, Bob will suffer lack of moves and hence Alice wins.
  2. [“a”,””]: If Alice appends to Athen Bob will append c to B’ and if Alice appends to B’ then Bob will append b to A’. So Alices looses.
  3. [“a”, “c”]: If this is the start position, Alice will append b to A’. Now, Bob will suffer lack of moves and hence Alice wins.
  4. [“ab”,””]: If this is the start position, Alice will append c to B’. Now, Bob will suffer lack of moves and hence Alice wins.
  1. [“ab”,”c”]: If this is the start position, Alice will suffer lack of moves and hence he looses.
  2. [“b”,””]: If this is the start position, Alice will append c to B’. Now, Bob will suffer lack of moves and hence Alice wins.
  3. [“b”,”c”]: If this is the start position, Alice will suffer lack of moves and hence he looses.
    So, the list of start positions in lexicographical order where Alice wins are: [‘””‘, ‘”””], [“”, “c”], [“a”, “c”], [“ab”, “”], [“b”, “”]. The 3rd one in this list is [“a”, “c”].
HackerRank Two Strings Game Problem Solution
HackerRank Two Strings Game Problem Solution

Two Strings Game C Solution


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define A_SIZE 26
#define MIN_C 'a'
typedef struct _st_node st_node;
typedef struct _st_edge st_edge;
struct _st_node{
int x;
unsigned long long count;
st_node *suffix_link;
st_edge *edges[A_SIZE+1];
};
struct _st_edge{
int from;
int to;
int suffix_index;
st_node *node;
};
int dfs0(st_node *root,int flag);
unsigned long long dfs1(st_node *root);
void dfs2(int idx,st_node *root);
unsigned long long dfs3(st_node *root);
void dfs4(int idx,st_node *root);
void suffix_tree(st_node *root,char *str,int len);
char a[300001],b[300001],ans[300001];
unsigned long long dp[50],total,K,KK,val;

int main(){
int N,M,i;
st_node r1,r2;
scanf("%d%d%lld%s%s",&N,&M,&K,a,b);
suffix_tree(&r1,a,N);
suffix_tree(&r2,b,M);
dfs0(&r1,0);
dfs0(&r2,1);
for(i=0;i<50;i++)
total+=dp[i];
dfs1(&r1);
if(r1.count<K){
printf("no solution\n");
return 0;
}
dfs2(0,&r1);
dfs3(&r2);
KK=0;
dfs4(0,&r2);
return 0;
}
int dfs0(st_node *root,int flag){
char arr[20];
int len,ret,i;
if(!root){
if(flag)
dp[0]++;
return 0;
}
memset(arr,0,sizeof(arr));
for(i=0;i<A_SIZE;i++)
if(root->edges[i]){
len=root->edges[i]->to-root->edges[i]->from+1;
ret=dfs0(root->edges[i]->node,flag);
if(len==1)
arr[ret]=1;
else
if(ret){
if(flag){
dp[0]+=len/2;
dp[1]+=(len-1)/2;
}
if(len%2)
arr[1]=1;
else
arr[0]=1;
}
else{
if(flag){
dp[1]+=len/2;
dp[0]+=(len-1)/2;
}
if(len%2)
arr[0]=1;
else
arr[1]=1;
}
}
for(i=0;i<20 && arr[i];i++);
if(flag)
dp[i]++;
root->x=i;
return i;
}
unsigned long long dfs1(st_node *root){
int len,ret,i;
unsigned long long ret2,count=0;
if(!root)
return total-dp[0];
for(i=0;i<A_SIZE;i++)
if(root->edges[i]){
len=root->edges[i]->to-root->edges[i]->from+1;
ret2=dfs1(root->edges[i]->node);
if(root->edges[i]->node)
ret=root->edges[i]->node->x;
else
ret=0;
count+=ret2;
if(ret){
count+=len/2*(total-dp[0]);
count+=(len-1)/2*(total-dp[1]);
}
else{
count+=len/2*(total-dp[1]);
count+=(len-1)/2*(total-dp[0]);
}
}
count+=total-dp[root->x];
root->count=count;
return count;
}
void dfs2(int idx,st_node *root){
int len,ret,start,i,j;
unsigned long long t1,t2;
if(!root){
ans[idx]=0;
printf("%s\n",ans);
val=0;
K-=KK;
return;
}
if(KK+total-dp[root->x]>=K){
ans[idx]=0;
printf("%s\n",ans);
val=root->x;
K-=KK;
return;
}
KK+=total-dp[root->x];
for(i=0;i<A_SIZE;i++)
if(root->edges[i]){
len=root->edges[i]->to-root->edges[i]->from+1;
if(root->edges[i]->node){
ret=root->edges[i]->node->x;
t2=root->edges[i]->node->count;
}
else{
ret=0;
t2=total-dp[0];
}
t1=0;
if(ret){
t1+=len/2*(total-dp[0]);
t1+=(len-1)/2*(total-dp[1]);
}
else{
t1+=len/2*(total-dp[1]);
t1+=(len-1)/2*(total-dp[0]);
}
if(KK+t1+t2<K)
KK+=t1+t2;
else if(KK+t1<K){
KK+=t1;
for(j=root->edges[i]->from;j<=root->edges[i]->to;j++)
ans[idx+j-root->edges[i]->from]=a[j];
dfs2(idx+root->edges[
i]->to-root->edges[i]->from+1,root->edges[i]->node);
return;
}
else{
if((ret && len%2) || (!ret && len%2==0))
start=1;
else
start=0;
for(j=root->edges[
i]->from;j<root->edges[i]->to;j++,start^=1){
ans[idx+j-root->edges[i]->from]=a[j];
if(KK+total-dp[start]>=K){
ans[idx+j+1-root->edges[i]->from]=0;
printf("%s\n",ans);
val=start;
K-=KK;
return;
}
KK+=total-dp[start];
}
return;
}
}
return;
}
unsigned long long dfs3(st_node *root){
int len,ret,i;
unsigned long long ret2,count=0;
if(!root){
if(val)
return 1;
return 0;
}
for(i=0;i<A_SIZE;i++)
if(root->edges[i]){
len=root->edges[i]->to-root->edges[i]->from+1;
ret2=dfs3(root->edges[i]->node);
if(root->edges[i]->node)
ret=root->edges[i]->node->x;
else
ret=0;
count+=ret2;
if(ret){
if(val!=0)
count+=len/2;
if(val!=1)
count+=(len-1)/2;
}
else{
if(val!=1)
count+=len/2;
if(val!=0)
count+=(len-1)/2;
}
}
if(val!=root->x)
count++;
root->count=count;
return count;
}
void dfs4(int idx,st_node *root){
int len,ret,start,i,j;
unsigned long long t1,t2;
if(!root){
ans[idx]=0;
printf("%s\n",ans);
return;
}
if(val!=root->x && KK+1==K){
ans[idx]=0;
printf("%s\n",ans);
return;
}
if(val!=root->x)
KK++;
for(i=0;i<A_SIZE;i++)
if(root->edges[i]){
len=root->edges[i]->to-root->edges[i]->from+1;
if(root->edges[i]->node){
ret=root->edges[i]->node->x;
t2=root->edges[i]->node->count;
}
else{
ret=0;
if(val)
t2=1;
else
t2=0;
}
t1=0;
if(ret){
if(val!=0)
t1+=len/2;
if(val!=1)
t1+=(len-1)/2;
}
else{
if(val!=1)
t1+=len/2;
if(val!=0)
t1+=(len-1)/2;
}
if(KK+t1+t2<K)
KK+=t1+t2;
else if(KK+t1<K){
KK+=t1;
for(j=root->edges[
i]->from;j<=root->edges[i]->to;j++)
ans[idx+j-root->edges[i]->from]=b[j];
dfs4(idx+root->edges[
i]->to-root->edges[i]->from+1,root->edges[i]->node);
return;
}
else{
if((ret && len%2) || (!ret && len%2==0))
start=1;
else
start=0;
for(j=root->edges[i]->from;j<root->edges[i]->to;j++,start^=1){
ans[idx+j-root->edges[i]->from]=b[j];
if(val!=start){
if(KK+1==K){
ans[idx+j+1-root->edges[i]->from]=0;
printf("%s\n",ans);
return;
}
KK++;
}
}
return;
}
}
return;
}
void suffix_tree(st_node *root,char *str,int len){
int a_edge,a_len=0,remainder=0,need_insert,from,i;
st_node *a_node=root,*pre_node,*t_node;
st_edge *t_edge;
memset(root,0,sizeof(st_node));
for(i=0;i<len;i++){
need_insert=0;
pre_node=NULL;
remainder++;
if(i==len)
need_insert=1;
else if(a_len)
if(str[a_node->edges[
a_edge]->from+a_len]==str[i])
if(a_node->edges[
a_edge]->from+a_len==a_node->edges[a_edge]->to){
a_node=a_node->edges[a_edge]->node;
a_len=0;
}
else
a_len++;
else
need_insert=1;
else
if(a_node->edges[str[i]-MIN_C])
if(a_node->edges[
str[i]-MIN_C]->from==a_node->edges[str[i]-MIN_C]->to)
a_node=a_node->edges[str[i]-MIN_C]->node;
else{
a_edge=str[i]-MIN_C;
a_len=1;
}
else
need_insert=1;
if(need_insert)
for(;remainder>0;remainder--){
if(!a_len)
if(i==len){
a_node->edges[A_SIZE]=(st_edge*)malloc(sizeof(st_edge));
a_node->edges[A_SIZE]->suffix_index=i-remainder+1;
a_node->edges[A_SIZE]->node=NULL;
}
else{
if(a_node->edges[str[i]-MIN_C]){
if(pre_node)
pre_node->suffix_link=a_node;
if(a_node->edges[
    str[i]-MIN_C]->from==a_node->edges[str[i]-MIN_C]->to)
a_node=a_node->edges[str[i]-MIN_C]->node;
else{
a_edge=str[i]-MIN_C;
a_len=1;
}
break;
}
t_edge=(st_edge*)malloc(sizeof(st_edge));
t_edge->from=i;
t_edge->to=len-1;
t_edge->suffix_index=i-remainder+1;
t_edge->node=NULL;
a_node->edges[str[i]-MIN_C]=t_edge;
t_node=a_node;
}
else{
if(i!=len && str[a_node->edges[
    a_edge]->from+a_len]==str[i]){
if(pre_node)
pre_node->suffix_link=a_node;
if(a_node->edges[a_edge]->from+a_len==a_node->edges[
    a_edge]->to){
a_node=a_node->edges[a_edge]->node;
a_len=0;
}
else
a_len++;
break;
}
t_node=(st_node*)malloc(sizeof(st_node));
memset(t_node,0,sizeof(st_node));
t_edge=(st_edge*)malloc(sizeof(st_edge));
t_edge->from=a_node->edges[a_edge]->from+a_len;
t_edge->to=a_node->edges[a_edge]->to;
t_edge->suffix_index=a_node->edges[a_edge]->suffix_index;
t_edge->node=a_node->edges[a_edge]->node;
from=a_node->edges[a_edge]->from;
a_node->edges[a_edge]->node=t_node;
a_node->edges[a_edge]->to=a_node->edges[
    a_edge]->from+a_len-1;
t_node->edges[str[t_edge->from]-MIN_C]=t_edge;
if(i==len){
t_node->edges[A_SIZE]=(st_edge*)malloc(sizeof(st_edge));
t_node->edges[A_SIZE]->suffix_index=i-remainder+1;
t_node->edges[A_SIZE]->node=NULL;
}
else{
t_edge=(st_edge*)malloc(sizeof(st_edge));
t_edge->from=i;
t_edge->to=len-1;
t_edge->suffix_index=i-remainder+1;
t_edge->node=NULL;
t_node->edges[str[i]-MIN_C]=t_edge;
}
}
if(pre_node)
pre_node->suffix_link=t_node;
pre_node=t_node;
if(a_node==root && a_len>0){
if(remainder>1)
a_edge=str[i-remainder+2]-MIN_C;
from=i-remainder+2;
a_len--;
}
else if(a_node!=root)
if(a_node->suffix_link)
a_node=a_node->suffix_link;
else
a_node=root;
while(a_len>0 && a_len>=a_node->edges[
    a_edge]->to-a_node->edges[a_edge]->from+1){
a_len-=a_node->edges[
    a_edge]->to-a_node->edges[a_edge]->from+1;
from+=a_node->edges[
    a_edge]->to-a_node->edges[a_edge]->from+1;
a_node=a_node->edges[a_edge]->node;
a_edge=str[from]-MIN_C;
}
}
}
return;
}

Two Strings Game C++ Solution

#include <iostream>
#include <ctime>
#include <fstream>
#include <cmath>
#include <cstring>
#include <cassert>
#include <cstdio>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <complex>
#include <utility>
#include <cctype>
#include <list>

using namespace std;

#define FORALL(i,a,b) for(int i=(a);i<=(b);++i)
#define FOR(i,n) for(int i=0;i<(n);++i)
#define FORB(i,a,b) for(int i=(a);i>=(b);--i)

typedef long long ll;
typedef pair<int,int> pii;
typedef map<int,int> mii;

#define pb push_back
#define mp make_pair

#define INF 1000000000000001000ll
#define MAXG 27
#define MAXN 600010

#define NO_ASSERT
#ifndef REGULAR_ASSERT
    #ifndef NO_ASSERT
        #undef assert
        #define assert sassert
    #else
        #undef assert
        #define assert(x)
    #endif
#endif


void sassert(bool x) {
    if (!x) { cout << "assertion failed!" << endl; exit(0); }
}

void add(ll& a, ll b) {
    if (a >= INF-b) a=INF;
    else a+=b;
}

void mul(ll& a, ll b) {
    if (b==0) a=0;
    else if (a >= (INF+b-1)/b) a = INF;
    else a *= b;
}


struct my_map {
    int s[26];
    my_map() { memset(s,-1,sizeof(s)); }
    int count(int idx) { return s[idx-'a'] >= 0; }
    void clear() { memset(s,-1,sizeof(s)); }
    
    int& operator[](int idx) {
        idx -= 'a';
        if (s[idx] < 0) s[idx] = 0;
        return s[idx];
    }
};

// a Suffix-Automaton data structure over a string S
// It is "the smallest DFA which accepts all suffixes of S".
// Fast linear time construction (constant is like 5 at worst).
// based on http://e-maxx.ru/algo/suffix_automata. Originally by Blumer et al
// Code under the Public DomainS
struct state {
  // Modified for the present problem (Two Strings Game, HackerRank 20/20 Feb 2014 )
  // Includes grundy numbers (i.e.: the nim-sum)
  // Turns out, the nim-sums work nicely for Suffix Automata! (each state is a node)
  int len, link, grundy;
  ll paths[MAXG];        // the # of paths from this state downward to any node with grundy g
  my_map next;
  state(int a, int b) {
    len=a; link=b; next.clear();
    grundy = 0; memset(paths,0,sizeof(paths));
  }
  state() { len=link=0; next.clear(); memset(paths,0,sizeof(paths)); }
};

// add next (alphabetic) character c to the dfa Q (an array of states).
// K is the number of states. tail is the state representing the entire string
void sa_add(char c, state* Q, int& K, int& tail) {
  assert(K<MAXN - 5);
  int x,y, cur = K++;
  Q[cur].len = Q[tail].len+1; Q[cur].link = -1;
  for(x=tail; x>=0 && !Q[x].next.count(c); x = Q[x].link)
    Q[x].next[c] = cur;
  if (x<0) Q[cur].link = 0;
  else {
    y = Q[x].next[c];
    if (Q[y].len == Q[x].len + 1) {
      Q[cur].link = y;
    } else {
      int cl = K++;  // clone
      Q[cl].len = Q[x].len+1; Q[cl].link = Q[y].link;//state(Q[x].len + 1, Q[y].link);
      Q[cl].next = Q[y].next;
      for(; x>=0 && Q[x].next[c]==y; x=Q[x].link)
        Q[x].next[c] = cl;
      Q[y].link = Q[cur].link = cl;
    }
  }
  tail = cur;
}

#define MAXL 300002
bool vis[MAXN];
bool mex[MAXN][MAXG];        // a temporary array to store reachable grundy numbers (and to find the mex)

void dfs(int i, state* Q) {
    assert(i<MAXN && i>=0);
    //if (vis[i]) return;
    //vis[i] = true;
    
    //cout << i << endl;
    
    FOR(g,MAXG) mex[i][g] = 0, Q[i].paths[g] = 0;
    FORALL(c,'a','z') if (Q[i].next.count(c)) {
        int j = Q[i].next[c];
        //assert(vis[j]);
        //dfs(j,Q);
        mex[i][Q[j].grundy] = true;
    }
    
    Q[i].grundy = -1;
    FOR(g,MAXG) {
        if (!mex[i][g]) {
            Q[i].grundy = g;
            break;
        }
    }
    
    assert(Q[i].grundy >= 0);
    
    FORALL(c,'a','z') if (Q[i].next.count(c)) {
        int j = Q[i].next[c];
        FOR(g,MAXG) {
            add(Q[i].paths[g], Q[j].paths[g]);
        }
    }
    add(Q[i].paths[Q[i].grundy],1);
    assert(Q[i].grundy <= 26);
}

// construct the suffix automaton for the string t
// store the resulting states into the array Q;
// return the number of states. Will be no more than 2|t| + 2 (ish?)
int sa_construct(char* t, state* Q) {
  int n = strlen(t), first[n+1], next[2*n-1], K = 1, tail = 0;
  Q[0].len = 0; Q[0].link = -1; Q[0].next.clear();
  FOR(i,n) sa_add(t[i],Q,K,tail);
  
  // do a dfs / dp to compute grundy numbers (nim-sums)
  // also compute all paths that lead to each grundy number starting from any node
  //memset(vis,0,sizeof(vis));
  FORALL(i,0,n) first[i] = -1;
  FOR(i,K) next[i] = first[Q[i].len], first[Q[i].len] = i;
  FORB(k,n,0) for(int i = first[k]; i>=0; i = next[i])
    dfs(i,Q);
    //Q[Q[i].link].occs += Q[i].occs;
  
  
  //FORB(i,K-1,0) dfs(i,Q);
  return K;
}

// Uses for suffix automata (treat it exactly like a trie)
// All of these run in O(|p|) time!!!!

// find pattern p in the search text (i.e.: suffix automaton Q)
// return true if p is found in the string
bool sa_find(state* Q, char* p) {
  for(int s=0; *p && Q[s].next.count(*p); s = Q[s].next[*p], p++);
  return ((*p) == 0);  // reached end of string with no errors! we found it
}

// find a pattern p and return its grundy number.
// return -1 if not found
int sa_grundy(state* Q, const char* p) {
  int s;
  for(s=0; *p && Q[s].next.count(*p); s = Q[s].next[*p], p++);
  return (((*p)==0)?Q[s].grundy:-1);
}

state Qa[MAXN], Qb[MAXN];
char A[MAXL], B[MAXL];
char a[MAXL], b[MAXL];

// number of paths in b (starting from state s) that
//     lead to a grundy number not equal to <grun>
//ll Q0P[MAXG];
inline ll get_winning(int grun, state* Q, int s=0) {
    ll ans = 0;
    FOR(g,MAXG) if (g != grun){
        //if (s == 0) add(ans,Q0P[g]);
        /*else*/
        add(ans,Q[s].paths[g]);
    }
    return ans;
}

int main () {
    int N,M;
    ll K;
    cin >> N >> M >> K;
    //FOR(i,N) A[i] = 'a'+(i%2);
    //FOR(i,N) B[i] = 'b'+(i%2);
    //FOR(i,N) A[i] = 'a';
    //FOR(j,M) B[j] = 'b';
    //A[N-1] = 'b';
    //B[N-1] = 'a';
    scanf("%s%s",A,B);
    //N = strlen(A);
    //M = strlen(B);
    
    sa_construct(A,Qa);
    sa_construct(B,Qb);
    //FOR(g,MAXG) Q0P[g] = Qa[0].paths[g];
    //assert(Kb < MAXN);
    
    
    //assert(Ka < MAXN);
    //int Kb = sa_construct(B,Qb);
    //assert(Ka < MAXN && Kb < MAXN);
    
    //cout << sizeof(Qa) << " " << Ka  << endl;
    //return 0;
    
    
    ll total_winning = 0;
    FOR(g,MAXG) {
        ll tmp = Qa[0].paths[g];
        mul(tmp,get_winning(g,Qb));
        add(total_winning, tmp);
    }
    
    if (total_winning < K) {
        cout << "no solution" << endl;
        return 0;
    }

    // we can now assume there is a solution
    // first construct a
    ll num_winning, total_here, tmp, x;
    int len = 0;
    int s = 0, news;            // current state in the suffix automaton
    while(K) {
        // check the empty case
        num_winning = get_winning(Qa[s].grundy,Qb);
        if (num_winning >= K) break;
        
        // otherwise, need to add another character
        // note: we keep the old "num_winning" (counting the number of possibilities we've skipped)
        //bool found = false;
        FORALL(c,'a','z') {
            if (!Qa[s].next.count(c)) continue;
            news = Qa[s].next[c];
            total_here = 0;
            FOR(g,MAXG) {
                tmp = Qa[news].paths[g];
                mul(tmp,get_winning(g,Qb));
                add(total_here, tmp);
            }

            x = num_winning; add(x,total_here);
            if (x >= K) {
                K -= num_winning;
                a[len++] = c;
                //found = true;
                s = news;
                break;
            } else {
                num_winning += total_here;
            }
        }
        
        // eventually it will find something (since we assumed there is a solution)
        //assert(found);
    }
    
    // now construct b
    int a_grundy = Qa[s].grundy;
    //sa_construct(B,Qa);
    len = 0;
    s = 0;            // current state in the suffix automaton
    while(K) {
        // check the empty case
        num_winning = ((Qb[s].grundy == a_grundy)?0:1);
        if (num_winning >= K) { K -= 1; break; }
        
        // now we push a new character to b
        // note: we keep the old "num_winning" (counting the number of possibilities we've skipped)
        //bool found = false;
        FORALL(c,'a','z') {
            if (!Qb[s].next.count(c)) continue;
            news = Qb[s].next[c];
            tmp = get_winning(a_grundy, Qb, news);
            if (num_winning + tmp >= K) {
                K -= num_winning;
                b[len++] = c;
            //    found = true;
                s = news;
                break;
            } else {
                num_winning += tmp;
            }
        }
        
        // eventually it will find something (since we assumed there is a solution
        //assert(found);
    }
    
    assert(!K);
    printf("%s\n%s\n",a,b);
    //cout << a << endl;
    //cout << b << endl;
}

Two Strings Game Java Solution

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();
  }
}
c C# C++ HackerRank Solutions java javascript python

Leave a Reply