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 BR 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
1 2 3 1 2
2 3 1 2
3 1 2 3 1 2

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;

}
Copy The Code & Try With Live Editor

Input

x
+
cmd
3 5 4 6
1 2 3 1 2
2 3 1 2
3 1 2 3 1 2

Output

x
+
cmd
2 3
Advertisements

Demonstration


Previous
#2061 Beecrowd Online Judge Solution 2061 Closing Tabs Solution in C, C++, Java, Js and Python
Next
#2078 Beecrowd Online Judge Solution 2078 Green Peace! World Hypocrisy! Solution in C, C++, Java, Js and Python