SRM 574 div 2

This time I was downgraded to div2 and was having an easier time. The good news is that I got back to div1 with a rank of 80 in div2.

Summary: got 250 and 500 without much effort, but was not able to finish 1000, a simple backtrack problem after 60 minutes!

250, count for 'A' to 'Z', then print.

500, I use bfs since the number of nodes is bounded by n^2, the string for each node is substr(i,j) and we have forward and backward, for a total of n^2 possible strings. Another solution is to notice that the optimal solution is to cut a prefix and a suffix and possibly reverse, so you can try to find B in A or Areverse, and count the cost. Notice you get a better cost if B is a prefix of A since you can save a reverse cost of 1. Notice also that you never need to do more than 1 reverse.

1000, the constraint N is so small, N=13, and each sequence must end after all N nodes were present. You know we start with at least 2 nodes, so the remaining sequence is at most 11 factorial, which is about 10^8. The only tricky part is to check whether two pairs (i1,j1) and (i2,j2) intersect. Assume i1 < j1 and all i1,j1,i2,j2 are distinct. Then they intersect iff i2 is in range(i1,j1) and j2 is not, or vice versa. The solution is a dfs with backtracking. Each node maintains current neighbor, which goes from 1 to N. In each move we either extend the search path by one more node, or hit the end, in this case if (last, first) intersects some other pair, then we get one more solution. the remaining case is a nodes exhausted all its neighbors 1 to N. In this case and the dead end case we backtrack by popping from the end of the path. We stop when we try to pop the original points. One invariant that helps is to init neighbor to 0, then in each iteration we start with prev neighbor + 1, this guarantees we skip the previous neighbor.

Alternative solution, notice that each feasible solution is a sequence of points followed by a permutation of the remaining elements. And we can generate all such permutations, only 13 - 3 = 10 factorial of them. One catch is that when points have size 2, this case we immediately return 0. In TC server, 11 factorial will TLE.

Code below:

class PolygonTraversal2
{
public:
    bool inrange(int lo, int hi, int val)
    {
        assert(lo < hi);
        return (lo < val && val < hi);
    }

    bool intersect(int a, int b, int c, int d)
    {
        int x, y;
        x = min(a, b); y = max(a, b);
        bool ans1 = inrange(x, y, c) && !inrange(x, y, d);
        bool ans2 = !inrange(x, y, c) && inrange(x, y, d);
        return ans1 || ans2;
    }

    bool cross(int a, int b, vector list) {
        for (int i = 0; i+1 < list.size(); ++i) {
            if (intersect(a, b, list[i], list[i+1]))
                return true;
        }
        return false;
    }

    int count(int N, vector points)
    {
  int ans = 0;
  if (points.size() < 3) return 0;
  // generate all permutations, only 13-2=11 factorial
  vector rem;
  for (int i = 1; i <= N; ++i) {
   bool used = false;
   for (int j = 0; j < points.size(); ++j)
    if (points[j] == i) { used = true; break; }
   if (!used) rem.push_back(i);
  }
  sort(rem.begin(), rem.end());
  do {
   bool good = true;
   vector prefix = points; prefix.pop_back();
   for (int i = 0; i <= rem.size(); ++i) {
    int prev, curr;
    if (i == 0) { prev = points.back(); curr = rem[i]; }
    else if (i == rem.size()) { prev = rem.back(); curr = points[0]; }
    else { prev = rem[i-1]; curr = rem[i]; }
  
    if (!cross(prev, curr, prefix)) { good = false; break; }
    prefix.push_back(prev);
    if (prefix.size() >= N-1) prefix.erase(prefix.begin());
   }
   //cout << good << endl;
   if (good) { ans++; }
  } while (next_permutation(rem.begin(), rem.end()));
        return ans;
    }
  

};

Conclusion: I think I am done with div2 problems for this SRM. I guess those red coders are seeing div1 problems as the way I am seeing div2 problems...