Блог пользователя Shameek

help needed in CSES question
Автор Shameek, 4 года назад, По-английски

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

  • Проголосовать: нравится
  • +12
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    4 года назад, # ^ |
    ← Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

    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://mirror.codeforces.com/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!!

    → Ответить
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    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 ?

    → Ответить
    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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

      → Ответить
      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        → Ответить
        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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?

          → Ответить
          • »
            »
            »
            »
            »
            »
            4 года назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            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.

            → Ответить
  • »
    »
    4 года назад, # ^ |
    ← Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

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

    → Ответить
    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      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?

      → Ответить
      • »
        »
        »
        »
        4 года назад, # ^ |
        ← Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

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

        → Ответить
»
4 года назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

nvm i understood

→ Ответить