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

needed help in problem Permutations from atcoder educational dp contest
Автор hars123, история, 6 лет назад, По-английски

I have tried this problem a lot and also figured out the states. I am trying to build up a 2D dp table dp[i][j] where first i-1 signs are satisfied and last number in the sequence is j. can someone help me in finding out the transitions for these states and solve this problem in O(N^2). If someone could suggest a top-down approach it would be really helpful as i generally find it difficult to find transitions using bottom-up approach.

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

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

Are you sure your DP states are correct? My thoughts are DP[i][j] denotes number of permutation for first i'th signs such that there are j numbers smaller than current number in the permutation obtained till now and then I think we can use prefix sum. Can someone please explain the correct solution?

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

    I am also giving it a try and trying to arrive at a solution.I will also be thankful to someone who could guide me

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

      I missed it. There is already explaination here https://codeforces.net/blog/entry/64250

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

        I have gone through the comment by Rudy358 but when i am trying to build the dp table from it its just not coming out correctly.It feels like i still have not got the right intuition about the solution.It would be helpful if you could explain me the idea behind the solution.

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

          DP[i][j] = no. Of permutat**n we can get of length i such that j numbers are smaller than value at position i. Then consider two case :

          If p[i] > p[i-1] Then dp[i][j] is sum of all dp[i-1][k] where k < j. Since there will be at most j-1 smaller number than p[i-1]

          If p[i] < p[i-1] Then dp[i][j] is sum of all dp[i-1][k] where k >= j. Since there will be atleast j smaller number than p[i-1]

          Now this solution will be O(n**3) you can speed it to O(n**2) if you store prefix sum for each layer of i.

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

Clearly explained by Errichto in this video.

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

I still don't understand the solution for this problem even after watching Errichto's video.Any help ?

→ Ответить