CHEFARK - Editorial

PROBLEM LINK:

Contest
Practice

Author: Dymtro Berezein
Testers: Istvan Nagy
Editorialist: Praveen Dhinwa

DIFFICULTY:

Easy

PREREQUISITES:

basic combinatorics, even-odd parity understanding

PROBLEM:

You have an array A of n integers. You can choose some element in the array and multiply it by -1. You have to do this operation total K times. Find the number of different arrays you can end up with.

QUICK EXPLANATION:

The basic idea of the problem is to choose some elements in the array and multiply by -1’s. Remaining operations can be done on a single element by making sure that its parity is not changed. If there exists a zero element in the array, the remaining operations can always be done on that element. In this case, the condition of making sure parity is unchanged is implicitly satisfied.

EXPLANATION:

Notice that the elements of the final array will be either same, or multiplied by -1. This means, that we can replace each number in the array with 0 (if the element is zero), 1 (if the element is positive), -1 (if it is negative).

The basic idea of the problem is to choose some elements in the array and multiply by -1’s. Remaining operations can be done on a single element by making sure that its parity is not changed. If there exists a zero element in the array, the remaining operations can always be done on that element. In this case, the condition of making sure parity is unchanged is implicitly satisfied.

So, we will check whether we can change only some x non-zero elements. If there exists a zero element in the array, then it can always be done. Otherwise, if K - x is even, then also it can be done by applying the operation on same element multiple times. Number of ways of choosing x elements out n elements is denoted by C(n, k) which can be found by precomputing factorials and finding inverse modulo a number.

Time Complexity:

\mathcal{O}(n) or \mathcal{O}(n \, log n) if you are finding inverse modulo in each call of C(n, k)

AUTHOR’S AND TESTER’S SOLUTIONS:

Tester

3 Likes

@admin Can you point out reason for tle in this solution with possible modifications

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

Thanks in advance

I think it is due to calling combination function for each iteration in which you compute factorial upto n again again instead of storing it. If you store factorial upto 100000 in an array in main() before while(t–) and use it for each call to combination function then it would certainly passed.

1 Like

What was wrong in my solution? Please can u help? https://www.codechef.com/viewsolution/10508844

@ohmankur, your code is probably TLEing cause you are calculating the vector “f”, for maintaining factorials, each time you are calling your “C” function to given nCr. You can instead, precompute factorials upto 10^5 and store them in “f” for once, instead repeatedly calculating them.

Have a look at my code to understand more clearly and see where I have calculated array “f”.

Solution

@easy_ It might be possible that when you calculate nChoosek it might get big enough than what unsigned long long int can store, though not sure, and may when you do this in loops ans+=nCr(i) -> I think here also there are chances that it might be overflowing.
Maybe make some changes there and it might work!

@lohit_97 Can you tell me what will be the better way to store such big numbers, or if there is any other better way of calculating nCk?

Hi! Could anybody please suggest a test case where my solution fails? I calculated n choose k correctly(I think so).

Link to my solution

Thanks in advance.

@easy_ Please have a look at my solution or you can visit this blog.

@devilhector your code fails on the cases when there is 0 present in the array
for eg. n=5,k=5,array=[1,2,3,0,0]
check this actual answer will be 8,but your code outputs 4.

1 Like

Please anybody help where my code goes wrong
https://www.codechef.com/viewsolution/10498938

For calculating nCr in different situations, you can refer to the following link:

https://github.com/likecs/Competitive-Coding/blob/master/C%2B%2B/Maths/combinations.cpp

@easy_ so basically we are adding nC0,nC2,nC4…if k is even
else we are adding nC1,nC3,nC5 (k odd)

is that right??

can anyone tell me why code fails for higher numbers…it is giving correct answer but dont no why i am getting only 40 marks.
pleas tell me.
https://www.codechef.com/viewsolution/10347950

sorry i pasted the solution of 4th question.

sorry i pasted the solution of 4th question.

Hi!! Can you please tell me the error in my code??

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

@lohit_97

I did this before but i was facing tle in one of the test case

link is:
https://www.codechef.com/viewsolution/10513481

Can somebody point out the error in my solution. It only passed the first sub-task.

@anshika_1

There exist overflow problem for higher values.Change your data type.Use the concept of mod 10^7 for computing higher values.