PolygonAndPermutations

You are given K equally long line segments. On each line segment there are N marked points (all distinct from each other and from the segment's endpoints). The points on each segment have distinct labels from 1 to N, so they form a permutation. For each line segment you are given this permutation - the list of point labels from one end to another.

You are going to use these K line segments to build a regular polygon with K sides. Note that it is allowed to turn the segments "upside down" so that the permutation appears in reverse order.

Once the polygon is built, we will draw some new line segments: we will connect each pair of points that shares the same label. See the figure below for an example.

You get to choose the correct way in which the segments should be placed on the boundary of the polygon. Your task is to minimize the number of pairs of line segments which intersect strictly inside the polygon. Intersections on the boundary of the polygon do not count. For example, in the figure shown above there are 14 pairs of line segments which intersect strictly inside the polygon.

Return the smallest possible number of intersecting pairs of line segments.

In order to keep the input size small, the permutation for each line segment is generated pseudorandomly. Below we give the C++ and Java code for this generation.

C++:

long long xx, pr;

long long get_random() {
    xx = xx % 1000000007;
    long long temp = (xx*xx + pr) % 1000000007; 
    pr = xx;
    xx = temp;
    return xx;
}

vector<int> permutation(int n) {
    vector<int> cur(n), res;
    for(int i=0; i<n; ++i) cur[i] = i+1;
    for(int i=0; i<n; ++i) {
        int tmp = get_random() % (n-i);
        swap( cur[n-i-1], cur[tmp] );
        res.push_back(cur[n-i-1]);
    }
    return res;
}

long long solve(int K, int N, long long seed) {
    xx = seed;
    pr = 0;
    vector< vector<int> > segments(K);
    for (int i=0; i<K; ++i) segments[i] = permutation(N);
    // find the optimal solution for the segments described by segments[][]
}

==============================================================================

Java:

long xx, pr;

long get_random() {
    xx = xx % 1000000007;
    long temp = (xx*xx + pr) % 1000000007; 
    pr = xx;
    xx = temp;
    return xx;
}

int[] permutation(int n) {
    int[] cur = new int[n];
    int[] res = new int[n];
    for(int i=0; i<n; ++i) cur[i] = i+1;
    for(int i=0; i<n; ++i) {
        int tmp = (int)(get_random() % (n-i));
        int foo = cur[n-i-1];
        cur[n-i-1] = cur[tmp];
        cur[tmp] = foo;
        res[i] = cur[n-i-1];
    }
    return res;
}

long solve(int K, int N, long seed) {
    xx = seed;
    pr = 0;
    int[][] segments = new int[K][];
    for (int i=0; i<K; ++i) segments[i] = permutation(N);
    // find the optimal solution for the segments described by segments[][]
}