Help needed in 1011 — Marriage Ceremonies (lightoj) problem

#	User	Rating
1	tourist	3778
2	Benq	3592
3	ecnerwala	3521
4	Um_nik	3423
5	jiangly	3375
6	Petr	3342
7	Radewoosh	3337
8	scott_wu	3313
9	maroonrk	3265
10	yosupo	3259

#	User	Contrib.
1	Errichto	201
2	1-gon	200
3	rng_58	194
4	SecondThread	193
5	awoo	186
6	vovuh	183
7	Um_nik	181
8	antontrygubO_o	177
9	Ashishgup	175
10	-is-this-fft-	171

Hello, in this problem 1011 — Marriage Ceremoniesthe priority index is not clear to me. I used bottom up manner and calculate the max adjacent values.

5
5 10 10 2 3
2 11 3 10 10
16 12 1 5 2
4 2 11 5 2
1 8 14 4 13

Ans:60.Which for me 14 11 12 11 10 total 58.What am I missing here? Need help with that.

My code


#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=2e6+5,mod=1e9+7;

int mat[20][20],dp[20][20];
int main()
{
	int t,cnt=1;cin>>t;
	while(t--)
	{
		int n;cin>>n;
		for(int i=1;i<=n;++i)
		{
			for(int j=1;j<=n;++j)
			{
				cin>>mat[i][j];
			}
		}
		memset(dp,0,sizeof(dp));
		for(int i=1;i<=n;++i)
		{
			for(int j=1;j<=n;++j)
			{
				if(n&1)
				{
					if(j==(n+1)/2)
					{
						int temp=max(max(dp[i-1][j],dp[i-1][j-1]),dp[i-1][j+1]);
						dp[i][j]=max(dp[i][j],temp)+mat[i][j];
					}
					else if(j<(n+1)/2)
					{
						dp[i][j]=max(max(dp[i][j],dp[i-1][j]),dp[i-1][j+1])+mat[i][j];
					}
					else
					{
						dp[i][j]=max(max(dp[i][j],dp[i-1][j]),dp[i-1][j-1])+mat[i][j];
					}
				}
				else
				{
					if(j<=n/2)
					{
						dp[i][j]=max(max(dp[i][j],dp[i-1][j]),dp[i-1][j+1])+mat[i][j];
					}
					else
					{
						dp[i][j]=max(max(dp[i][j],dp[i-1][j]),dp[i-1][j-1])+mat[i][j];
					}
				}
			}
		}
		//cout<<endl;
		int ma=0;
		for(int i=1;i<=n;++i)
		{
			for(int j=1;j<=n;++j)
			{
				//cout<<dp[i][j]<<" ";
				ma=max(ma,dp[i][j]);
			}
			//cout<<endl;
		}
		cout<<"Case "<<cnt++<<": "<<ma<<endl;
	}
	return 0;
}

Comments (5)

Write comment?

Loser_

2 months ago, # |

Auto comment: topic has been updated by Loser_ (previous revision, new revision, compare).

→ Reply

Hafiz_

I think you are missing this line=> "Remember that each man should be paired with a woman and only monogamous families should be formed.".

If you take 14(5th man with 3rd woman) then you cannot take 11(4th man with 3rd woman).

The correct pairs will be like the following =>

10(1st man with 2nd woman), 10(2nd man with 4th woman), 16(3rd man with 1st woman), 11(4th man with 3rd woman), and 13(5th man with 5th woman).

2 months ago, # ^ |

Oh,thank you so much. I didn't get the problem statement.Will you discuss the approach here?

I didn't solve it yet and don't know how to solve it.

This problem is based on basic bitmasking. This video has exact similar problem explained so this might be helpful for others.Perhaps someone needs the solution is here also find another interesting solution for this problem is here

Loser_'s blog