Solving the 2023B Class Assignment Problem with Dynamic Programming

Problem: In a kindergarten two classes are mixed; each child knows whether they are in the same class as the previous child (Y) or a different class (N). Given space‑separated entries “id/flag”, determine the IDs belonging to each class.

Input: A sequence of lines, each containing an integer child ID and a flag Y/N separated by “/”. The total number of children ≤ 999, IDs are in (0, 999]. Input ends with an empty line.

Output: Two lines. The first line lists the IDs of the class whose smallest ID is smaller, the second line lists the other class IDs; IDs on each line are sorted ascending and separated by spaces. If all children belong to one class, the second line is empty. Invalid input yields the string “ERROR”.

Dynamic‑Programming Solution

Let dp[i] be a boolean indicating the class of the i‑th child (True for class 1, False for class 2). Assume child 0 is in class 1, so dp[0] = True. For each i ≥ 1:

if YN_lst[i] == "Y":
    dp[i] = dp[i-1]
elif YN_lst[i] == "N":
    dp[i] = not dp[i-1]

After filling dp, iterate over the children: if dp[i] is True append the child ID to class1, otherwise to class2. Sort both lists, then output the list whose first element is smaller first.

Reference Implementation (Python)

# 2023B – Class Assignment
children_lst = []
YN_lst = []

while True:
    s = input()
    if len(s) == 0:
        break
    child, ch = s.split("/")
    children_lst.append(int(child))
    YN_lst.append(ch)

n = len(children_lst)
dp = [None] * n
dp[0] = True

for i in range(1, n):
    if YN_lst[i] == "Y":
        dp[i] = dp[i-1]
    elif YN_lst[i] == "N":
        dp[i] = not dp[i-1]

class1, class2 = [], []
for i in range(n):
    (class1 if dp[i] else class2).append(children_lst[i])

class1.sort()
class2.sort()

if len(class2) == 0:
    print(" ".join(map(str, class1)))
    print("")
else:
    if class1[0] > class2[0]:
        class1, class2 = class2, class1
    print(" ".join(map(str, class1)))
    print(" ".join(map(str, class2)))

Complexity Analysis

Time complexity: O(x log x + y log y + N), where x and y are the sizes of the two classes (sorting) and N is the number of children (DP pass).

Space complexity: O(N) for the DP array and the two class lists.