Editorial for EXUNC (Yet Another Partition Problem)

PROBLEM LINK:

Practice

Contest

Author: Bharat Goyal

Tester: Shashwat Chandra, Taranpreet Singh, Bharat Goyal

Editorialist: Bharat Goyal

DIFFICULTY

Easy-Medium

PROBLEM

Given an array A partition it into the minimum number of chains such that for members A_i and A_{i+1} of the same chain, A_{i+1} \bmod A_i = 0. You have to process Q point updates and queries. The queries ask for the first element of the chain to which the provided index belongs.

PREREQUISITES

C++ Sets, observations.

QUICK EXPLANATION:

When no two adjacent elements are equal, each chain is guaranteed to have length smaller than log_2(Z) (Z is the maximum value in the array). For the second subtask, we can compress each group of adjacent positions that have the same element by using a set. This way, the length of each chain once again becomes log_2(Z).

EXPLANATION:

Subtask 1:

Note that no two elements can be adjacent and equal. This means for a given chain B_1, B_2 … B_k , the condition \frac{B_{j+1} }{ B_j } \geq2 holds for any j \leq k-1 . From this we can infer that the length of any chain will be at most log_2(Z) where Z represents the maximum value of the array elements (10^6). So, for the update operation, we can change the values in the original array and for the queries, we can start from the given index and keep on moving to the previous index until we enter a different chain. Note that we don’t have to store the chains separately. Whether or not two elements are in the same chain can be verified by applying the modulo condition given in the question.

Subtask 2:

There are two ways to handle this subtask. The first way would be to compress all adjacent equal values into one chain and then handle the queries like we did in subtask 1. For this solution, we push the first index at which a particular value occurs into a set (and then the adjacent occurrences of the same value need not be added to the set). The update operation becomes a bit tricky here. Let ind represent the index whose value is being updated and val be it’s new value. The following cases have to be handled:

In case val is not the same as A_{ind+1} we append ind+1 to the set.

If val is the same as A_{ind+1} we remove ind+1 from the set.

If val is not equal to A_{ind-1} then we add ind to the set.

If val is equal to A_{ind-1}, we must ensure that ind is removed from the set.

For the queries, we can use a set iterator and decrement it until we find the first element of the chain. Since we’re using sets to ensure that we don’t iterate over duplicate elements, this step is guaranteed to be O(log_2Z) (Z is the maximum value present in the array).

Subtask 2 (Alternative):

The second way to handle this subtask is to store the index of the first element of each chain in the set. If we are able to maintain this set, then the answer to each query will simply be the largest index in the set that is smaller than or equal to the query index. The initial set can be built easily by iterating over the entire array and actually generating the chains while appending the index of their first element to the set. Once again, assume that A_{ind} is being updated to val. The cases that have to be handled for the update operation are as follows:

If val \bmod A_{ind-1} = 0 then delete any occurrence of ind from the set as the new value makes sure that it is a part of the chain that previously ended at ind-1.

If val \bmod A_{ind-1} ≠ 0 then add ind to the set as a new chain will have to start from ind.

If A_{ind+1} \bmod val = 0 then delete any occurrence of ind+1 from the set as A_{ind+1} will be part of the same set as A_{ind}.

If A_{ind+1} \bmod val ≠ 0 then add ind+1 to the set as a new chain will have to begin at ind+1.

COMPLEXITY

O(Qlog(N) + Nlog(N))

SOLUTIONS

Author’s Solution (Subtask 1)
Author’s Solution (100 points)

TESTER’S SOLUTION

Tester’s Solution (Subtask 1)
Tester’s Solution (100 points)

4 Likes

I handled this differently, similar to a disjoint set union.
At any moment, consider the array partitioned into groups where each element A[i] is divisible by A[i-1] inside a group. Then, let us define \text{parent}(A[i]) = i-1 if (i-1) is in the same group, and = i otherwise. Let us also define \text{n-th order parent}. For instance, parent of parent is an order 2 parent. Then let each element store a pointer to its \text{order }\sqrt{N}\text{-th parent}. It is easy to see that this structure is easy to build in \mathcal{O}(N) time. Further, queries take \mathcal{O}(\sqrt N) time. Furthermore, each update only requires us to modify at most \mathcal{O}(\sqrt N) pointers in the worst case (we get 4 cases as to whether A[i] \% A[i-1] == 0 and A[i+1] \% A[i] == 0 but this is still true in any case).
Hence the complexity is \mathcal{O}((N+Q) \sqrt N) \sim \mathcal{O}(N\sqrt N) for N \sim Q.
The solution runs in just under 1 sec.

1 Like

That’s a perfectly good solution, though you might struggle if the constraints are a bit tighter. We originally wanted to keep Q\leq10^6 for this reason but decided against it later.

1 Like

Can You explain in short What the Problem Exactly want

can someone help me optimize my solution
Solution: 40468902 | CodeChef