### mochow's blog

By mochow, history, 4 years ago, ,

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.

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

 » 4 years ago, # |   +12 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; }