Reformulating Polish Sequences

For a sequence of non-negative integers \((V_1,\dots,V_N)\), consider the following path on a grid:

• Starting from \((0,1)\), for \(i=1,\dots,N\) in order, move up \(V_i\) units in the positive \(y\) direction, then move right \(1\) unit in the positive \(x\) direction.

A sequence being Polish is equivalent to this path eventually reaching \((N,N)\) without passing through \((0,0),\dots,(N-1,N-1)\). This can be proved by mathematical induction following the definition.

Case Analysis for Lexicographical Constraints

From this reformulation, we can determine whether \((A_1,\dots,A_N)\) is Polish in \(O(N)\).

Next, to handle sequences lexicographically less than \((A_1,\dots,A_N)\), we divide into cases. Specifically, we consider sequences starting with \((A_1,\dots,A_{i-1}, a)\) for \(i=1,\dots,N\) and \(a<A_i\). However, this would lead to \(O(N^2)\) cases with \(A_1+\dots+A_N\), so we need a better approach.

Observing the grid paths corresponding to sequences starting with \((A_1,\dots,A_{i-1}, a)\), we see they match the path for \((V_1,\dots,V_N)\) initially but deviate horizontally (positive \(X\) direction) at some point. The case analysis on \(i\) and \(a\) is essentially choosing where the path deviates. Since paths that exceed \(y\)-coordinate \(N\) can’t reach \((N,N)\), there are only about \(N\) candidates to actually try.

Counting

Now we just need to count for each case. In summary, we need to count the number of grid paths from \((x,y)\) to \((N,N)\) that don’t pass through \((0,0),\dots,(N-1,N-1)\) for \(O(N)\) coordinates \((x,y)\).

This can be solved using the same method as finding the general term of Catalan numbers using shortest paths (reference). Specifically, subtract the number of paths from \((y,x)\) to \((N-1,N)\) from the number of paths from \((x,y)\) to \((N-1,N)\).

Sample Implementation in C++