INC

2602203674 – Liunadi Rizky Hidayat

Problem E
1. Reading Input
a. The code begins by reading an integer `N`, representing the length of a string
`S`. It then reads the string `S` itself, followed by an integer `Q`, indicating the
number of queries or tests to be performed.
b. Each query involves reading a string `T` character by character. This string is
checked against `S` to see if they match under certain conditions.
2. Data Processing
a. The main data processing involves comparing two strings, `S` and `T`. The
program uses a custom comparison function `substrcmp` to perform this
operation.
b. `substrcmp` compares the characters of `S` and `T` in a specific manner:
starting from a given position in `S` (moving backwards) and a given interval
in `T` (moving forwards), checking for character equality.
3. Processing Logic
a. The logic of the program is to determine if string `T` can be transformed into
string `S` by reversing it and possibly making some changes.
b. This check is performed inside the main loop in `main`, which iterates through
each character of `T` and compares it with the corresponding character in `S`
(from end to start).
c. If a mismatch is found, the program checks if the ASCII values of the
mismatched characters are equal and if `substrcmp` returns true for the
remaining characters. If these conditions are met, `isValid` is set to true,
indicating a potential match.
d. `substrcmp` plays a critical role in determining if the portions of the strings
being compared are equal under the given conditions.
4. Output

1
 For each query, the program outputs "YES" if the conditions for transforming `T` into
`S` are met, and "NO" otherwise. This output is determined by the boolean variable
`isValid`, which is set based on the string comparison logic.
5. Complexity
Time: O(Q * N^2)
Space: O(N)

Problem M
1. Reading Input
The program reads three long long integers: `n`, `m`, and `k`. These variables
represent the dimensions of a grid (`n` rows and `m` columns) and the number of
rectangles (`k`) that need to be formed within this grid.
2. Data Processing
There is minimal data processing in the traditional sense, as the program primarily
relies on logical checks and calculations rather than transforming or manipulating
input data. The primary data processing occurs in the form of arithmetic operations
and logical comparisons used to determine the minimum number of lines needed.
3. Processing Logic
a. The main processing logic of the program is divided between the `main`
function and the `checkForTwo` function.
b. In `main`, the program first checks if the total area of the grid (`n * m`) is
equal to `k`, and then checks if `k` is divisible by either `n` or `m`.
c. The `checkForTwo` function is called if these initial checks don’t determine
the outcome. This function iteratively checks whether two lines (either
horizontal or vertical) can be used to form the desired number of rectangles. It
examines various combinations of dividing the grid using these lines and
checks for any combination where the remaining area after subtracting the
area covered by the lines exactly fits the remaining number of rectangles.
4. Output
Depending on the conditions evaluated in the logic processing, the program outputs
the minimum number of lines required to create `k` rectangles in an `n` by `m` grid.
This output is an integer that can be 0, 1, 2, or 3, printed to the standard output.
5. Complexity
Time: O(m + n)

2
 Space: O(1)

Problem L
1. Reading Input
- The code initializes by reading two integers, n and k. The variable n possibly
denotes the number of elements or the range of computation, while k may represent a
specific value or condition to be achieved.
- There is no string reading involved in this code, nor are there any queries like Q or
string T as mentioned in your template.
2. Data Processing
- The code does not involve any string comparison. Instead, it sets up a dynamic
programming (DP) array dp with k+1 elements. This array is used to compute and
store intermediate results based on the conditions given in the input.
- There is no function substrcmp in this code. The processing is done through iterative
loops and modular arithmetic, which suggests that the problem could be related to
counting or combinatorics under a modular system.
3. Processing Logic
- The core logic of the code involves using dynamic programming to compute values
in the dp array. This is not about transforming one string into another but about
calculating a sequence of values up to k based on the number n.
- The comparison mentioned does not exist in the provided code. Instead, the
program uses a prefix_sum to calculate the new values for the DP array, applying a
modulus operation to keep values within a certain range.
- There is no matching of ASCII values or any substring comparisons. The
conditionals in the code handle the updating of the prefix_sum based on the current
indices of i and j.
- The role of the prefix_sum is to accumulate values for the DP array, ensuring that
each new_dp[j] is computed correctly before being copied back to dp.
4. Output
The output of this program is a single integer, dp[k], which is printed at the end. It
represents the computed result from the DP array for the kth element. There is no
output of "YES" or "NO" as this is not a string comparison problem.
5. Complexity
Time: O(n * k)

3
 Space: O(k)

Problem C
1. Reading Input
- The program starts by reading an integer n, representing the number of nodes in a
graph.
- It then reads n-1 pairs of integers, each representing an edge between two nodes in
an undirected graph. These edges are used to construct an adjacency list adj for the
graph.
2. Data Processing
- The main data processing involves a depth-first search (DFS) on the graph, which is
represented by the adjacency list adj. The graph is traversed starting from node 1.
- The DFS is performed twice for each node: once with use set to 0 (not using the
node) and once with use set to 1 (using the node). The results are stored in a 2D
dynamic programming (DP) array dp.
3. Processing Logic
- The logic of the DFS function is to compute, for each node, the result of including or
excluding that node in some computation, which is not specified but could be related
to a maximum independent set or some other combinatorial optimization on the
graph.
- The DFS function employs memoization to store and reuse results for subproblems,
thus avoiding redundant calculations. This is done by initializing the dp array to -1
and checking if a value has already been computed.
4. Output
For the given graph, the program outputs a single integer, which is the maximum
result of the DFS computation multiplied by (n - 1). This is printed to the standard
output.
5. Complexity
Time: O(N)
Space: O(N)

Problem I
1. Reading Input

4
 - The program begins by reading two long long integers p and q, which likely
represent the number of nodes and the number of edges in a directed acyclic graph
(DAG), respectively.
- For each edge, it reads a pair of long long integers j and k, representing the directed
edges from node k to j. This information is used to build the graph by populating the
adjacency list Vect.
2. Data Processing
- A Depth-First Search (DFS) is initiated on each unvisited node to perform
topological sorting. The sorted nodes are stored in the oneD array, with rr keeping
track of the current index for insertion.
- The Topology function marks nodes as visited using the vectorBit bitset to prevent
revisiting nodes during DFS.
3. Processing Logic
- After the DFS and topological sorting, the program calculates arrays twoD, threeD,
and fourD. The purpose of these arrays is not explicitly stated but seems to be related
to computing the height (twoD), Lowest Common Ancestor (LCA) information
(threeD), and some additional property (fourD) for each node in the graph.
- The LowestCommonAncestor function is used to find the LCA of two nodes, which
is a common operation in tree data structures and suggests that Vect represents a tree-
like structure.
- The loops that calculate twoD, threeD, and fourD perform dynamic programming
based on the LCA and the size of the children of each node.
- The threeD array seems to be used for fast LCA queries, storing 2^i-th ancestors for
each node. The fourD array stores a cumulative count, which gets incremented
conditionally based on the number of children.
4. Output
The program outputs the computed fourD value for each node in the graph, which
likely represents a count of certain properties accumulated from its ancestors.
5. Complexity
Time: O(p * log p + q)
Space: O(p * log p + q)