We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • HackerRank Home

    HackerRank

  • |
  • Prepare
  • Certify
  • Compete
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Dynamic Programming
  4. Superman Celebrates Diwali
  5. Discussions

Superman Celebrates Diwali

Problem
Submissions
Leaderboard
Discussions
Editorial

    You are viewing a single comment's thread. Return to all comments →

  • sukhesai
    2 years ago+ 0 comments

    typical dp problem with some tricky manipulation. Here is my python solution:

    import collections
    
    
    n,h,ii = map(int, input().split())
    dp = [[0]*h for _ in range(n)]
    for i in range(n):
        x = list(map(int, input().split()))
        for j in x[1:]: dp[i][j-1] += 1
    last = collections.deque()
    for j in range(h):
        x = last.popleft() if j >= ii else 0
        for i in range(n):
            dp[i][j] += max(0 if j == 0 else dp[i][j-1], x)
        last.append(max(k[j] for k in dp))
    print(max(k[-1] for k in dp))
    
    0|
    Permalink
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy