i dont know why priorities need to be given and then how to give priorities
i have tried to think for a week but still not able to find this priority based solution
and i haven’t coded anything yet
PLEASE HELP
thanks in advance
Siddharth and permutations
found the priority ordering thing but still not able to apply topological sort since i dont know where to apply it
from
i.e i have a priority list and now how to assign values to integer array using topological on that priority graaph sine the graph is made of disconnected components
PLEASE HELP ME OUT WITH THIS
my code
PROBLEM : am passing only one out of two test cases
hello jai please try to understand this code and find where you are going wrong.
bhaiya,
i don’t understand the reason behind building a tree since here we will assign priorities kind of thing and then topological sorting is required to be applied
plus i don’t understand how the tree is built
Let’s consider ai = n + 1 instead of ai = - 1. Let’s also define the sequence b, where bi = j such that aj = i or bi = n + 1 if there is no such j. Lets make a directed graph with vertices be the indices of the permutation p with edges of type (a, b) representing that pa > pb. If we topologically sort this graph then we can come up with a possible permutation: if S is the topologically sorted graph then we can assign to pSi number i.
In this problem we will use this implementation of topological sort.
But how we can find the edges? First of all there are edges of the form (i, bi) if bi ≠ n + 1 .For a vertex i he visited all the unmarked vertices j (1 ≤ j < ai, j ≠ i) and you know for sure that for all these j, pj < pi. But how we can check if j was already marked? The vertex j will become marked after turn of vertex bj or will never become unmarked if bj = n + 1. So there is a direct edge from i to j if j = bi or 1 ≤ j < ai, j ≠ i and bj > i.
Suppose we already visited a set of vertices and for every visited vertex node we assigned to bnode value 0 (for simplicity just to forget about all visited vertices) and now we want to find quickly for a fixed vertex i an unvisited vertex j with condition that there is edge (i, j) or say it there isn’t such j, if we can do that in subquadratic time then the task is solved. As stated above the first condition is j = bi if 1 ≤ bi ≤ n, this condition is easy to check. The second condition is 1 ≤ j < ai and bj > i, now consider vertices with indices from interval 1…ai - 1 and take j with maximal bj. If bj > i we found edge (i, j) otherwise there are no remaining edges. We can find such vertex j using segment tree and updating values while we visit a new vertex. In total we will visit n vertices and query the segment tree at most 2 × (n - 1) times (n - 1 for every new vertex and n - 1 for finding that there aren’t remaining edges).
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.