SRM 574 div 1

275: A comb game problem, a straightforward approach is to use dp with memorization. A state is (a, b, turn, move)

bool check(int a, int b, int turn, int move)
// turn = 0 for Manao, 1 for the opponent, move is at most 1000
// a and b has only (10 choose 2) choices, so total number of states
// is around 100 * 100 * 2 * 1000 = 10^7
base case, or terminal states:
1. move = 1000, then, if turn = 1, return true, else return false, because Manao loses
2. a = b, then if turn = 0, return true, else return false, because Manao wins

Other cases:
1. reverse a
2. a div 10
3. reverse b
4. b div 10

call check(anew, bnew, 1-turn, 1+move)
if any of them is false, that means next player loses, then return true
else all of them are true, then this position is a lose position, return false

The solution is by calling check(A, B, 0, 1)

450:
The problem statement is the same as p1000 in div2, however now N can be as large as 18. Does backtrack still work? Should not be because the return type is long long, and one testcase clearly have ans more than 10^9, so an algorithm computes ans by increment of 1 will definitely TLE. How to count faster?

// this is like TSP problem, so think about O(2^n * n) algorithm
// given a prefix with last, we want to extend the prefix by node = next
// In this problem we need to know whether prefix intersects (last, next)
// so it appears we need to know the actual prefix, not only the mask of all
// nodes in prefix, but then the algorithm would be n factorial which is too slow!
//
// Now comes the observation: we only need to know the subset of nodes in prefix,
// to determine intersection, their order does not matter. Let S be the set of nodes
// in prefix, then S contains a pair (a, b) that intersects (last, next) if and only
// if S contains nodes both inside and outside the range of (a, b), regardless of
// how nodes in S are ordered. Because we only need to know whether S crosses
// (last, next) or not, this check is enough.

#include <cassert>
#include <algorithm>
#include <vector>
using namespace std;


long long dp[1<<18][20];  // careful, dp[1<<20][20] for long long will mem limit exceeded, SIGKILL

class PolygonTraversal
{
public:

bool inrange(int a, int b, int val)
{
    assert(a < b && a != val && b != val);
    return a < val && val < b;
}

bool cross(int a, int b, const vector<int> &vec)
{
    bool inside, outside;
    inside = outside = false;
    for (int i = 0; i < vec.size(); ++i) {
        int k = vec[i];
        if (inrange(a, b, k)) inside = true;
        else outside = true;
    }
    return inside && outside;
}

long long count(int N, vector <int> points)
{   
    for (int i = 0; i < points.size(); ++i) points[i]--;
    int start = 0;
    for (int i = 0; i < points.size(); ++i) start |= 1 << points[i];
    dp[start][points.back()] = 1;
       
    for (int mask = 0; mask < (1 << N); ++mask) if ((mask & start) == start) {  // mask contains start
        for (int last = 0; last < N; ++last) if (mask & 1 << last) {  // mask has last
            vector<int> prefix;
            for (int i = 0; i < N; ++i) if ((mask & 1 << i) && i != last)
                prefix.push_back(i);
            for (int next = 0; next < N; ++next) if (!(mask & 1 << next)) {  // next is not in mask
                int a, b;
                a = min(last, next); b = max(last, next);
                if (cross(a, b, prefix)) {
                    dp[mask | 1<<next][next] += dp[mask][last];
                }
            }
        }
    }
    long long ans = 0;
    for (int last = 0; last < N; ++last) if (last != points[0]) {
        vector<int> vec;
        for (int i = 0; i < N; ++i) if (i != points[0] && i != last) vec.push_back(i);
        int a, b;
        a = min(points[0], last); b = max(points[0], last);
        if (cross(a, b, vec))
            ans += dp[(1<<N) - 1][last];
    }
    return ans;
}  // end of method

};  // end of class

1000:Not read yet.

Conclusion: Had I been competing in div1, I should have p250, but no handle on 450 and 1000.

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...

