 # STRINGRA - Editorial

Author: Arjun Arul
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)

easy-medium

Sortings

### 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

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-

https://www.codechef.com/viewsolution/15020660

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).

3 Likes

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 :).

The test cases were very weak. My code fails on sample case still got 100 points. Solution

2 Likes

i do not understand how the list lp and lp-1 can be same.can somebody explain it more clearly

if you explain with some example it will be more helpful…

“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?

hello @likecs

i have also used that one observation and use greedy approach to assign the number in array