Can anyone plz take a lokk at my solution, i am getting WA in just one testcase. https://www.codechef.com/viewsolution/8520392
@atulshanbhag could you please tell me the reason for use long long everywhere in fkhan_iitbhu solution.
Where his solution is getting an overflow.
@fkhan_iitbhu
As stated above please change int to long long int since large values of int cause overflow and then try again. 
explain plz
This was my First DP problem. Thanks to Problem Setter, this was really an amazing problem!
First find the frequency of upper hemisphere and lower hemisphere in two separate arrays.
Multiply each array index correspondingly and make copy of this array as in code.
Take cumulative sum from end of array and multiply this array by one shifting with copy array in the same mul array.
- Sum of c-1 elements of mul array is D+1 answer where D=1.
Then again take the cumulative of mul array and multiply this with copy
array with 2 shifting.
- Sum of c-2 elements of mul array is D+1 answer where D=2.
Repeat this process by increasing shifts c-1 times.
-> now you can understand code.
1 Like
I tried quite a few different approaches for this problem but the first one I used is this.
https://www.codechef.com/viewsolution/8373392
I basically used the previous values to ith sequence to get the values of the (i+1)th sequence but yet couldnāt find why I was getting WA in particular cases.
Could someone please help me out?
Just add modulo everywhere because there can be overflow.
AC code - https://www.codechef.com/viewsolution/8537624
Nice problem , it made me to think for a sol of polynomial multiplication ā¦
which would not be possible , if i had studied DP earlier
This problem can be solved by multiplying two polynomial iteratively.
by taking 1 polynomial as (1 + a[i]x ) and other as product obtained earlier ā¦
Hereās link to my codeā¦ https://www.codechef.com/viewsolution/8434494
hi dragonemperor, i have been following your posts on codechef long contest ques, itās been a great learning curve, i learned trie with the help of your amazing insights on REBXOR form sep15,
i googled for polynomial function method but only managed to find FFT, can you please share the resource that led you to succesfully implement your code,
thanks ā¦
@rb08
Actually I also found only FFT and I didnāt understand it. I am still trying to understand that.
For the above problem, I only needed to multiply n linear polynomials that made it a bit easy (I donāt know if I could do for higher power).
Hereās my approach.
Consider the polynomial (x-1)*(x-2)
It is equal to x^2-3x+2
For any multiplication we only need the co-efficient of the polynomial (letās store only the co-efficient in array say coeff). Also, when we are multiplying the first polynomial with x, since itās co-efficient is 1, the coefficients of the result doesnāt change. Only power of each term increases by 1.
Letās write x-1 as 0x^2 + 1x - 1. When we are multiplying it with x, the result becomes
1x^2 - 1x +0. The power increases and co-efficient remains same.
When the constant factor is multiplied, the co-efficient change, not the power of each term.
(x-1)(-2) = -2x + 2 (power of each term is constant). Now after multiplication of each part, we need to add the result.
The coeff array before multiplication is {0,1,-1} //0 for x^2
After multiplying x, since the power increases, we can simply shift them to the left as
{1,-1,0} and then add the result of the second multiplication with the constant. This result has power less than the first multiplication result. So we start adding the terms starting from the second term (check below to understand).
Co-efficient after multiplication with x, {1,-1,0}
Co-efficient after multiplication with -2, {0,-2,+2}
Ignoring the first term which is always 0 for second result, and un-altered for first result, we add the remaining corresponding terms. So result is {+1,-3,+2}.
This is the basic approach. Hope you understood.
In my code, I didnāt use multiple arrays for multiplication. I used a single long array initialized to 0. The first element of the array is the co-efficient for the highest power term. (whatever the highest term is after each multiplication). I used a pointer
idx to indicate the last position of the result (co-efficient of power 0, i.e. the constant term). For each multiplication, after multiplying with x, simply increased idx by 1. The new added term is always 0 as initialized. While multiplying the constant part, we need to add the result to corresponding terms. Remember, even though we shifted the co-efficient to the left, their value didnāt change. We can re-use them for the multiplication again. See below
idx is pointing to last element. So the element before it is equal to the co-efficient of power 0 before multiplying the x. We need to multiply the constant term -2 to this co-efficient and add it to the term at idx (see it using pen and paper for better understanding). I did the following to accomplish this
coeff[idx]+=(coeff[idx-1]*constant_term)
Putting it in a loop, we get
for(int i=idx;i>0;iā) //i!=0 as 0th term is the highest power and itās co-efficient never changes
coeff[i]+=(coeff[i-1]*constant_term)
I used modular arithmetic on this.
1 Like
A little experiment using pen and paper showed that if first term is present x time, second y times and so on, (ignoring the terms present 0 times), the problem can be reduced to finding product of elements of of subset of side c+1 (and for all other values of c, same thing applies), in the array {x,y,ā¦}
Following this link I got the approach
I explained my approach in the code as a separate answer as this didnāt fit comment. Check that out too.
1 Like
thanks alot for a detailed explanation @dragonemperor, though i still need some time to grasp polynomial multiplication better.
awsome work ā¦
I am getting 15 points and WA in some of the subtasks ,please can somebody take a look at my solution and tell me what is the problem here https://www.codechef.com/viewsolution/8370715 .It would be a great help,as this is the first time I got some points in a DP question
Hi,
Can someone please tell me why my code is failing only in the second last test-case?
https://www.codechef.com/viewsolution/8549224
Thanks
I didnāt understand why F[0][0] is taken ā1ā and not ā0ā in the editorial. Also what will be the base case for W[][]? Is F[0][0]=1(if it is correct) enough to solve the problem ?
Thank you so much. Now I finally understand why I was getting a WA.