Lance_HAOH's blog

Problem understanding solution for round #383 (div 2) problem C
By Lance_HAOH, history, 8 years ago, In English

This was the given solution for round #383 (Div 2) problem C:

The problem statement: Here

The solution:

Make a directed graph and put edge from i and crushi. If the graph has vertex such that its in-degree is 0 then obviously answer doesn't exists. Otherwise the graph consists of some cycles. For each cycle suppose that its length is len. If it has odd length, add len to S, otherwise, add len / 2.

Answer is the LCM of numbers in S.

I am unsure why the LCM is the answer. Is anyone able to advise me?

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (7)
| Write comment?
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

When you start from a, you end at b. The problem requires if you start from b, you must end at a. This requires a presence of cycle. So if the cycle is of even size, we can obtain the above property in a multiple of len / 2. And if its odd, we need a multiple of len. Since we have to make this true for every cycle, you need the LCM.

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

    Sorry. I don't quite get it. Let's say that we have a relationship between x and y as follows:

    x is a crush of y and y is a crush of x

    So the cycle is of length 2.

    Now len/2 = 1. Let's use 3 as an arbitrary multiple of 1,

    Now, if we move 2 steps from x (since we stop when t = 1), we return back to x which should not correct right?

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

      You have misunderstood the problem. Given a value of t, begin from node x. Lets say you end up at node y. Now what problem needs is if we start from node y and take the same value of t, we should end up at x.

      In the above case, you begin with x and end at x. So this is the trivial solution satisfying the condition.

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

It is easy to prove that every connected component is cycle (and nothing else). This is because every node must have at least one edge coming into it, otherwise it is impossible as you can never reach it. Also every node must have on edge coming out of it. Therefore the graph is a group of cycles, otherwise it is impossible.

Let x denote the length of one of the cycles.

If x is even, then t must be a multiple of x/2. This ensures that when you travel length t*2 you come back to the same place.

If x is odd, then t must be a multiple of x. This ensure that when you travel length t*2 you come back to the same place.

Then we find the minimum t which is a multiple of all these values.

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

    When x is even, why can't we let t be a multiple of x since if we travel 2*t, we come back to the same place?

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

      Multiple of x/2 is always a multiple of x...

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

Lets say the set is S = {a1,a2,a3 ... aN}. For the cycle with contributed to a1, all the multiples of a1 will satisfy the answer.

So, we took the LCM of the set S, so as to select a minimum number which will satisfy all the cycles in the graph.

→ Reply