PROBLEM LINK:
Author: Arjun Arul
Tester: Hasan Jaddouh
Editorialist: Hussain Kara Fallah
PROBLEM EXPLANATION
Given an array consisting of N integers. Let’s construct a directed acyclic graph of N+1 nodes. If there is a subsequence S1 ending at position U which cannot be formed with all elements to the left of AU, let’s denote by S2 the subsequence resulting from appending AV to S1 (U < V)
An edge is added from node U to node V if and only if the subsequence S2 cannot be formed with all elements to the left of AV. You are given a DAG with N+1 nodes and M edges, you are asked to restore the lexicographically minimum array which this graph corresponds to or state that data is inconsistent.
Please note that node 0 represents the empty subsequence.
(1 ≤ N,M ≤ 105)
DIFFICULTY:
easy-medium
PREREQUISITES:
Sortings
EXPLANATION:
Observation 1:
Let’s denote by L_i the adjacency list of the i-th node.
Note that the out degree of node 0 (size of L_0) is equal to the number of distinct elements in our array (let’s denote it by K). Because each position that presents in this list refers to the first occurrence of a (new) number since an edge from node 0 to other node corresponds to a subsequence of size 1.
Observation 2:
Consider an arbitrary position P, you can note that the subsequence containing all elements A_i (1 \leq i \leq P) cannot be formed without considering all elements till A_P let’s denote this subsequence by S_1. If there is an edge (P \rightarrow Q), it means that Q must be the first occurrence (to the right of P) of one of our numbers (Why?), because if there was an earlier occurrence R (R < Q), then the subsequence S_1 + A_Q (+ denotes concatenation) could be formed with the first R elements, and that means an edge (P \rightarrow R) must exist and the other edge (P \rightarrow Q) mustn’t (contradiction).
Observation 3:
Let’s consider the list L_{P} and the list L_{P - 1}. The size of L_{P} must be equal or less by one than the size of L_{P - 1}. Let’s think about earliest occurrences of our K numbers when looking to the right of A_{P-1}, you can see that all of them will remain the same (when looking to the right of A_P), EXCEPT for 1 element which is A_P. P is present in L_{P - 1} (clearly it’s the earliest occurrence of A_P), but in L_{P} it will be replaced by the first occurrence to the right of P (so lists sizes will stay the same), or there may be no next occurrence (if P was the last occurrence of A_P) then size of L_{P} would be less by 1.
Let’s assign numbers from 1 to K to all positions present in L0 (in increasing order of position). After that let’s consider each 2 consecutive lists L_{P}, L_{P - 1}. All elements of L_{P - 1} must be present in L_{P} except for one element for sure which is equal to P. All elements of L_{P} must be present in L_{P - 1} except one number X which is equal to A_P, so we should assign A_X = A_P (if size of L_{P} is less by one than the size of L_{P-1} then we don’t need to look for it.
Corner Case
While processing elements from left to right, if we come to an element which hasn’t been processed then our data is inconsistent. Any position P must exist in L_{P-1} and reaching an unassigned number means that it’s not existed in L_{P-1} otherwise we would have assigned it to a value.
Solution runs in O(M log M)
AUTHOR’S AND TESTER’S SOLUTIONS:
AUTHOR’s solution: Can be found here
TESTER’s solution: Can be found here
EDITORIALIST’s solution: Can be found here