Complexity of the cardpath constraint

The cardpath constraint enforces a constraint C to be satisfied a given number of times over a sequence of variables. In this note, we give a polynomial propagation algorithm for a special case of this constraint, which in fact is the only case which was not known to be intractable