CF 174

A: each operation, update sum and remember extra at the last element. When pop, add extra[last] to extra[last-1]. B: notice that we only have (pos, hop) states, where pos = 1 to n, hop = 0 or 1, meaning whether next is x + a[x] or x - a[x]. We can assume we start at pos > 1, because (x, y) is (1, 0) to begin with and the first move is necessarily pos=1 and hop = 0, after that since a[1] = 1 to n-1, so next pos must be greater than 1. So the start state is some (pos, hop=1) with pos >= 2. And it is not hard to see that if we ever have the same (pos, hop) appearing again, then it is a loop. Otherwise either we end at some (pos, hop) and next move get to pos out of bounds, that is, pos > n or pos <= 0. This will stop the sequence. The only remaining case is when pos = 1. Then if hop = 1, we know that next move is x - a[x], where we have x = 1 and a[1] >= 1, so next move must have pos <= 0, and the sequence will stop. The other case is that hop = 0, then we have next move is x + a[x] for x = 1. This will get us to next pos = 1 + a[1]. However, the only way we can get to this pos = 1 + a[1] is by starting at (x, y) = (1, 0) and when a[1] is set to the number such that pos = 1 + a[1], so we started at x=1 and val = a[1], and after some steps we are at x=1 again, and the next pos must be 1 + a[1], so we must have a loop (**this part is not clear as I would like to**). We have covered all cases and it is clear that we only need to do dfs for n*2 states, the graph has 2n nodes and 2n edges, given n = 10^5, it runs in time limit.

TC 573

Summary: failed 250 and that's it. Finally down to div 2.

250: Given an array of int, a[n], find max number of triples such that value(triple) > target.
value(triple) is min + max.

Solution: easy to see that if we sort a[n], then two pointers left and right going towards each other. Move left++ while left + right <= target. The pitfall is when we have left and right but there are only two elements remaining.

450: Given a graph with 50 nodes, each node has altitude[i]. edge[i][j] = 'Y' or 'N'. Find a path from 0 to N-1 such that each node has altitude[i] changed to b[i] and node[k-1] has height >= node[k] in path. Cost is sum of abs(altitude[i] - b[i]).

The hardest part is to figure out that optimal path only need b[i] to be one of a[0] .. a[N-1]
Then it is a shortest path problem with state being (pos, alt) meaning node[pos] is taking altitute[alt]
Could use either Dijkstra or Bellman-Ford.

Here is a sketch of proof:
// claim: there is an opt path uses a[i] altitude only
// proof: given an opt path, convert into a path uses a[i] only
// first break the path into blocks with each block using a[k] < b[i] < a[k+1]
// then what happens inside block does not affect outside
// for each block, we can shift the whole thing towards + or -, until one node hits some a[i]
// then we effectively break the block into several blocks and we recurse
// in the end we have an optimal path with each node takes some a[i] altitude only, and in
// every step we never increase the path cost.
//
// then the problem becomes a shortest path problem with vertex (i, j) indicating node[i] is having altitude a[j]

p850: this is wcao's solution

// this is a math problem
//
// 1. if we consider x[i] + y[i] for i = 0 to n-1,
// then the only way for i and j to meet is to 
// have x[i] + y[i] with the same parity as x[j] + y[j]
// because in every step, both change their parity
// so first check if all x[i] + y[i] must have same parity
// and ans is 0 if not
//
// 2. now we count the number of ways the wolves can meet
// first notice that the x and y are independent, we can
// count the number of ways x values meet and y values meet
// then just multiply them
// consider the minval and maxval of x, call it v
// then minval = v[n-1] - M and maxval = v[0] + M
// assuming v[0] .. v[n-1] are sorted
//
// there is a catch here, some wolf might have both odd parity for
// x and y, while some might have both even parity for x and y
//
// solution by wcao: since x[i] + y[i] and x[i] - y[i] uniquely determine
// x[i] and y[i], we can work on these two quantities instead, then both
// have same parity as M
//
// now we count for each val from minval to maxval
// for a given v[i], how many ways it can make to val
// let there be a count of a +1 and a count of b -1
// then a + b = M for M rounds
// a - b = val
// so the number of ways is (M choose a) which is (M choose (M+val)/2)
// notice that val must have the same parity with M to have nonzero result
//
// although I looked at wcao's solution, when implement it myself,
// integer overflow everywhere

