PROBLEM LINK:Author: Arjun Arul PROBLEM EXPLANATIONGiven an array consisting of N integers. Let's construct a directed acyclic graph of N+1 nodes. If there is a subsequence S_{1} ending at position U which cannot be formed with all elements to the left of A_{U}, let's denote by S_{2} the subsequence resulting from appending A_{V} to S_{1} (U < V) An edge is added from node U to node V if and only if the subsequence S_{2} cannot be formed with all elements to the left of A_{V}. 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 ≤ 10^{5}) DIFFICULTY:easymedium 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_{P1}$, 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 L_{0} (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_{P1}$ then we don't need to look for it. Corner CaseWhile 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_{P1}$ and reaching an unassigned number means that it's not existed in $L_{P1}$ 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
This question is marked "community wiki".
asked 14 Aug '17, 08:35

I used used only 1 observation to solve the problem i.e. the number of edges outgoing from a node is number of distinct numbers in the range $[node, N]$, where $N$ is size of array. Then to minimise the answer, just assign the numbers greedily, i.e. the smallest unsed number till now starting from $ans[node]$. (i.e. also called "mex" as in game theory). Then check whether the constructed answer obeys the given graph (i.e. using above observation only). Implementation : Link answered 18 Aug '17, 16:21
Hey @likecs you said the number of edges outgoing from a node is number of distinct numbers in the range [node,N] but two same numbers after node may also be present and that number too have an edge(number with first occurrence). Have i made myself clear? Please Help.
(24 Aug '17, 11:34)

For those people who requested me for the solution, heres my code. I have given necessary comments, but you guys need to make observations on your own answered 18 Aug '17, 15:18

For me personally, this was the hardest problem that i solved. The statement was very confusing and mentioned multiple edges many times, when eventually i learned that multiple edges only mean that you should output 1. I also had some of the observations above but could not get my solution to pass. It is quite difficult to generate your own tests for this particular problem. So i started googling and found this link. In here you can see that from any subsequence (i.e. array) you can build a finite state machine( or DAG = Directed Acyclic Graph) which can generate all of it's subsequences. I noticed that the graph that we were given in the problem was actually exactly that type of finite state machine. So i used that to generate tests for my solutions. I just created the original arrays with my test generator, which created the finite state machine, which i passed as input to my solution and checked if my output is the same as my input. I found my bugs quickly after that :). Hopefully this link helps someone :). answered 18 Aug '17, 19:03

i do not understand how the list lp and lp1 can be same.can somebody explain it more clearly answered 18 Aug '17, 21:31

if you explain with some example it will be more helpful... answered 18 Aug '17, 23:37

"Note that even if an edge with a different label is already present, this edge is added. Just that there will not be multiple edges from one vertex to another with the same label" Whats the meaning of this statement? how can two edge between two nodes with different labels are possible? answered 19 Aug '17, 20:10

hello @likecs i have also used that one observation and use greedy approach to assign the number in array but gets the wrong answer here is my implementation https://www.codechef.com/viewsolution/15014201 plz check it and tell my mistakes........thanks in advance. answered 20 Aug '17, 12:57

I have one doubt about sample test case. Why 2 test case in sample is giving 1 as output ? Why it is invalid graph formation ? And it is compulsory that from position in array there "must be edge" only to first occurrence of any number present on right from that position ? answered 26 Aug '17, 12:31
