-______-'s blog

Help In Question B. BerSU Ball ( Codeforces Round #277.5 )
By -______-, history, 6 years ago, In English

I've successfully solved this problem using Greedy Approach but in the editorial it was given that the probelm can also be solved using Dynamic Programming.

Can someone help me with the DP solution ? (preferably in C++)

Problem Link : http://codeforces.com/problemset/problem/489/B

Editorial Link : http://codeforces.com/blog/entry/14741

My Solution ( Greedy ) : 39216236

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
6 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

First, sort arrays a and b.

Let dp[i][j] be the answer if we have only a[0..i] and b[0..j].

dp[i][j] is maximum of:

  • 0
  • 1 if |a[i]-b[j]|<=1
  • dp[i-1][j-1]+1 if i-1>=0, j-1>=0 and |a[i]-b[j]|<=1
  • dp[i-1][j] if i-1>=0
  • dp[i][j-1] if j-1>=0

Answer will be dp[n-1][m-1].

My Solution: 39227258

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

    Can we do an O(n) dp ?

    Can we solve the problem Online (without brute-forces) ?

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

    Here is my shorter dp solution O(n * m) ~ vector dp(n + 1, vi(m + 1, 0)); for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) dp[i][j] = max({dp[i-1][j], dp[i][j-1], dp[i-1][j-1] + (abs(boy[i-1] — girl[j-1]) <= 1)}); ~

    Can we dp in O(n) if we use frequency array ?

    → Reply