Poker Chips - Editorial

general
, ,
1

PROBLEM LINK:

Practice

Contest

Author: Rishav Pati

Tester: Rajat De

Editorialist: Sidhant Bansal

Difficulty : Cakewalk - Easy

Expected Complexity: O(A_MAX * N * N)

Editorial -

The array should be an arithmetic progression with common difference 1, ie. more formally A[i] - A[i - 1] = 1, for all i from 2 to N
As N <= 50 and A[i] <= 50 we can do a naive brute force.

We can assume the first element to be from the values 0 to S where S is the sum of all the elements of array A[].

  1. For each starting element we build the entire AP of the array in O(N), let this array be B[] and check weather the sum of all these elements is equal to S.
  2. If Yes, then we can calculate the minm no. of steps to do this by maintaining a variable RESULT, initialize RESULT to 0.
  3. Wherever we find that B[i] > A[i], add (B[i] - A[i]) to RESULT.
Note - The above statement ensures that we only move coins if necessary and the case B[i] < A[i] is covered in this only. We take the minimum over all the RESULT's and that is our answer.

Pseudocode -


ANSWER = INT_MAX
FOR i = 0 to S (where S is the sum of array A[])
	 B[ 1 ] = i
	SUM = B [ 1 ]
	FOR j = 2 to N
		B[j] = B[j - 1] + 1
		SUM = SUM + B[j]
	IF SUM = S
		RESULT = 0
		FOR j = 1 to N
			IF B[j] > A[j]
				RESULT = RESULT + (B[j] - A[j])
		ANSWER = MIN(ANSWER, RESULT)
IF ANSWER = INT_MAX 
	PRINT -1
ELSE
    PRINT ANSWER

Complexity analysis - O(A_MAX * N * N), as S = A_MAX * N in the worst case and the checking of array B[] is O(N).

2

In the first for loop, SUM should be assigned to i(or B1) instead of 0.

1 Like
3

Fixed. Thanks :slight_smile:

4

it can be done in O(n) in worst case;
create array b[] directly by knowing the first element of b[] in O(1)
by this formula
long first_element=(2sum-n***n+n)/(2n)**; where sum is sum of input array a[]
then generate other elemnt of array b[] by adding 1 to previous value;
if(sum of array b is equal to sum of array a[] then answer exist) else print -1
answer can be calculated as above describe in editorial
FOR j = 1 to N
IF B[j] > A[j]
RESULT = RESULT + (B[j] - A[j])
print result

https://www.codechef.com/viewsolution/8851410