yadv's blog

[Help] Educational Round 93, Problem D (Colored Rectangles)
By yadv, history, 4 years ago, In English

Help needed regarding today's contest. Problem D (Colored Rectangles).

I tried to solve this problem using a 3-dimensional dp array but I'm not able to figure out where I went wrong. My code is written below with comments, and it won't take much of your time. Thank you.

int r,g,b; cin>>r>>g>>b;    // number of red, green and blue pair
vi ar(r),ag(g),ab(b);      // vector to store each of them. (ar is for red, ag is for green, ab for blue)

for (ll i = 0; i < r; ++i)      
  cin>>ar[i];
for (ll i = 0; i < g; ++i)
   cin>>ag[i];
for (ll i = 0; i < b; ++i)
  cin>>ab[i];


// declaring a 3d vector to store all the possible choices for red,green and blue
//dp vector is 1-based index

vector<vector<vector<int>>> dp (r+1,vector<vector<int> >(g+1,vector <int>(b+1,0)));

for (ll i = 1; i < r+1; ++i)
{
  for (ll j = 1; j < g+1; ++j)
  {
    for (ll k = 1; k < b+1; ++k)
    {
       // exclude
      dp[i][j][k]=dp[i-1][j-1][k-1];

      // red & green include
      dp[i][j][k]=max(dp[i][j][k], ((ar[i-1]*ag[j-1])+dp[i-1][j-1][k]));

       // red & blue include
      dp[i][j][k]=max(dp[i][j][k], ((ar[i-1]*ab[k-1])+dp[i-1][j][k-1]));

       // green & blue
      dp[i][j][k]=max(dp[i][j][k], ((ab[k-1]*ag[j-1])+dp[i][j-1][k-1]));    
    }
  }
}
cout<<dp[r][g][b];
  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (10)
| Write comment?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

First sort the and then continue extracting elements from the back.

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

You shouldn't exclude all 3 at once, only one at a time. Also sort before you do dp.

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +11 Vote: I do not like it

You have missed the cases where i+j+k=2, (for e.g. i=1, j=1, k=0), check my solution (https://codeforces.me/contest/1398/submission/89931563) if you're still not sure.

Edit: Also sort as everyone else has recommended.

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

Can someone please explain why sorting is necessary? We will be visiting all elements before and after so how will sorting help?

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

    This dp does not skip elements but takes some elements at the beginning. So imaging you got the input like this:

    3 1 1
1 1 100
1
1
    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

If $$$a{\geq}b{\geq}c{\geq}d$$$ (all greater than 0) then it can be proven that $$$a*b+c*d {\geq} a*c+b*d$$$ and $$$a*b+c*d{\geq}a*d+b*c$$$. That means that for every subset of four elements it is always more convenient to add the product of the larger elements to the product of the smaller ones. That's why the numbers are sorted in descending order. So that we can maximize the number of subsets of four mentioned above. Hope it helps.

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

On dry run you shall find you missed to include conditions

          if(i!=0 and j!=0)dp[i][j][k]=max(dp[i][j][k],dp[i-1][j-1][k]+A[i]*B[j]);
          if(i!=0 and k!=0)dp[i][j][k]=max(dp[i][j][k],dp[i-1][j][k-1]+A[i]*C[k]);
          if(j!=0 and k!=0)dp[i][j][k]=max(dp[i][j][k],dp[i][j-1][k-1]+B[j]*C[k]);

This gets your code going 89962238

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

Can someone please help me with this. I have done sorting and still I am not able to get the correct output. I have used 1 based indexing so the user baranwalm's comment regarding two cases won't be required (I think so).

Here is a sample test(the incorrect one produced by my code): INPUT: 10 1 1 11 7 20 15 19 14 2 4 13 14 8 11

OUTPUT: 220

Please help if you have some time.

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

    Are you sorting in descending order? If not, you should be. Can you post the code in a spoiler tag so we can see it?

    → Reply