Shashank and the Palindromic Strings
Problem Statement :
Shashank loves strings, but he loves palindromic strings the most. He has a list of n strings, A = [a0,a1,...,an-1] , where each string, ai, consists of lowercase English alphabetic letters. Shashank wants to count the number of ways of choosing non-empty subsequences s0,s1,s2,...,sn-1 such that the following conditions are satisfied: 1.s0 is a subsequence of string a0, s1 is a subsequence of string a1, s2 is a subsequence of string a2, ..., and sn-1 is a subsequence of string . 2. s-+s1+s2+ ...+ sn-1 is a palindromic string, where + denotes the string concatenation operator. You are given q queries where each query consists of some list, A. For each query, find and print the number of ways Shashank can choose n non-empty subsequences satisfying the criteria above, modulo 10^9 + 7, on a new line. Note: Two subsequences consisting of the same characters are considered to be different if their characters came from different indices in the original string. Input Format The first line contains a single integer, q, denoting the number of queries. The subsequent lines describe each query in the following format: The first line contains an integer, n, denoting the size of the list. Each line i of the n subsequent lines contains a non-empty string describing ai. Constraints 1 <= q <= 50 1 <= n <= 50 Σ |ai| <= 1000 over a test case. For 40% of the maximum score: 1 <= n <= 5 Σ |ai| <= 250 over a test case. Output Format For each query, print the number of ways of choosing non-empty subsequences, modulo 10^9 + 7, on a new line.
Solution :
Solution in C :
In C++ :
#include <bits/stdc++.h>
using namespace std;
#define vec vector
#define ALL(x) (x).begin(), (x).end()
#define mp make_pair
#define mt make_tuple
typedef pair< int, int > pii;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
int const inf = 1000 * 1000 * 1000;
ll const inf64 = 1ll * inf * inf;
int const mod = inf + 7;
inline int sum(int a, int b) { return (a + b) % mod; }
inline int raz(int a, int b) { return ((a - b) % mod + mod) % mod; }
inline int mul(int a, int b) { return (1ll * a * b) % mod; }
bool solve() {
int n;
cin >> n;
vec< string > a(n);
string text = "";
for(int i = 0;i < n;i++) cin >> a[i], text += a[i];
int sz = (int)text.size();
vec< int > id(sz);
for(int j = 0, i = 0;i < n;i++) {
for(int iter = 0;iter < (int)a[i].size();iter++) {
id[j++] = i;
}
}
vec< int > le(n, inf);
vec< int > ri(n,-inf);
for(int i = 0;i < sz;i++) {
le[id[i]] = min(le[id[i]], i);
ri[id[i]] = max(ri[id[i]], i);
}
vec< vec< int > > dp(sz, vec< int >(sz));
vec< vec< int > > sm(sz, vec< int >(sz));
for(int l = sz - 1;l >= 0;l--) {
for(int r = l;r < sz;r++) {
if(r > 0) sm[l][r] = sum(sm[l][r], sm[l][r - 1]);
if(l + 1 < sz) sm[l][r] = sum(sm[l][r], sm[l + 1][r]);
if(r > 0 && l + 1 < sz) sm[l][r] = raz(sm[l][r], sm[l + 1][r - 1]);
if(r < l || text[l] != text[r]) continue;
dp[l][r] = id[r] - id[l] <= 1;
int tl1, tr1, tl2, tr2;
tl1 = l + 1;
tr1 = min(r - 1, id[l] + 1 < n ? ri[id[l] + 1] : ri[id[l]]);
tl2 = max(l + 1, id[r] ? le[id[r] - 1] : le[id[r]]);
tr2 = r - 1;
if(tl1 <= tr1 && tl2 <= tr2) {
dp[l][r] = sum(dp[l][r], sm[tl1][tr2]);
if (tl2 > 0) dp[l][r] = raz(dp[l][r], sm[tl1][tl2 - 1]);
if (tr1 + 1 < sz) dp[l][r] = raz(dp[l][r], sm[tr1 + 1][tr2]);
if (tr1 + 1 < sz && tl2 > 0) dp[l][r] = sum(dp[l][r], sm[tr1 + 1][tl2 - 1]);
}
sm[l][r] = sum(sm[l][r], dp[l][r]);
}
}
int res = 0;
for(int l = 0;l < (int)a[0].size();l++) {
for(int r = sz - 1;r >= l && r >= sz - (int)a[n - 1].size();r--) {
res = sum(res, dp[l][r]);
}
}
cout << res << "\n";
return true;
}
int main() {
int T;
cin >> T;
while(T--) solve();
return 0;
}
In Java :
import java.io.*;
import java.math.*;
import java.text.*;
import java.util.*;
import java.util.regex.*;
public class Solution {
final static int MODE = 1000000007;
/*
* Complete the palindromicStrings function below.
*/
static int palindromicStrings(int[] a, char[] cc) {
final int N = cc.length;
int[][] dp = new int[6*N][N];
int[] ids = new int[N];
int t=a[0]==1?0:1;
for(int i=1;i<N;++i){
if(t==0){
ids[i]=ids[i-1]+1;
}else{
ids[i]=ids[i-1];
}
++t;
if(a[ids[i]]==t)t=0;
}
int[] st = new int[6];
for(int i=1;i<6;++i)st[i]=i*N;
for(int i=N-1;i>=0;--i){
dp[st[5]+i][i]=dp[st[4]+i][i]=dp[i][i]=1;
dp[st[3]+i][i]=dp[st[2]+i][i]=dp[st[1]+i][i]=2;
for(int j=i+1;j<N;++j){
if(ids[j]==ids[j-1]){
dp[st[5]+i][j]=dp[st[5]+i][j-1];
dp[st[4]+i][j]=dp[st[4]+i][j-1];
}else{
dp[st[5]+i][j]=dp[st[4]+i][j-1];
}
if(cc[i]==cc[j]){
if(i+1==j){
++dp[st[5]+i][j];
++dp[st[4]+i][j];
}else{
int k=0;
if(ids[i]==ids[i+1])k+=2;
if(ids[j]==ids[j-1])k+=1;
dp[st[5]+i][j]=(dp[st[5]+i][j]+dp[st[k]+i+1][j-1])%MODE;
dp[st[4]+i][j]=(dp[st[4]+i][j]+dp[st[k]+i+1][j-1])%MODE;
}
}
dp[st[1]+i][j]=dp[st[3]+i][j]=dp[st[5]+i][j];
dp[st[0]+i][j]=dp[st[2]+i][j]=dp[st[4]+i][j];
if(ids[i]==ids[i+1]){
dp[st[3]+i][j]=(dp[st[3]+i][j]+dp[st[3]+i+1][j])%MODE;
dp[st[2]+i][j]=(dp[st[2]+i][j]+dp[st[2]+i+1][j])%MODE;
dp[st[1]+i][j]=(dp[st[1]+i][j]+dp[st[1]+i+1][j])%MODE;
dp[st[0]+i][j]=(dp[st[0]+i][j]+dp[st[0]+i+1][j])%MODE;
}else{
dp[st[3]+i][j]=(dp[st[3]+i][j]+dp[st[1]+i+1][j])%MODE;
dp[st[2]+i][j]=(dp[st[2]+i][j]+dp[st[0]+i+1][j])%MODE;
}
}
}
return dp[0][N-1];
}
private static final Scanner scanner = new Scanner(System.in);
public static void main(String[] args) throws Exception {
BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
long t = System.currentTimeMillis();
int q = scanner.nextInt();
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])*");
for (int qItr = 0; qItr < q; qItr++) {
int aCount = scanner.nextInt();
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])*");
int[] a = new int[aCount];
StringBuilder sb = new StringBuilder();
for (int aItr = 0; aItr < aCount; aItr++) {
String aItem = scanner.nextLine();
//scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])*");
a[aItr] = aItem.length();
sb.append(aItem);
}
int result = palindromicStrings(a, sb.toString().toCharArray());
bufferedWriter.write(String.valueOf(result));
bufferedWriter.newLine();
}
bufferedWriter.close();
scanner.close();
//Thread.sleep(3800);
System.out.println(System.currentTimeMillis()-t);
}
}
In C :
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#define md 1000000007
char cv[1001], fv[1000], lv[1000], gv[1000];
unsigned int mv[1000 * 1000 * 4];
int m;
void readInput() {
int i, j, k, l, n;
char *s;
for (i = 0; i < 1000; ++i)
{
fv[i] = 0;
lv[i] = 0;
}
s = cv;
k = 0;
scanf("%d", &n);
for (i = 0; i < n; ++i)
{
scanf("%s", s);
l = strlen(s);
fv[k] = 1;
lv[k + l - 1] = 1;
for (j = 0; j < l; ++j)
{
gv[k + j] = i;
}
k += l;
s += l;
}
m = strlen(cv);
}
int ix(int i, int j, int oi, int oj) {
return (i * m * 4) + (j * 4) + (oi * 2) + oj;
}
unsigned int f(int i, int j, int oi, int oj) {
if (i == j)
{
return (oi || oj) ? 2 : 1;
}
if (j < i)
{
return 1;
}
if (gv[i] == gv[j])
{
oi = oi || oj;
oj = oi;
}
return mv[ix(i, j, oi, oj)];
}
void run() {
int l, i, j, p;
int il, jf, oi, oj, oi1, oj1, b1, b2;
unsigned int c;
readInput();
for (l = 2; l <= m; ++l)
{
for (i = 0; i <= m - l; ++i)
{
j = i + l - 1;
for (p = 0; p < 4; ++p)
{
if (p == 0 || p == 3 || gv[i] < gv[j])
{
il = lv[i];
jf = fv[j];
oi = p & 1;
oj = p >> 1;
c = 0;
b1 = oi || !il;
b2 = oj || !jf;
oi1 = !il && oi;
oj1 = !jf && oj;
if (b1)
{
c += f(i + 1, j, oi1, oj);
}
if (b2)
{
c += f(i, j - 1, oi, oj1);
}
if (b1 && b2 && (l > 2 || oi || oj))
{
c += md - f(i + 1, j - 1, oi1, oj1);
}
if (cv[i] == cv[j])
{
c += f(i + 1, j - 1, !il, !jf);
}
//printf("%d %d %d %d %u\n", i, j, oi, oj, c % md);
mv[ix(i, j, oi, oj)] = c % md;
}
}
}
}
printf("%u\n", mv[ix(0, m - 1, 0, 0)]);
}
int main() {
int q, i;
scanf("%d", &q);
for(i = 0; i < q; ++i) {
run();
}
return 0;
}
View More Similar Problems
Array-DS
An array is a type of data structure that stores elements of the same type in a contiguous block of memory. In an array, A, of size N, each memory location has some unique index, i (where 0<=i<N), that can be referenced as A[i] or Ai. Reverse an array of integers. Note: If you've already solved our C++ domain's Arrays Introduction challenge, you may want to skip this. Example: A=[1,2,3
View Solution →2D Array-DS
Given a 6*6 2D Array, arr: 1 1 1 0 0 0 0 1 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 An hourglass in A is a subset of values with indices falling in this pattern in arr's graphical representation: a b c d e f g There are 16 hourglasses in arr. An hourglass sum is the sum of an hourglass' values. Calculate the hourglass sum for every hourglass in arr, then print t
View Solution →Dynamic Array
Create a list, seqList, of n empty sequences, where each sequence is indexed from 0 to n-1. The elements within each of the n sequences also use 0-indexing. Create an integer, lastAnswer, and initialize it to 0. There are 2 types of queries that can be performed on the list of sequences: 1. Query: 1 x y a. Find the sequence, seq, at index ((x xor lastAnswer)%n) in seqList.
View Solution →Left Rotation
A left rotation operation on an array of size n shifts each of the array's elements 1 unit to the left. Given an integer, d, rotate the array that many steps left and return the result. Example: d=2 arr=[1,2,3,4,5] After 2 rotations, arr'=[3,4,5,1,2]. Function Description: Complete the rotateLeft function in the editor below. rotateLeft has the following parameters: 1. int d
View Solution →Sparse Arrays
There is a collection of input strings and a collection of query strings. For each query string, determine how many times it occurs in the list of input strings. Return an array of the results. Example: strings=['ab', 'ab', 'abc'] queries=['ab', 'abc', 'bc'] There are instances of 'ab', 1 of 'abc' and 0 of 'bc'. For each query, add an element to the return array, results=[2,1,0]. Fun
View Solution →Array Manipulation
Starting with a 1-indexed array of zeros and a list of operations, for each operation add a value to each of the array element between two given indices, inclusive. Once all operations have been performed, return the maximum value in the array. Example: n=10 queries=[[1,5,3], [4,8,7], [6,9,1]] Queries are interpreted as follows: a b k 1 5 3 4 8 7 6 9 1 Add the valu
View Solution →