Codeforces 888F - Connecting Vertices

Problem Link:

http://codeforces.com/problemset/problem/888/F

Problem Statement:

There are n points marked on the plane. The points are situated in such a way that they form a regular polygon (marked points are its vertices, and they are numbered in counter-clockwise order). You can draw n - 1 segments, each connecting any two marked points, in such a way that all points have to be connected with each other (directly or indirectly).

But there are some restrictions. Firstly, some pairs of points cannot be connected directly and have to be connected undirectly. Secondly, the segments you draw must not intersect in any point apart from the marked points (that is, if any two segments intersect and their intersection is not a marked point, then the picture you have drawn is invalid).

How many ways are there to connect all vertices with n - 1 segments? Two ways are considered different iff there exist some pair of points such that a segment is drawn between them in the first way of connection, but it is not drawn between these points in the second one. Since the answer might be large, output it modulo 10⁹ + 7.

The first line contains one number n (3 ≤ n ≤ 500) — the number of marked points.

Then n lines follow, each containing n elements. a_i, j (j-th element of line i) is equal to 1 iff you can connect points i and j directly (otherwise a_i, j= 0). It is guaranteed that for any pair of points a_i, j = a_j, i, and for any point a_i, i = 0.

Print the number of ways to connect points modulo 10⁹ + 7.

Analysis:

The difficulty here is how to avoid double counting and how to store dp values.

The first observation we could made is that if we connect vertex i and j directly, the rest vertices are split into two parts, and vertices in each part can only connect to vertices in their own parts. This fact reminds us of the classical way of dynamic programming, i.e., the number of ways to connect vertices on a large interval is based on the number of ways to connect vertices on smaller intervals.

Next, how can we avoid double counting? We need to see some characteristics of the way of connecting the vertices on some interval. If we are to connect the vertices on the interval from l to r, i.e., connecting vertex l, l+1, …, r-1, and r, vertex l must directly connect to one or more of the vertices in the interval from l+1 to r, since the all vertices must be connected. We can split the situation into different cases, each case in which the last vertex in the interval vertex l connects to is different. Notice that if the last vertex vertex l connects to is vertex m in the interval, it does not follow that vertex l will not connect to any vertices other than vertex m, but what it really means is that all the other vertices that vertex l can connect to must come before vertex m in this interval. Then we can make the following claim: counting the ways of connecting vertices in the interval from different cases won’t count any distinct way of connecting the vertices more than once, and this is clear, as we have made the first observation. To handle the cases, we just need to calculate the ways of connecting vertices between vertex l and vertex m to vertex l or vertex m and the ways of connecting vertices between vertex m (inclusive) and vertex r (inclusive). The special case here is the case where we connect vertex l and vertex r directly, and we can handle this case by splitting the interval differently by iterating on the split point, and then connect the left part of the interval to vertex l and the right part of the interval to vertex r.

The DP Equations:

If we store the total number of ways of connecting vertices in interval from vertex l to vertex r in dp1[l][r], and the ways when vertex l and vertex r are directly connected in dp2[l][r], we can write the following equations:

dp2[l][r] = if(l and r can be connected) sum(dp1[l][m] * dp1[m+1][r]);

dp1[l][r] = sum(dp2[l][m] * dp1[m][r]);

Time Complexity:

O(n³)

AC Code:

 1 #include <iostream>
 2 #include <sstream>
 3 #include <fstream>
 4 #include <string>
 5 #include <vector>
 6 #include <deque>
 7 #include <queue>
 8 #include <stack>
 9 #include <set>
10 #include <map>
11 #include <algorithm>
12 #include <functional>
13 #include <utility>
14 #include <bitset>
15 #include <cmath>
16 #include <cstdlib>
17 #include <ctime>
18 #include <cstdio>
19 #include <memory.h>
20 #include <iomanip>
21 #include <unordered_set>
22 #include <unordered_map>
23 using namespace std;
24 
25 typedef long long ll;
26 
27 const ll md=1e9+7;
28 
29 int n;
30 int a[505][505];
31 ll dp1[505][505]; //stands for total ways
32 ll dp2[505][505]; //stands for ways to directly connect
33 
34 int main(){
35     scanf("%d",&n);
36     for(int i=0;i<n;i++){
37         for(int j=0;j<n;j++){
38             scanf("%d",&a[i][j]);
39         }
40     }
41     for(int i=0;i<n;i++){
42         dp1[i][i]=dp2[i][i]=1;
43     }
44     for(int i=1;i<n;i++){
45         for(int x=0,y=i;x<n;x++,y=(y+1)%n){
46             if(a[x][y]){
47                 for(int k=x;k!=y;k=(k+1)%n){
48                     dp2[x][y]+=dp1[x][k]*dp1[(k+1)%n][y];
49                     dp2[x][y]%=md;
50                 }
51             }
52             for(int k=x;k!=y;k=(k+1)%n){
53                 dp1[x][y]+=dp2[x][(k+1)%n]*dp1[(k+1)%n][y];
54                 dp1[x][y]%=md;
55             }
56         } 
57     }
58     printf("%I64d\n",dp1[0][n-1]);
59 }