bully....maguire's blog

Please explain what problem D of Educational Round 84 want's to say ?
By bully....maguire, 5 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

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

→ Reply
  • »
    »
    5 years ago, # ^ |
      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
    • »
      »
      »
      5 years ago, # ^ |
        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.

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

        the statement in your spoiler needed to be the statement during contest .

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

          uummmmmmmmm......

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

            You really don't get sarcasm .....I meant why it is in spoiler if it was in contest....

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

              I'm sorry, I didn't mean to be sarcastic. I just thought I'd put that clause in a spoiler because I snatched it from the problem statement. Maybe it should've been a blockquote instead.

              → Reply
»
5 years ago, # |
  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
  • »
    »
    5 years ago, # ^ |
    ← 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
»
5 years ago, # |
← 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
  • »
    »
    5 years ago, # ^ |
      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
    • »
      »
      »
      5 years ago, # ^ |
        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