PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: raysh07 and iceknight1093
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Easy
PREREQUISITES:
Factorization
PROBLEM:
There’s a robot at (0, 0), initially facing the positive X-axis.
For an array A of length M, it will do the following:
- Iterate i in order from 1 to M.
- Move A_i units in the direction it’s currently facing.
- Then, turn 90^\circ either clockwise or anticlockwise.
Define f(A) as the number of distinct possible final positions the robot can end up at, for the array A.
Given an integer N, compute the length of the smallest array for which f(A) = N, or claim that no such array exists.
EXPLANATION:
To solve this problem, we need to understand how exactly f(A) is computed from a given array A.
For convenience, we’ll call the positive/negative X-axis the directions “right” and “left” respectively.
Similarly, the positive/negative Y-axis will be called directions “up” and “down”, respectively.
So, the robot starts out facing right. Then,
- It moves A_1 units right, and then turns to face either up or down (both are possible).
- It moves A_2 units in the direction it’s facing, then turns to face either right or left (both are possible, irrespective of whether it is facing up or down).
- It moves A_3 units in the direction it’s facing, then turns to face either up or down (again, both options are always possible).
\vdots
In general, the robot will always face right on its first move.
After that, for each even-indexed move it will always face either up or down, and for each odd-indexed move it will always face either left or right - and any combination of directions is allowed.
This means the robot’s final x-coordinate is determined purely be the odd-index elements of A, while its y-coordinate is determined by the even-index elements.
In particular,
- The robot’s final x-coordinate will be
A_1 \pm A_3 \pm A_5 \pm A+7\pm\ldots - The robot’s final y-coordinate will be
\pm A_2\pm A_4\pm A_6\pm\ldots
Here, \pm means we can choose either the + or the - sign for that element, and any such combination is valid.
Since the x-coordinates and y-coordinates are independent, the total number of distinct final positions the robot can reach equals the product of the number of distinct x-coordinates and the number of distinct y-coordinates.
This brings us to the question: if we have an array B of some length M, how many distinct sums of the form \pm B_1 \pm B_2 \pm\ldots \pm B_M does it have?
The answer to that is in fact quite simple: it’s just the number of distinct subset sums of B!
Proof
Let’s start by giving every element the + sign, to obtain a sum of B_1 + B_2 + \ldots + B_M.
Now, for each index i, we can either leave the sign at + and nothing changes, or we can change the sign to - and the sum changes by -2B_i.
This choice is independent, so the overall change we can obtain is just any subset sum of the set
\{-2B_1, -2B_2, \ldots, -2B_M\}.The -2 is a common multiplier and doesn’t affect the number of distinct sums that can be reached, so factoring it out tells us that the count itself simply equals the number of distinct subset sums of \{B_1, B_2, \ldots, B_M\}, which is what we wanted to show.
So, going back to our initial problem: for an array A,
- The number of distinct y-coordinates equals the number of distinct subset sums of \{A_2, A_4, A_6, \ldots\}.
If N is even there are \frac{N}{2} elements here, otherwise there are \frac{N-1}{2}. - The number of distinct x-coordinates equals the number of distinct subset sums of \{A_3, A_5, A_7, \ldots\}.
Note that A_1 is excluded here because it’s always given the + sign, so it just shifts the sum obtained from the other elements by A_1 but cannot create any new sums.
If N is even there are \frac{N}{2}-1 elements here, otherwise there are \frac{N-1}{2}.
The next question that comes up is: if we have an array of some length K containing positive integers, how many distinct subset sums can it have?
An obvious upper bound on this quantity is 2^K, since there are only 2^K subsets at all.
It’s not hard to see that 2^K can be reached: for example take
B = [2^0, 2^1, 2^2, \ldots, 2^{K-1}] and all subset sums will be distinct.
Because the elements are positive, a lower bound on the count is also K+1, since we’ll always have the sums 0, B_1, B_1+B_2, B_1+B_2+B_3, \ldots, B_1+B_2+\ldots+B_K.
It’s not hard to see that this is always achievable too: for example by [1, 1, 1, \ldots, 1].
What about counts between K+1 and 2^K?
It turns out, all of them are achievable too!
Proof
This turns out to be quite simple if we use induction.
We’ll prove something even stronger: given K, for any K+1 \leq x \leq 2^K it’s possible to create an array of positive integers that has exactly x distinct subset sums, with these sums being \{0, 1, 2, 3, \ldots, x-1\}.
First, look at K = 1.
Our claim is that all counts between K+1 and 2^K are achievable, but for K = 1 both of these are 2.
Of course, any array of size 1 containing a positive number will have exactly two distinct sums: 0 (from the empty subset) and the positive number.
By taking the array [1], we obtain an array with the sums 0 and 1.
So, the hypothesis is true for K = 1.Now, suppose the claim is true for some K. We’ll extend it to K+1.
Consider some x such that (K+1)+1 \leq x \leq 2^{K+1}.
In particular, note that K+1 \leq x-1.There are two possibilities:
- x \leq 2^K+1
Here, because K+1 \leq x-1, we have K+1 \leq x-1 \leq 2^K.
So, by the inductive hypothesis we can create an array of length K whose subset sums are exactly the set \{0, 1, 2, \ldots, x-2\}.
Let A be one such array. Simply append 1 to A, to form the array [A_1, A_2, \ldots, A_K, 1], and we obtain an array of length K+1 with subset sums \{0, 1, 2, \ldots, x-1\}, as desired.- x \gt 2^K + 1.
Here, we can take the array [1, 2, 4, 8, \ldots, 2^{K-1}] of length K which has all subset sums in [0, 2^K-1], and then append x - 2^K to it.
This results in all subset sums in [0, x-1], as desired.By induction the claim is thus true for all K.
This allows us to run the following algorithm.
Let’s fix the length N of the array A.
We then obtain the number of elements at even/odd indices: either \left(\frac{N}{2}, \frac{N-1}{2}\right) or \left(\frac{N}{2}-1, \frac{N-1}{2}\right) as seen above.
Whatever it is, let these counts be (N_1, N_2).
Let [L_1, R_1] be the range of subset sums corresponding to N_1, and [L_2, R_2] be the range corresponding to N_2.
Now what we want to know is: do there exist integers d_1 and d_2 such that:
- L_1 \leq d_1 \leq R_1
- L_2 \leq d_2 \leq R_2
- d_1\times d_2 = N
If such integers do exist, we can of course obtain f(A) = N by having d_1 distinct x-coordinates and d_2 distinct y-coordinates.
The question now is, how do we check this quickly?
The most obvious solution is to just iterate through all the divisors of N as d_1, check if it satisfies the condition, and then check if d_2 = \frac{N}{d_1} satisfies the condition.
The complexity of this is \mathcal{O}(d(N)\cdot \text{ans}), where d(N) equals the number of divisors of N and \text{ans} is the final answer.
Quite nicely, this approach is indeed fast enough!
The key here is to note that \text{ans}, if it exists at all, cannot be very large: a simple upper bound is 65, for example.
This is because, with N = 65, we’ll have (N_1, N_2) = (32, 32), meaning both parts will have the corresponding range [33, 2^{32}] of possible distinct subset sums.
Note that 2^{32} \gt N, so every factor of N is small enough to fit into the range for sure: the only issue now is that the factor might be so small (\lt 33) that it doesn’t fit in the range.
But, if N is increased further, the lower bound and upper bound will only increase: so any factor that’s too small now will still be too small in the future; which is why checking N \gt 65 is pointless.
So, we can simply check for N = 1, 2, 3, \ldots, 65.
If any of them are valid, the smallest valid N is the answer; otherwise print -1.
Since we have N \leq 10^9, we have d(N) \leq 1344.
The complexity of this approach is hence bounded by \mathcal{O}(\sqrt N) + 1344\cdot 65, which for 1000 testcases will run in time without issue.
TIME COMPLEXITY:
\mathcal{O}(\sqrt N + d(N)\cdot \text{ans}) per testcase, where d(N) \leq 1344 and \text{ans} \leq 65.
CODE:
Editorialist's code (PyPy3)
def getrange(k):
return k+1, 2**min(k, 31)
for _ in range(int(input())):
n = int(input())
facs = []
d = 1
while d*d <= n:
if n%d == 0:
facs.append(d)
facs.append(n//d)
d += 1
ans = -1
for L in range(1, 66):
even, odd = L//2, (L-1)//2
l1, r1 = getrange(even)
l2, r2 = getrange(odd)
for d1 in facs:
if l1 <= d1 <= r1 and l2 <= n//d1 <= r2:
ans = L
if ans != -1: break
print(ans)