Problem Link
Author: Noszály Áron
Tester: Misha Chorniy
Editorialist: Bhuvnesh Jain
Difficulty
MEDIUM
Prerequisites
Factorisation, Combinatorics
Problem
You are given N workers and each of them has a deadline to complete the work, given by d_i for i^{th} worker. Each worker completes the work in 1 day and on each day at most 1 worker can work. You need to decide to the array containing the deadline for every worker such that the number of ways in which the workers can decide to work is C and d_n is minimised. Also, the array of deadlines should be sorted.
Explanation
Before proceeding towards the solution, we need to find the number of ways in which workers can decide to work for a given array d_1 ≤ d_2 ≤ \cdots ≤ d_n.
Consider the case for n ≤ 3. Let d_1 = x, d_2 = y, d_3 = z. We have the following dynammic programming solution
Using the above observations, it is clear that number of ways is \prod_{i=1}^{i=n} {(d_i - i + 1)}. We can even prove it combinatorially. The first person has d_1 choices, the second one has (d_2 - 1) choices and so on. By the principle of multiplication, the number of ways comes out to be same.
Note the above solution clearly points out that d_i >= i. Thus for C = 1, the array is (1, 2, 3, 4, \cdots).
Thus, the problem now reduces to finding an array d_1 ≤ d_2 ≤ \cdots ≤ d_n such that \prod_{i=1}^{i=n} {(d_i - i + 1)} = C and d_n is minimised.
Instead of finding d_1, d_2 \cdots d_n, we will find sorted array, d_1, (d_2-1), \cdots, (d_n-n+1), such that product of this sequence is C and later add back (i - 1) to every term to ensure that sequence is increasing.
Subtask 1: N ≤ 10, C ≤ 100
We can use dynamic programming based solution for this subtask. Let dp[N][C] denote the minimised value of d_n for which the sequence d_1, d_2, \cdots, d_n has number of ways as C. The transitions are simple. Let dp[N][C] = x. So, we need to find the minimum value for the sequence with (N - 1) terms and product as (C/x). The possible candidates are the divisors of (C/x). So, we try all possible candidates and update our answer whether or not it is possible to form an array with the tried candidate. Once, the dynamic programming table is built, we can simply backtrack it to print the answer.
The time compleixty of the above approach is O(N * {\sigma_{0}{(C)}}^2), where \sigma_{0}{(C)} denotes the number of divisors of C.
For details, you can refer to author’s solution for the above approach.
Subtask 2, 3: N ≤ {10}^6, C ≤ {10}^9
We may see that for optimal answer, the sequence d_1, (d_2-1), \cdots, (d_n-n+1), looks like the following for large n:
[zero or more numbers greater than 1] [bunch of ones] [zeros or more numbers greater than 1]
Outline of proof for above claim: Basically we want to show that if we have a solution that is not in the above form, then there’s a solution of the above form which has the same last element. We achieve this by moving the blocks of non 1 elements as a unit, in this part, we will use the monotonicity of array d as an argument to show that the blocks are indeed movable and don’t break anything.
The above form is important because increasing N actually just pushes more ones into the middle (if there were a better way to distribute the numbers we would have used it earlier). So to solve, we calculate the optimal sequence for smaller N and then extend the “bunch of ones” in the middle.
In the worst case the above method’s complexity is O(N + (\text{number of prime factors of C}) * {\sigma_{0}{(C)}}^2). Because the number of prime factors in the range of {10}^9 is 30 in the worst case and the number of divisors is 1000 in the worst case, this gives around 3 * {10}^7 operations per test case.
For more details, you can refer to the setter’s or tester’s solution below.
Editorialist Solution: Based on solutions by contestants in the contest (Greedy approach)
Incorrect Solution: Note that the below solution is wrong for small values of N. This is because it is not guaranteed that choosing the largest factor at every moment in the below solution will yield an optimal solution. It though will work for cases where N > \log{C} as even the greedy approach will take O\log{C} steps to check optimality for the answer. For details refer to the below comments for some counter cases. Note that in all the test case N ≤ \log{C}.
We will first store all the factors of C. Now, we traverse the factors one by one and check if we can form an array d_1, (d_2-1), \cdots, (d_n-n+1), such that the last element is given factor. Is yes, we simply update the answer. Below is the pseudo-code for checking whether we can find an array with the last element as given factor x.
# facts store the factors of C.
# facts[idx] = x
def check(idx):
ptr = n
prod = c
while ptr > 0:
while prod % facts[idx] != 0
idx -= 1
prod /= facts[idx]
ans[ptr] = facts[idx] + ptr - 1
ptr -= 1
if idx != len(facts)-1 and facts[idx] == (facts[idx+1] - 1):
idx += 1
if idx == 0 or prod == 1:
break
return (prod == 1)
Let us analyse the above pseudo-code. We first try to greedily find the first largest factor of the remaining product. At first step it will be facts[idx] = x, the number we want to check. Since in final array we want d_{(i-1)} ≤ d_i and we are finding array (d_i - i + 1), the previous term can now contain a possible larger factor only if it is greater than the previous factor by 1. The last condition just checks that if the product has become 1, then we know the trivial answer or if the factor to be considered is 1, the product will remain same. Below is an example iteration of the above for N = 8 and C = 36. Let the factor to be checked is x = 2.
Since the prod now becomes 1 we break. To build the required array we add the offsets (i - 1) to the array.
Thus, required array is (1, 2, 3, 4, 6, 8, 9, 9). Note that this may or may not be the optimal solution. It just shows how we check if a given factor can form the series if it is the last term in the sequence.
The time complexity of the above approach will be O({\sigma_{0}{(C)}}^{2} + N). This is because, for every factor, the checking will take O(\log{C}) step in the worst case as “prod” variable will decrease by a factor of atleast 2 in each iteration. But the dominating factor will be the while loop which determines the optimal factor in each iteration and can take up to \sigma_{0}{(C)} operations. The second term, O(N), is for building the complete sequence containing the initial trivial part of (1, 2, 3, \cdots) and printing the answer. The space complexity will be O(N + sqrt(C)).
Once, you are clear with the above idea, you can see the editorialist implementation below for help.
Feel free to share your approach, if it was somewhat different.
Time Complexity
O(N + (\text{number of prime factors of C}) * {\sigma_{0}{(C)}}^2)
Space Complexity
O(sqrt(C) + 1000 * sqrt(C) + N), where 1000 denotes the value of small N used by author to solve problem by dynamic programming.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.
Editorialist’s solution can be found here. ( Incorrect )
