HackerRank Alien Languages Problem Solution
In this post, we will solve HackerRank Alien Languages Problem Solution.
Sophia has discovered several alien languages. Suprisingly, all of these languages have an alphabet, and each of them may contain thousands of characters! Also, all the words in a language have the same number of characters in it.
However, the aliens like their words to be aesthetically pleasing, which for them means that for the ith letter of an n-letter alphabet (letters are indexed 1… n):
if 2i > n. then the ith letter may be the last letter of a word, or it may be immediately followed by any letter, including itself.
if 2i 2i.
Sophia wants to know how many different words exist in this language. Since the result may be large, she wants to know this number, modulo 100000007(10 power 8 +7).
Input Format
The first line contains t, the number of test cases. The first line is followed by t lines, each line denoting a test case. Each test case will have two space-separated integers n. m which denote the number of letters in the language and the length of words in this language respectively.
Sample Input
3
1 3
2 3
3 2
Sample Output
1
3
6Explanation
For the first test case, there’s one letter (‘a’) and all the words consist of 3 letters. There’s only one possibility which is “aaa”.
For the second test case, there are two letters (‘a’ and ‘b’) and all the words are of 3 letters. The possible strings are “abb”, “bab”. & “bbb”. The words can end only with ‘b’ because 2. index(b) = 2.2 > 2 and for ‘a’, it’s 2 index(a) = 2.1 ≤ 2. “aab” is not allowed because ‘a’ can not be followed immediately by ‘a’. For a word of length 4 and alphabet of size 2, “abab” would be allowed.
For the third test case, there are three letters (‘a’, ‘b’ and ‘C’) and all of the words are 2 letters. The words can only end with ‘b’ or ‘c’. The possible words are “ab”, “ac”, “bb”, “cc”, “bc”, “cb”.
Alien Languages C Solution
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
int dp[2][100001];
long long material[17];
int number[500001];
int reduce(long long value) {
while(value < 0)
value += 100000007;
return value % 100000007;
}
int main() {
int t, n, m, middle, i, j, sum, index = 0, first, second, max_length;
long long result;
scanf("%d", &t);
for (; t > 0; --t) {
scanf("%d %d", &n, &m);
memset(dp, 0, sizeof(dp));
memset(material, 0, sizeof(material));
middle = n / 2;
for (i = middle + 1; i <= n; ++i) {
dp[index][i] = 1;
}
for (i = 2; i <= m + 1; ++i) {
index = 1 - index;
if (i == 2) {
sum = n - middle;
} else {
sum = 0;
for (j = 1; j <= middle; ++j) {
if (dp[1 - index][j] == 0) {
break;
}
sum += dp[1 - index][j];
sum = reduce(sum);
}
}
if (sum == 0) {
break;
}
material[i - 1] = sum;
for (j = 1; j <= middle; ++j) {
first = (j << 1) - 1;
second = first - 1;
sum -= dp[1 - index][first] + dp[1 - index][second];
sum = reduce(sum);
dp[index][j] = sum;
}
for (j = middle + 1; j <= n; ++j) {
dp[index][j] = 0;
}
}
max_length = i - 2;
number[0] = 1;
for (i = 1; i <= m; ++i) {
result = 0;
for (j = 1; j <= max_length && j <= i; ++j) {
result += material[j] * number[i - j];
result = reduce(result);
}
number[i] = result;
}
printf("%d\n", number[m]);
}
return 0;
}
Alien Languages C++ Solution
#include <bits/stdc++.h>
using namespace std;
typedef long long ULL;
ULL MOD = 100000007;
int N, M;
void Update(vector<ULL> &bit, int x, ULL val)
{
for(x++; x < bit.size(); x += x&-x)
{
bit[x] = (bit[x] + val) % MOD;
}
}
ULL Query(vector<ULL> &bit, int x)
{
ULL res = 0;
for(x++; x > 0; x -= x&-x)
{
res = (res + bit[x]) % MOD;
}
return res;
}
ULL Solve()
{
if(M == 1)
{
return N / 2;
}
ULL top = 1;
ULL half = (N / 2) + (N % 2);
ULL DP[half + 3] = {0};
ULL prev[half + 3] = {0};
DP[half + 2] = half;
prev[1] = 1;
// prev[1]
for(int size = 2; size <= M; size++)
{
ULL high = DP[half + 2];
ULL add = DP[half / 2 + 2] - DP[half / 4];
cerr << size << ": " << high << " (" << add << ")\n";
int i;
for(i = 1; 2 * i <= N; i++)
{
ULL a;
if(2 * i > half)
{
ULL diff = half - i;
a = (N % 2 == 0)
? (diff + 1) + ((top * 2) * diff) % MOD
: ((top * 2) * diff) % MOD;
a = (a + (top * 2 * (diff * (diff - 1) / 2)) % MOD) % MOD;
cerr << "\t[" << i << "]: " << a << "\n";;
DP[i + 1] = (DP[i] + a) % MOD;
i++;
break;
}
else
{
a = DP[half + 2];
// if(a * 2 <= half / 2 + 1)
a -= DP[i * 2];
// else a -= DP[i + 2];
}
DP[i + 1] = (DP[i] + a) % MOD;
cerr << "\t[" << i << "]: " << a << " (" << add << ")\n";;
}
prev[size] = top;
top = high;
DP[half + 2] = (DP[i] + (high * half)) % MOD;
// DP[i + 2] = DP[i + 1];
}
ULL res = DP[half + 2];
return (res < 0) ? res + MOD : res;
}
ULL SOLVE()
{
if(M == 1)
{
return N / 2;
}
ULL res = 0;
// vector<vector<ULL>> DP(M + 1, vector<ULL>(N + 2, 0));
vector<ULL> prev(N + 2, 0);
for(ULL i = 1; i <= N; i++)
{
// break;
if(i * 2 > N) Update(prev, i, 1);
}
// Update(prev, N / 2 + 1, N / 2 + 1);
ULL top = 1;
ULL half = N / 2 + 1;//(N % 2);
for(int size = 2; size <= M; size++)
{
vector<ULL> next(N + 2, 0);
ULL high = Query(prev, N);
cerr << size << ": " << high << "\n";
for(int i = 1; i <= N; i++)
{
ULL a;
if(2 * i <= N)
{
a = (high - Query(prev, i * 2 - 1)) % MOD;
Update(next, i, a);
}
else
{
a = high;
Update(next, i, a);
}
cerr << "\t[" << i << "]: " << a << "\n";;
}
prev = move(next);
}
res = Query(prev, N);
if(res < 0) res += MOD;
return res;
}
/*
1
_ 2
*/
/*
9
1:
5
6
7
8
9
2:
1 5
2 5
1 6
2 6
3 6
1 7
2 7
3 7
1 8
2 8
3 8
4 8
1 9
2 9
3 9
4 9
3:
1 2 5
1 2 6
1 3 6
1 2 7
1 3 7
1 2 8
1 3 8
1 4 8
2 4 8
1 2 9
1 3 9
1 4 9
2 4 9
4:
1 2 4 8
1 2 4 9
1
_ 2 3 4|5 6 7 8 9
2
_ _ _ 4|5 6 7 8 9
3
_ _ _ _|_ 6 7 8 9
4
_ _ _ _|_ _ _ 8 9
*/
ULL _Solve()
{
vector<vector<ULL>> DP(20, vector<ULL>(N + 1, 0));
vector<ULL> counts(20, 0);
for(int i = N / 2 + 1; i <= N; i++)
{
DP[1][i] = DP[1][i - 1] + 1;
}
counts[1] = DP[1][N];
ULL p = 2;
for(int size = 2; size < 20; size++)
{
// cerr << size << "\n";
for(int j = 1; j <= N; j++)
{
if(j * 2 > N)
{
DP[size][j] = (DP[size][j - 1]) % MOD;
continue;
}
ULL sum = DP[size - 1][N] - DP[size - 1][j * 2 - 1];
DP[size][j] = (DP[size][j - 1] + sum) % MOD;
}
counts[size] = DP[size][N];
continue;
cerr << size << ": " << counts[size] << "\n";
for(int j = 1; j <= N; j++)
{
if(DP[size][j])
{
cerr << "\t" << j << ": " << DP[size][j] - DP[size][j - 1] << "\n";
}
}
p *= 2;
}
vector<ULL> result(M + 1, 0);
result[0] = 1;
for(int size = 1; size <= M; size++)
{
for(int i = 1; i < 16 && size - i >= 0; i++)
{
result[size] = (result[size] + result[size - i] * counts[i]) % MOD;
}
}
return (result[M] < 0) ? result[M] + MOD : result[M];
return 0;
}
int main()
{
int t;
cin >> t;
while(t--)
{
cin >> N >> M;
cout << _Solve() << "\n";
continue;
cout << Solve() << "\n";
cout << SOLVE() << "\n";
// memo = vector<vector<ULL>>(M + 1, vector<ULL>(N + 1, -1));
// cout << Naive(0, N) << "\n";
}
}
// 5000
// 43750000
// 29143101
// 96187357
// 95307470Alien Languages C Sharp Solution
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
namespace Solution {
class Solution {
const ulong prime = 100000007UL;
static void Main(string[] args) {
int t = Convert.ToInt32(Console.ReadLine());
for(int i = 0; i < t; ++ i)
{
string[] str = Console.ReadLine().Split(' ');
ulong n = Convert.ToUInt64(str[0]);
ulong m = Convert.ToUInt64(str[1]);
Console.WriteLine(Solve(n,m));
}
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
}
static ulong Solve(ulong n, ulong m)
{
ulong[,] arr = new ulong[2, n + 1];
var k = n % 2 + n / 2;
var fac = new List<ulong> { k };
for (var i = 1UL; i <= n / 2; ++i) arr[0, i] = (2 * i <= n / 2) ? k : n + 1 - 2 * i;
k = n / 2;
for ( ulong i = 0UL; k > 0 ;k /=2, i++)
{
ulong val = 0, q = i % 2;
for (ulong j = k; j > 1; -- j)
{
val = (val + arr[q, j]) % prime;
arr[1 - q, j / 2] = val;
}
fac.Add((arr[0, 1] + arr[1, 1]) % prime);
arr[q, 1] = 0;
}
ulong[] res = new ulong[fac.Count];
res[0] = 1;
for( ulong i = 0; i < m; ++ i)
{
ulong ans = 0;
for (int j = 0; j < res.Length; ++j) ans += (res[j] * fac[j]) % prime;
Array.ConstrainedCopy(res, 0, res, 1, res.Length - 1);
res[0] = ans % prime;
}
return res[0];
}
}
}Alien Languages Java Solution
import java.io.*;
import java.math.*;
import java.text.*;
import java.util.*;
import java.util.regex.*;
public class Solution {
static final long MOD = 100_000_007;
static int alienLanguages(int n, int m) {
int[][] t = new int[n + 1][20];
int nb = n / 2;
for (int i = n; i > nb; i--) {
t[i][0] = 1;
}
int[] words = new int[m + 1];
int[] mult = new int[20];
for (int j = n, k = 0; j > 0; j /= 2, k++) {
long d = 0;
for (int i = n; i > 0; i--) {
d = (d + t[i][k]) % MOD;
t[i / 2][k + 1] = (int) d;
}
for (int i = n; i > 0; i--) {
mult[k] = (int)((mult[k] + t[i][k]) % MOD);
}
}
words[0] = 1;
for (int i = 1; i <= m; i++) {
long d = words[i - 1];
for (int j = 0; mult[j] > 0 && i + j <= m; j++) {
words[i + j] = (int)((words[i + j] + (d * mult[j]) % MOD) % MOD);
}
}
return words[m];
}
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 t = Integer.parseInt(st.nextToken());
for (int i = 0; i < t; i++) {
st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
int result = alienLanguages(n, m);
bw.write(String.valueOf(result));
bw.newLine();
}
br.close();
bw.close();
}
}Alien Languages Python Solution
mod = 10**8 + 7
for cas in range(int(input())):
n, m = map(int, input().strip().split())
v = [2*i > n for i in range(n+1)]
for i in range(n-1,-1,-1):
v[i] += v[i + 1]
c = []
while v[1]:
c.append(v[1])
for i in range(1,n//2+1):
v[i] = v[2*i]
for i in range(n//2+1,n+1):
v[i] = 0
for i in range(n-1,-1,-1):
v[i] = (v[i] + v[i + 1]) % mod
f = [1] + [0]*(len(c)-1)
for k in range(1,m+1):
f = [sum(F * C for F, C in zip(f, c)) % mod] + f[:-1]
print(f[0])
