Algorithm
Problem Name: 2 AD-HOC - beecrowd | 2070
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/2070
Counting MadSequences
By Thalyson Nepomuceno, UEC 
Brazil
Timelimit: 1
Given an integer K and 3 sequences S1, S2 and S3, we call MadSequence, a sequence consisting of positive integers smaller or equal to K and that is not subsequence of S1, S2 or S3. Remember that a subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements.
For example, for K = 3, S1 = <1, 2, 3, 1, 2>, S2 = <2, 3, 1, 2> and S3 = <3, 1, 2, 3, 1, 2> , all possible sequences of size 1 (<1> <2> and <3>) are not MadSequences, because are subsequences of S1, S2 and S3.
Analyzing all possible sequences of length 2 for K = 3:
- <1, 1> is not subsequence of S2, then <1, 1> is a MadSequence;
- <1, 2> is subsequence of S1, S2 and S3;
- <1, 3> is not subsequence of S2, then <1, 3> is a MadSequence;
- <2, 1> is subsequence of S1, S2 and S3;
- <2, 2> is subsequence of S1, S2 and S3;
- <2, 3> is subsequence of S1, S2 and S3;
- <3, 1> is subsequence of S1, S2 and S3;
- <3, 2> is subsequence of S1, S2 and S3;
- <3, 3> is not subsequence of S1 and S2, then <3, 3> is a MadSequence;
Thus, the size of the smallest MadSequence, for this example, is equal to 2. We also conclude that there are 3 MadSequences of length 2.
Input
The first line of input consists of four integers K, L1, L2 and L3 represent, respectively, the integer K and sizes of S1, S2 and S3 (1 ≤ K ≤ 20 and 1 ≤ L1, L2 and L3 ≤ 200). The second line consists of L1 integers, representing the elements of S1. The third line consists of L2 integers, representing the elements of S2. The fourth line consists of L3 integers, representing the elements of S3. Assume that all elements of the sequences S1, S2 and S3 are positive integers smaller than or equal to K.
Output
The integer M is the smallest size of a MadSequence for the input data. Print a single line containing M and the amount of MadSequences with M size.
| Input Sample | Output Sample |
|
3 5 4 6 |
2 3 |
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int k;
int l[3];
int s[3][205];
int g[3][205][25];
int m[205][205][205];
int cc[205][205][205];
typedef struct{
int a, b, c;
} tri;
typedef struct{
int first;
int second;
} pair;
pair bfs();
int main(int argc, char **argv)
{
int i, j, w;
scanf("%d %d %d %d", &k, &l[0], &l[1], &l[2]);
for (i = 0; i < 3; ++i)
for (j = 1; j < = l[i]; ++j)
scanf("%d", &s[i][j]);
for (i = 0; i < 3; ++i)
for (j = 1; j < = l[i]; ++j)
for (w = 0; w < = k; ++w)
g[i][j][w] = l[i] + 1;
for (i = 0; i < 3; ++i)
for (j = 1; j < = l[i]; ++j)
for (w = j - 1; w >= 0; --w)
{
g[i][w][s[i][j]] = j;
if (s[i][w] == s[i][j])
break;
}
pair ans = bfs();
printf("%d %d\n", ans.first, ans.second);
return 0;
}
pair bfs()
{
int qts = 0;
int i, s, e;
int menor = 1000000;
tri queue[100000];
s = e = 0;
tri tmp = { 0 };
queue[e++] = tmp;
memset(m, 0, sizeof(m));
memset(cc, 0, sizeof(cc));
cc[0][0][0] = 1;
while (s < e)
{
int p1 = queue[s].a;
int p2 = queue[s].b;
int p3 = queue[s].c;
s++;
if (menor < = m[p1][p2][p3])
break;
for (i = 1; i < = k; ++i)
{
if (g[0][p1][i] == l[0] + 1 || g[1][p2][i] == l[1] + 1 || g[2][p3][i] == l[2] + 1)
menor = m[p1][p2][p3] + 1, qts += cc[p1][p2][p3];
if (qts)
continue;
int pp1 = g[0][p1][i];
int pp2 = g[1][p2][i];
int pp3 = g[2][p3][i];
if (!m[pp1][pp2][pp3])
{
m[pp1][pp2][pp3] = m[p1][p2][p3] + 1;
cc[pp1][pp2][pp3] = cc[p1][p2][p3];
tri tmp = {pp1, pp2, pp3};
queue[e++] = tmp;
}
else if (m[pp1][pp2][pp3] == m[p1][p2][p3] + 1)
cc[pp1][pp2][pp3] += cc[p1][p2][p3];
}
}
pair ans;
ans.first = menor;
ans.second = qts;
return ans;
}
Input
1 2 3 1 2
2 3 1 2
3 1 2 3 1 2
Output