Shameek's blog

help needed in CSES question
By Shameek, 4 years ago, In English

https://cses.fi/problemset/task/1160

can someone please help me in this question?

I am not getting any ideas as to how i should proceed...

  • Vote: I like it
  • +12
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Each node has only one outgoing edge, so we have no options (like choosing where to go next); we merely follow the (only) edge.

This kind of directed graph is also called a functional graph. One of the most important properties of functional graphs is that each component (here, a component is that of an undirected sense) has a single cycle, and possibly a few trees (that are directed, where each node points to the parent and the root is on the cycle) attached to them.

If you're not sure, I recommend that you take a few random examples (random $t_i$s, in this problem) and draw the graph. Say, n=10, t[1..10] = {2, 3, 1, 2, 2, 4, 4, 9, 8, 9}. The key is to see that, starting from any vertices, you are going to eventually reach the cycle (i.e. arrive at a node that is on the cycle) of the component.

Say we're processing a query from a to b. First, if these two nodes belong to different components, it is easy to see that we'll never be able to reach b from a.

Now, assume they are on the same component. If b is on the cycle of the component, you are going to reach it from a in some number of steps. It would consist of two stages: first, you reach the cycle (if a is not on the cycle). Second, you reach b. Figuring out how long each stage takes is left to you. Note that the length of the first stage is the same regardless of b.

If b is not on the cycle, then it belongs to a tree hanging around the cycle. For a to reach b then, a should be a descendant of b (or equivalently, b is an ancestor of a). How to check that? Again, I'd like you to work on that.

If anything's not clear or you have more questions, feel free to ask.

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it +8 Vote: I do not like it

    thanks for the crystal clear explanation i absolutely understood everything!

    implementing this is definitely going to be a little tough but ill try then get back

    Edit: https://codeforces.me/blog/entry/79518 this is an attempt to writing the editorial

    for the graph section of cses but its incomplete... if u have time can u finish this off? it

    would be of great help!!

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Shouldn't $$$a$$$ be an ancestor of $$$b$$$ in case $$$b$$$ is not on the cycle ?

    Like for Example in this graph. Link To Image

    If $$$a = 1$$$ and $$$b = 2$$$ in this case ?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      i dont get your quesn..can u explain further? e.g. a = 2 b = 1 a is not the ancestor of b though b isnt on the cycle

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I mean to reach from a to b. In the graph I gave, shouldn't a be an ancestor of b.

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          The sentence "$$$a$$$ is an ancestor of $$$b$$$." means that $$$a$$$ is on the parent side (like parent, grandparent, grand-grandparent, ...), up in the hierarchy and closer to the cycle. Is this what you meant?

          → Reply
          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Yes, Meaning $$$depth(a) < depth(b)$$$ Or More Formally,

            $$$dt(a) < dt(b) \; and \; ft(a) > ft(b)$$$ Where $$$dt$$$ and $$$ft$$$ are discovery times and finish times respectively.

            → Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it +8 Vote: I do not like it

    Namnamseo i tried but i am still getting WA on only 1 testcase but its very huge so i cannot understand

    approach: i first assign depth to nodes by randomly assigning any one node of the cycle as 1 then doing depth[node] = depth[child[node]] + 1

    then by building a binary lifting table i jump

    this will work because as you pointed out in functional graph, there is only one path i.e. a length 4 path from some node x has only one possible ending node

    now depending on difference of depth of nodes i jump and if i reach the node i print the depth difference else print -1

    special case here is that if two nodes are of the same cycle then depth[a] < depth[b] might be possible

    in that case , i print the length of the cycle — depth[b] + depth[a]

    my code: https://ideone.com/pi9Cx3

    any help will be appreciated thanks!!!

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Great job! I'm impressed by your implementation, especially using depths to make matters simple.

      One thing (I think) you've missed is that, the case of dep[a]>dep[b] can do occur, even when a is not on the cycle. Specifically, what if a has a small depth, b is beyond the dep=1 point and the cycle size is large enough?

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
        ← Rev. 2   Vote: I like it +8 Vote: I do not like it

        YES ABSOLUTELY!! my final code that got accepted...

        https://ideone.com/hKsG5K

        i did the same thing as above but i added a trick — depth of a node in a cycle can be either the depth or if b is part of a cycle its depth can be depth[b] — cyclelength

        thanks a lot!! i could never have done this question without you!!

        → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

nvm i understood

→ Reply