STRINGRA - Editorial

PROBLEM LINK:

Practice
Contest

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

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

Implementation : Link

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

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.

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 ?