#include 
#include 
#include 
using namespace std;

typedef long long int64;

const int MOD = (int)(1e9+7);

int fact[100000+5];
int invfact[100000+5];

class WolfPack
{
public:


int fastpow(int a, int b)
{
 int ans = 1;
 int base = a;
 while (b) {
  if (b&1) ans = (int64)ans * base % MOD;
  base = (int64)base * base % MOD;
  b /= 2;
 }
 return ans;
}

int inv(int a)
{
 return fastpow(a, MOD-2);
}

int comb(int n, int k)
{
 int deno = (int64)invfact[k] * invfact[n-k] % MOD; //cout << "deno " << deno << ' ' << inv(deno) << ' ' << fact[k] << ' ' << fact[n-k] << endl;
 int ans = (int64)fact[n] * deno % MOD;
 //cout << "comb " << n << ' ' << k << ' ' << ans << endl;
 return ans;
}

void init()
{
 fact[0] = 1;
 for (int i=1; i<100005; ++i) fact[i] = (int64)fact[i-1] * i % MOD;
 //for (int i=0; i < 10; ++i) cout << fact[i] << endl;
 for (int i=0; i<100005; ++i) invfact[i] = inv(fact[i]);
}


int calc(vector  v, int m)
{
 sort(v.begin(), v.end());
 int minval, maxval;
 int n = v.size();
 int64 ans = 0;
 for (int i = 1; i < n; ++i) if ((v[i] & 1) != (v[0] & 1)) { return 0; }
 minval = v[n-1] - m;
 maxval = v[0] + m;
 for (int val = minval; val <= maxval; val += 2)  // val and m must be same parity
 {
  int tmp = 1;
  for (int i = 0; i < n; ++i) {
   int diff = abs(val - v[i]);
   tmp = (int64)tmp * comb(m, (m - diff)/2) % MOD; //cout << tmp << ' ' << val << ' ' << i << ' ' << v[i] << ' ' << diff << endl;
  }
  //ans = ((int64)ans + tmp) % MOD;
  ans += tmp;
  if (ans >= MOD) ans -= MOD;
 }
 return ans;
}

int calc(vector  x, vector  y, int m)
{
 int n = x.size();
 init();
 vector a(n), b(n);
 for (int i = 0; i < n; ++i) {
  a[i] = x[i] + y[i];
  b[i] = x[i] - y[i];
 }
 return (int64)calc(a, m) * calc(b, m) % MOD;
}
};

CF 172

A: a geometry problem but difficult to implement nonetheless.

B: For each item a[i], if it serves as the second maximum element in the range, then the only choice for first maximum element would be the first one to the left that is larger, or the first one to the right that is larger. Now this looks very similar to the maximum rectangle problem in which you need the first smaller to the left and the first smaller to the right. For problem B you maintain a stack with decreasing elements and a[i] kills the top of stack until the top of stack is larger than a[i], then you push a[i] into stack. Every time you pop an item, called curr out of stack, update ans with curr xor st.top() and curr xor a[i], the one that caused curr to pop. Time complexity O(n)

C: This one is tricky when you look at the problem. If it is a list instead of a tree, then it is easy, because after removing some element, you get a shorter list. However for trees you can have potentially a larger number of different trees when a subtree gets pruned from the input tree.

