mochow's blog

By mochow, history, 4 years ago, In English,

I was trying to solve this problem from ICL2015div2 finals. I understand this is a problem on combinatorics (and perhaps DP) but I could not find a way towards solution.

Problem Link

I am weak in DP problems. They seem overwhelming to me most of the times. An elaborate explanations will surely be helpful for me. :)

Thanks in advance.

 
 
 
 
  • Vote: I like it
  • +8
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +12 Vote: I do not like it

You're right, it is a DP problem. So here's my solution:

using namespace std;

typedef long long ll;
int n , k;
ll d[100][100];
//d[i][j] = the answer of the problem for n = i , k = j

int main(){
    cin >> n >> k;
    d[0][0] = 1;
    for (int i = 1 ; i <= n ; i++)
	 for (int j = 0 ; j <= k ; j++){
	     //if j == 0 -> there is only one possible way to put 0 lines between i contacts 
	     if (j == 0){
		  d[i][j] = 1;
		  continue;
	     }	
  
	     //each line connects two contacts
	     //so if j > i / 2, no matter how we put the j lines between the contacts
	     //there is always a contact whom at least two lines are connected to him, so those two lines intersect
	     //so the answer is 0
	     if (j > i / 2){
		  d[i][j] = 0;
		  continue;
	     } 
	     
	     //there are two ways to put j lines between i contacts:
	 
	     //1_no lines connect the last contact to another contact
	     d[i][j] += d[i - 1][j];

	     //2_the last contact gets connected to another contact:
	     //the line connecting the last contact to another contact
	     //_I call this line "line x"_
	     //divides the circuit 
	     //into two parts in such way that contacts on each part can only get connected to each other
	     //(otherwise, they intersect with "line x")
	     for (int p = i - 1 ; p > 0 ; p--){
		  int a = i - p - 1 , b = p - 1;
		  //the first part contains a contacts, and the second one b contacts
		  //so we need to put (j - 1) lines in these parts in the required way
		  //there are (j - 1) ways to do that, the ith way is to put i lines in the
		  //first part and ((j - 1)-i) lines in the second part
		  for (int z = 0 ; z <= j - 1 ; z++)
		      d[i][j] += ll(d[a][z] * d[b][(j - 1) - z]);
	     }
	 }
    cout << d[n][k] << endl;
    return 0;
}