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

your nChoosek function is overflowing

@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!

Precompute the values of factorials % MOD and use them,dont repeatedly calculate them as u are doing here…

@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.

@easy_ you can store factorials up to n using for loop and taking mod 1000000007 in each step. To divide by k! and (n - k)!, use modulo-inverse. Modulo-inverse can be calculated by fast binary exponentiation, used to calculate k ^ (MOD - 2).

long long fastpower(long long base, long long index) {
long long res = 1;
while(index) {
    if(index & 1) res = (res * base) % MOD;
    base = (base * base) % MOD;
    index >>= 1;
}
return res % MOD;

}

To calculate modulo-inverse just pass k as base and (MOD - 2) as index. Remember, this works only if base and MOD are co-prime. This is proved by Fermat’s Little Theorem.

@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

@amit_369 Just a couple of suggestions:

  1. change data-type int to long long. There might be overflow problem.
  2. instead of dividing, using modulo-inverse of that number

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.

//