Official

B - Quadruple Editorial by evima Editorial for printing


The large value of \(N\) makes it impossible to try all possible quadruples \((a,b,c,d)\). Let us first consider the following easier version of the problem:

  • Given integers \(N\) and \(K\), find the number \(f(N,K)\) of pairs of integers \((a,b)\) such that \(1 \leq a,b \leq N\) and \(a+b = K\).

We can find it with a simple formula; actually, we have \(f(N,K)=\min(K-1,2N+1-K)\) for \(K=2,3,\ldots,2N\). For example, the distribution of sums when roling \(2\) dice is \(1,2,3,4,5,6,5,4,3,2,1\) for \(K=2,..,12\).

Let us get back to the original problem. We can rephrase the condition as \((a+b) - (c+d) = K\), so let us first fix \(x = a+b\). Then, we can rewrite the condition as “\(a+b = x\) and \(c+d = x-K\)”, so this case contributes \(f(N,x) \times f(N,x-K)\) to the answer. Thus, we can find the answer by summing this value over \(x = 2,..,2N\).

The time complexity of this solution is \(O(N)\).

By the way, we can also solve this problem in \(O(1)\) using the inclusion-exclusion principle and so on.

posted:
last update: