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

How to solve SPOJ problem YAPP?
Автор dush1729, история, 9 лет назад, По-английски

Problem link

Why is the answer 2 ^ ( n — 1 ) ?

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

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

Suppose the correct answer for f(n) = k and we want to find out f(n+1)

One could either place the highest number i.e. (n+1) either towards the rightmost end in the permutation or towards the leftmost end to satisfy constraints "maximum element between the indices [i..j] is either present at index i, or at index j" to satisfy for [1...n]. The other inner constraints would automatically be satisfied as we know f(n) is true. So there are 2 possible choices. f(n+1) = 2*f(n)

Now the base case n = 1. There is only 1 choice so f(1) = 1. Kind of Mathematical Induction Proof :P

So a recurrence relation f(n) = 2*f(n-1) when n > 1. Solving this recurrence f(n) = 2**n-1

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

    I cannot understand why is f(n+1) = 2*f(n) ?

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

      Emm. Suppose the ans for n = 3 has these possibilities:

      1 2 3
3 1 2
2 1 3
3 2 1

      4 possible answers

      Now i need to find ans for n = 4. So _ _ _ _. I can either place it at 1st index or 4th index to satisfy the property "maximum element between the indices [i..j] is either present at index i, or at index j" for range [1..4]

      So the ans will be:

      1 2 3 4
3 1 2 4
2 1 3 4
3 2 1 4

4 1 2 3
4 3 1 2
4 2 1 3
4 3 2 1

      4 + 4 = 8 possible answers

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

        excuse me , why did you not count these possibles in your answer??

        4 2 3 1

        4 1 3 2

        1 3 2 4

        2 3 1 4 ???

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

          4 2 3 1
          i=2,j=4 the maximum number is 3 which is neither in the ith nor in the jth position.
          4 1 3 2 i=2,j=4
          1 3 2 4 i=1,j=3
          2 3 1 4 i=1,j=3

          → Ответить