bully....maguire's blog

Please explain what problem D of Educational Round 84 want's to say ?
By bully....maguire, 6 years ago, In English

I read problem D many times i could not figure out what it want's to say . Can someone explain the problem with second example case. Problem D is the only problem in my life time that i did not understood by myself so please help me.

LINK

  • Vote: I like it
  • -30
  • Vote: I do not like it

»
6 years ago, hide # |
 
Vote: I like it +5 Vote: I do not like it

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

    in third case for example we get B = [3,6,1,8,7,2,5,4] from array A = [7 4 5 6 1 8 3 2] because at 7th position of A we have 3 hence 7 gets replaced by 3 . At 4th position of A we have 6 and thus 4 is replaced by 6 and so on . Now in array B , p2[4] = 8 p2[8] = 4 and thus we get sequence 4,8,4,8 .... and in color array [5 3 6 4 7 5 8 4] at position 4 we have 4 and at position 8 we have 4 . Thus each color corresponding to position in sequence 4,8,4,8 .... has same value.

    Is my understanding correct or else please explain the problem using one of the given example..

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

      Yes that's right. What you've just described is the existence of an infinite path. That infinite path exists for the first time in $$$p^{2}$$$. Take a look at $$$p^{1}$$$, no infinite paths exists.

      The problem wants you to find that.

      Спойлер
      → Reply
»
6 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Please help .I tried hard but could not understand . If some one explains any one of the example my problem will be solved .

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

    That is exactly what I mean by being specific. The sample testcases are already well explained in the problem statement, so you need to let people know which part that you don't understand.

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

The second test seems to be faulty because after 5 days it will end up same as the start.

As for the problem think of it as there is n land every land have color and portal which directs to the other land. Every night passes i th land steals the portal from the land which their portal used to direct to. Let's consider lucky infinite path as -> if a person goes through portals starting from ith land and every land he visits is in same color. After how many days will there be at least one infinite path.

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

    The second test seems to be faulty because after 5 days it will end up same as the start.

    Nope, that would take 6 days. After 5 days it is just trivial permutation, all paths in which are infinite

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

      Oooh Ok I got it now I was calculating wrong. This teleportation land idea is all wrong my bad. Tnx

      → Reply