K0KALARU47 Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: Cozma Tiberiu-Stefan
Tester: Felipe Mota, Abhinav Sharma
Editorialist: Pratiyush Mishra

DIFFICULTY:

3378

PREREQUISITES:

Dynamic Programming

PROBLEM:

in every century, there is a chosen one. Therefore, we do not live in a society
–Last paragraphs of the IZhO 2022 Editorial

K0Kalaru47 was out with his friends and he started to tell them about a CP Task. Because the statement was informal, his friends quickly parried with “Who Asked”, so here is the formal statement:

Given arrays P and C of size (N+K) each, the beauty of an array B of size (N+K) is defined as the sum of C_i for all 1\leq i \leq (N+K) such that B_i = P_i.

More formally, the beauty of an array B is equal to \large\sum^{|B|}_{i=1} C_i [B_i = P_i]

Given an array A of size N such that (1 \leq A_i \leq M).
Your task is to insert K elements into the array such that:

  • Each inserted element lies in the range [1, M].
  • The beauty of the final array is maximized.

Note that, an element can be inserted at any index of the array.

You should find two values:

  • The maximum beauty that can be obtained across all arrays of size (N+K).
  • The number of distinct arrays of size (N+K) having the maximum beauty. Note that, two arrays X and Y are said to be different if there exists some index i such that X_i ≠ Y_i. Since the number of distinct arrays can be huge, print the value modulo MOD.

QUICK EXPLANATION:

We can say some final vector B can be obtained from the initial vector if and only if

  • All number in B are [1,M].
  • Initial vector A is a subset of final vector B.

We can check if the initial vector is a subset of final vector using the following greedy approach.
FIrst pick a pointer p = 1. Loop through the array, if at any i, \; B_i = A_p, increment p by 1. If at the end p = |A| + 1, then and only then is A a subset of B. This is also known as the Subset Search Algorithm
One important thing to note here is that the subset it finds is always unique. Using this we can define our dp[i][j] to store the maximum beauty and the number of arrays to have that beauty.

One more thing we can notice is that we will form array B by only using the following values:

  • P_i
  • A_j
  • A_{j+1}
  • Any other value other than above three.

Thus we can only try these values and have O(1) transitions. Our final answer would be then dp[n+k][n].

EXPLANATION:

Let us construct our dp[i][j] and define it to store two values as:

  • The maximum beauty of an array that has length i and the subset search algorithm found the first j values of vector A.
  • The number of ways to have that beauty for an array that has length i and the subset search algorithm found the first j values of vector A.

Now let us define the transitions of our dp as follows:

  • if p[i]=a[j] \;and\; a[j]=a[j+1]:
dp[i][j] = max(dp[i][j],\{dp[i-1][j-1].first + C[i],dp[i-1][j-1].second\},\{dp[i-1][j].first,dp[i-1][j].second*(m-1)\})
  • Else if a[j] \neq a[j+1] \& a[j] \neq p[i] \& a[j+1] \neq p[i]:
dp[i][j] = max(dp[i][j],\{dp[i-1][j].first + C[i],dp[i-1][j].second\},\{dp[i-1][j].first,dp[i-1][j].second*(m-3)\},dp[i-1][j],dp[i-1][j-1])
  • Else if a[j] = a[j+1]:
dp[i][j] = max(dp[i][j],\{dp[i-1][j].first + C[i],dp[i-1][j].second\},\{dp[i-1][j].first,dp[i-1][j].second*(m-2)\},dp[i-1][j-1])
  • Else if a[j] = p[i]:
dp[i][j] = max(dp[i][j],\{dp[i-1][j-1].first + C[i],dp[i-1][j-1].second\},\{dp[i-1][j].first + C[i],dp[i-1][j].second\},\{dp[i-1][j].first,dp[i-1][j].second * (m-2)\})
  • Else if a[j+1] = p[i]:
dp[i][j] = max(dp[i][j],\{dp[i-1][j].first,dp[i-1][j].second*(m-2)\},dp[i-1][j],dp[i-1][j-1])

TIME COMPLEXITY:

O((N+K)\cdot N) for each test case.

SOLUTION:

Setter’s Solution
Tester1’s Solution
Tester2’s Solution