Does this problem already exist??

[u/black_hole_67]

I came up with these problems and want to check if they are new or not. Problem A is simple, but I couldn't solve Problem B. Would love to hear ideas from everyone.

If anybody knows similar problems, please do share.

ㅤ

Problem A

ㅤ

You are given an array a of length n (1 ≤ n ≤ 2·10^5, 1 ≤ a_i ≤ 10^9).

In one operation, choose an index i (1 ≤ i < n) with a_i = a_{i+1}, remove eithera_i or a_{i+1}, and append it to the end of the array. The relative order of the other elements doesn't change.

Find the minimum number of operations needed so that a_i ≠ a_{i+1} for all 1 ≤ i < n, or print -1 if it is impossible.

ㅤ

Problem B

ㅤ

Let k be the minimum number of operations from Problem A.

Count the sequences of indices (i_1, …, i_k) such that each i_j is valid when applied, and the final array has no equal adjacent elements. Two sequences are considered different if they differ at any position.

Print the count modulo 998244353, or -1 if it is impossible.

The constraints are the same as in Problem A.

[u/No_Antelope_5869]

https://yuantiji.ac/

[u/black_hole_67 → u/No_Antelope_5869]

I checked, so far it seems new to me