×

# 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

This question is marked "community wiki".

1081032
accept rate: 0%

19.8k350498541

 3 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 6★likecs 3.7k●23●80 accept rate: 9% 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)
 2 The test cases were very weak. My code fails on sample case still got 100 points. Solution answered 18 Aug '17, 21:03 4★rj25 230●5 accept rate: 0%
 0 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 answered 18 Aug '17, 15:18 15.4k●1●20●66 accept rate: 18%
 0 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 2★vasja 515●1●6 accept rate: 7%
 0 i do not understand how the list lp and lp-1 can be same.can somebody explain it more clearly answered 18 Aug '17, 21:31 23●5 accept rate: 0%
 0 if you explain with some example it will be more helpful... answered 18 Aug '17, 23:37 12●2 accept rate: 0%
 0 "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 15●4 accept rate: 0%
 0 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 4★dk30390 84●4 accept rate: 9%
 0 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 4★rj25 230●5 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,680
×1,672
×1,000
×947
×790
×193
×11

question asked: 14 Aug '17, 08:35

question was seen: 1,694 times

last updated: 26 Aug '17, 12:34