Light Bulbs (Easy Version) (Codeforces 1914G1)
Tags: Math, dsu

The easy and hard versions of this problem differ only in the constraints on $$$n$$$. In the easy version, the sum of values of $$$n^2$$$ over all test cases does not exceed $$$10^6$$$. Furthermore, $$$n$$$ does not exceed $$$1000$$$ in each test case.There are $$$2n$$$ light bulbs arranged in a row. Each light bulb has a color from $$$1$$$ to $$$n$$$ (exactly two light bulbs for each color).Initially, all light bulbs are turned off. You choose a set of light bulbs $$$S$$$ that you initially turn on. After that, you can perform the following operations in any order any number of times:  choose two light bulbs $$$i$$$ and $$$j$$$ of the same color, exactly one of which is on, and turn on the second one;  choose three light bulbs $$$i, j, k$$$, such that both light bulbs $$$i$$$ and $$$k$$$ are on and have the same color, and the light bulb $$$j$$$ is between them ($$$i < j < k$$$), and turn on the light bulb $$$j$$$. You want to choose a set of light bulbs $$$S$$$ that you initially turn on in such a way that by performing the described operations, you can ensure that all light bulbs are turned on.Calculate two numbers:  the minimum size of the set $$$S$$$ that you initially turn on;  the number of sets $$$S$$$ of minimum size (taken modulo $$$998244353$$$). 

Input: The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. Then follow the descriptions of the test cases.The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 1000$$$) — the number of pairs of light bulbs.The second line of each test case contains $$$2n$$$ integers $$$c_1, c_2, \dots, c_{2n}$$$ ($$$1 \le c_i \le n$$$), where $$$c_i$$$ is the color of the $$$i$$$-th light bulb. For each color from $$$1$$$ to $$$n$$$, exactly two light bulbs have this color.Additional constraint on the input: the sum of values of $$$n^2$$$ over all test cases does not exceed $$$10^6$$$.

Output: For each test case, output two integers:  the minimum size of the set $$$S$$$ that you initially turn on;  the number of sets $$$S$$$ of minimum size (taken modulo $$$998244353$$$). 


Sample Inputs:
4
2
2 2 1 1
2
1 2 2 1
2
1 2 1 2
5
3 4 4 5 3 1 1 5 2 2

Sample Outputs:
2 4
1 2
1 4
2 8

Solution (Python):
t = int(input())
MOD = 998244353

def calcPerm(A, last, i, k):
    perm = set()
    graph = {}
    for j in range(i, k + 1):
        graph[A[j]] = set()
    for j in range(i, k + 1):
        length = last[A[j]] - 1
        while length > j:
            graph[A[length]].add(A[j])
            length -= 1
    h = [A[i]]
    seen = set()
    while len(h) > 0:
        u = h.pop()
        perm.add(u)
        for v in graph[u]:
            if v not in seen:
                h.append(v)
                seen.add(v)
    return len(perm) * 2

def Solve(A):
    sets = 1
    numOfSet = 1
    first = {}
    last = {}
    for i in range(len(A)):
        last[A[i]] = i
    maxL = last[A[0]]
    prev = 0
    currentPerm = 0
    stack = []
    cache = {}
    for i in range(len(A)):
        if i > maxL:
            currentPerm = calcPerm(A, last, prev, i - 1)
            prev = i
            sets += 1
            numOfSet *= currentPerm
            numOfSet = numOfSet % MOD
            currentPerm = 0
        maxL = max(maxL, last[A[i]])
    currentPerm = calcPerm(A, last, prev, len(A) - 1)
    numOfSet *= currentPerm
    numOfSet = numOfSet % MOD
    return (sets, numOfSet)
for i in range(t):
    n = int(input())
    A = input().rstrip().split(' ')
    for i in range(len(A)):
        A[i] = int(A[i])
    sumA = sum(A)
    (sets, numOfSet) = Solve(A)
    print(str(sets) + ' ' + str(numOfSet))

Solution (Python):
mod = 998244353

def helper(a, b):
    not_good = set()
    for ii in range(a + 1, b):
        visit = set()
        for jj in range(ii, b):
            visit.add(nums[jj])
            if jj - ii + 1 == 2 * len(visit):
                not_good |= visit
                break
    return 2 * len(not_good)
for _ in range(int(input())):
    n = int(input())
    nums = list(map(int, input().split()))
    group = []
    i = 0
    seen = set()
    for (j, num) in enumerate(nums):
        seen.add(num)
        if j - i + 1 == 2 * len(seen):
            group.append((i, j))
            i = j + 1
            seen = set()
    ans = 1
    for (a, b) in group:
        ans *= b - a + 1 - helper(a, b)
        ans %= mod
    print(len(group), ans)

Solution (Python):
modulus = 998244353

def count_not_good_elements(start, end):
    not_good_set = set()
    for ii in range(start + 1, end):
        visit = set()
        for jj in range(ii, end):
            visit.add(numbers[jj])
            if jj - ii + 1 == 2 * len(visit):
                not_good_set |= visit
                break
    return 2 * len(not_good_set)
for _ in range(int(input())):
    array_size = int(input())
    numbers = list(map(int, input().split()))
    groups = []
    i = 0
    seen_numbers = set()
    for (j, num) in enumerate(numbers):
        seen_numbers.add(num)
        if j - i + 1 == 2 * len(seen_numbers):
            groups.append((i, j))
            i = j + 1
            seen_numbers = set()
    result = 1
    for (start, end) in groups:
        result *= end - start + 1 - count_not_good_elements(start, end)
        result %= modulus
    print(len(groups), result)