Now look at it differently and consider each node individually. What is the chance of a node get selected in a step and hence contribute 1 to the final cost. Things happen in other places do not matter, and the only thing that matters is whether some nodes in the path from this node to the root gets selected or not, and since we select each remaining node with equal probability, the only way a node can get selected is to get selected before any of its ancestor, and the probability is 1/depth[i] for node a[i], and this probability remains the same until one node in the path from a[i] to root a[1] gets selected and then we are done with a[i]. So the expected total number of steps is:
sum over i=1 to n, 1/depth[i]

This is reminiscent of the analysis in randomized quicksort when you need to find the probability that two items get 1 comparison or never compared. You get 1 comparison if one of them gets chosen as pivot before any other item in between becomes a pivot, in which case the two items will enter separate partition and never compared.

mesos build on Ubuntu 12.04 LTE

Hey Flo, run configure with --disable-perftools.


./bootstrap
mkdir build
../configure --with-webui --with-included-zookeeper
make
make check
# I correctly guess that the error below is due to running without sudo :)
[  FAILED  ] 19 tests, listed below:
[  FAILED  ] CgroupsIsolationTest.ROOT_CGROUPS_BalloonFramework
[  FAILED  ] CgroupsAnyHierarchyTest.ROOT_CGROUPS_Enabled
[  FAILED  ] CgroupsAnyHierarchyTest.ROOT_CGROUPS_Subsystems
[  FAILED  ] CgroupsAnyHierarchyTest.ROOT_CGROUPS_Mounted
[  FAILED  ] CgroupsAnyHierarchyTest.ROOT_CGROUPS_Get
[  FAILED  ] CgroupsAnyHierarchyTest.ROOT_CGROUPS_NestedCgroups
[  FAILED  ] CgroupsAnyHierarchyTest.ROOT_CGROUPS_Tasks
[  FAILED  ] CgroupsAnyHierarchyTest.ROOT_CGROUPS_Read
[  FAILED  ] CgroupsAnyHierarchyTest.ROOT_CGROUPS_Write
[  FAILED  ] CgroupsAnyHierarchyWithCpuMemoryTest.ROOT_CGROUPS_Busy
[  FAILED  ] CgroupsAnyHierarchyWithCpuMemoryTest.ROOT_CGROUPS_SubsystemsHierarchy
[  FAILED  ] CgroupsAnyHierarchyWithCpuMemoryTest.ROOT_CGROUPS_MountedSubsystems
[  FAILED  ] CgroupsAnyHierarchyWithCpuMemoryTest.ROOT_CGROUPS_CreateRemove
[  FAILED  ] CgroupsAnyHierarchyWithCpuMemoryTest.ROOT_CGROUPS_Listen
[  FAILED  ] CgroupsNoHierarchyTest.ROOT_CGROUPS_MountUnmountHierarchy
[  FAILED  ] CgroupsAnyHierarchyWithCpuAcctMemoryTest.ROOT_CGROUPS_Stat
[  FAILED  ] CgroupsAnyHierarchyWithCpuMemoryFreezerTest.ROOT_CGROUPS_Freeze
[  FAILED  ] CgroupsAnyHierarchyWithCpuMemoryFreezerTest.ROOT_CGROUPS_Kill
[  FAILED  ] CgroupsAnyHierarchyWithCpuMemoryFreezerTest.ROOT_CGROUPS_Destroy

TCO 13 round 1B

This could have been my first ever successful submission to 500 and 1000, although I did not take the competition for other work. Anyway this round seems easier than most div1 SRM. Here are my solution:

250: sort and add a[0], a[n-1], then a[1], a[n-2],  and keep track of min and max.

500: try all 2^15 possible moves for rows, then you have a fixed choice for col moves.

1000: two strings would match if and only if break them down to pairs of letters, a[0] with a[1], and a[2] with a[3], ... and the pairs match (either a[2*i] to b[2*j] and a[2*i+1] to b[2*j+1], or a[2*i] to b[2*j+1] and a[2*i+1] to b[2*j])

And you only need to find one word, then iterate through the rest to find a match, cross both. Repeat until no more word can be matched.