Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

-______-'s blog

By -______-, history, 2 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

»
2 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

  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    VladProg What gives the insight to sort input arrays? I was stuck with similar solution but only with considering suffixes subproblems instead of prefixes. Finally after seeing the above hint I got accepted. 55184617. If we think in terms of greedy sorting would be required in making local decision but DP solution I was getting the subproblem solution wrong in some cases and sorting corrected it, however I still don't understand why sorting fixes the solutions of subproblems.

  • »
    »
    4 months 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) ?

  • »
    »
    4 months 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 ?