WRKWAYS - Editorial

Problem Link

Practice

Contest

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

dp[x] = x
dp[x][y] = dp[x] * (y - x) + dp[x-1] * x = xy - x^2 + x^2 - x
dp[x][y] = xy - x = (y-1) * dp[x]
dp[x][y][z] = dp[x][y] * (z - y) + dp[x][y-1] * (y - x) + dp[x-1][y-1] * x
dp[x][y][z] = (xy - x)(z - y) + (xy - 2x)(y - x) + (xy - 2x - y + 2)x
dp[x][y][z] = (xyz - xz - 2xy + 2x) = (z - 2) * (xy - x)
dp[x][y][z] = (z - 2) * dp[x][y]

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.

\text{facts} = {1, 2, 3, 4, 6, 9, 12, 18, 36}
\text{Step 1} = {\cdots, 2}
\text{Step 2} = {\cdots, 3, 2}
\text{Step 3} = {\cdots, 3, 3, 2}
\text{Step 4} = {\cdots, 2, 3, 3, 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 )

2 Likes

I had used precisely same approach for this problem, but kept getting WA for one file in last sub-task. Can anyone tell me what’s wrong with this solution?

My approach uses another observation: That If a given factor is placed at end of array, we can reduce d[n] by c, where c is the size of consecutive block of numbers d[n]-1, d[n]-2d[n]-c that can be simultaneously formed using factors of c and remaining factors can be split into n-c-1 terms such that maximum of all those terms is less than or equal to d[n]. (Can be proved)

So, I calculate c for all factors and select the factor which minimize factor-c which is same as d[n]-n+1

Would be thankful if someone can point out any error in above solution.

2 Likes

Is this problem NP-Hard?

No, Check the complexity of above solution

Though the expected solution passes time limit but seriously it shouldn’t pass. I wrote my code similar to yours and submitted it, and I was searching for different way, I didn’t expect that to pass, but I got astonished when it passed all test files.

Like time complexity is 3*10^7 per test case i,e for t= 100, it is 3*10^9 overall, seriously do you think that it will pass. When a code with 10^8 operations doesn’t usually pass in one minute than how can this (30 times more) can pass in that.

Think of those who code a problem only after checking the time complexity of their logic, if suppose a few of them didn’t even implement this logic because they were thinking that there must exist a better approach. This is unfair to them.

I am getting WA only for for subtask 3 task 7.Please help. Here’s what I did
First store all the factors of C into a vector.
C=c1c2c3…cn (we get sequence of d by adding i-1)
c(i)-c(i+1)>=-1 (if violated sequence of d will not be increasing)
Now do binary search on the factors of C (assigning cn a value of a factor)
and check whether it is possible to get a factorisation with condition mentioned.
if it is possible try to find a lower value of factor else find a higher value of factor satisfing the condition.
Complexity(O(N*log(no of factors of C))
Link to the solution-https://www.codechef.com/viewsolution/18861133

And what complexity makes that problem become NP-Hard?

It is clearly mentioned sum of N over all test case is {10}^{7}. So, number of test cases can be 10 in that case. The complexity and time limits are correct. Read the constraints for the problem again.

That is exactly what I’ve done too.
But it was failing for the second last test case. :frowning:

Is there any way to get the test case itself?

@taran_1407:
I can’t reply directly to your comment, thus this seperate comment.
My solution failed at the same testcase as yours. It seems the binary search is not adequate here.

Example:

1
4 735134400

We can write 735134400 as 170 x 168 x 165 x 156.

But if we start with 175 which is greater than 170, we get the sequence of divisors : 175 -> 156 -> 153 -> 88 whose product is not 735134400.

2 Likes

I am facing same result. Share the test case if you find it.
https://www.codechef.com/viewsolution/18888868

Can u give other test case cuz my code is getting right op for your case
https://www.codechef.com/viewsolution/18888868

@shawnbam_96:

5
4 294053760
5 21621600
5 367567200
5 720
5 840

Your output :

112 136 138 146 
21 26 34 36 43 
34 55 57 59 69 
6 6 6 6 6 
7 7 7 7 

In the last line, your solution outputs only 4 numbers.

Author’s solution output :

126 131 134 139 
26 29 32 33 37 
45 53 53 59 59 
6 6 6 6 6 
1 8 8 8 8

@likecs: your solution gets AC, but fails the following:

9
4 221760
4 2882880
4 294053760
4 367567200
5 21621600
5 32432400
5 367567200
5 551350800
5 698377680

https://ideone.com/ofZ3yB

Author’s solution output :

22 22 22 27 
40 40 44 47 
126 131 134 139 
136 136 142 146 
26 29 32 33 37 
26 31 35 39 39 
45 53 53 59 59 
52 52 57 63 67 
51 58 58 69 69 
4 Likes

How did you find these test cases??

I spent nearly my whole long challenge generating random numbers and finding answers.

I used highly composite numbers, and I checked using the author’s solution. And for the case where your solution outputs less than n numbers, it was just by chance.

1 Like

Thanks for the case @khalid545

Hi! I was wondering why in the editorialist’s approach the complexity has \sigma_{0}(C)* logC instead of (\sigma_{0}(C))^2. This section of code :

while prod % facts[idx] != 0
            idx -= 1

can execute multiple times before we reach an idx for which the condition satisfies.

2 Likes

@khalid545, thanks for the test cases. This points out that test data was weak. Also, it leads me to actually prove my greedy solution again and find fault in it. I have updated the editorial with the caution in my solution.

1 Like

@artharva_sarage, for applying binary search you should prove that the function on which it is being applied is monotonic, i.e. it is true for some range and then false always OR it is false for some range and then true always. This clearly doesn’t hold. The test data was weak and hence was not able to catch the error in your code for small subtasks as well.