How to solve KBIGNUM which is removed from feb 17

Hello, as you might know the problem KBIGNUM has been removed from the feb17 contest as it was found somewhere else. Can someone tell me how did we have to solve the problem and where was it found online.

1 Like

Here is link which gives you sense that why it has been removed from the contest…

You can found Editorial also…

1 Like

Even the test cases were same! I think the author submitted same question to both the sites.

2 Likes

I didn’t know if it was available online. But I had seen this trick before in some IIT kanpur contest (IOPC). There is even an detailed editorial on the same here

2 Likes

I devoted around 11 hours to solve CHEFBEST and about 5 hours to solve KBIGNUM.
I request codechef to cancel the current ongoing contest and restart it with all new problems.

2 Likes

It’s a nice question, but what were different approaches for the subtasks? I can’t see a solution that would pass the first subtask and wouldn’t pass the others. I think first subtask should have been easier - lower N constraint.

1 Like

Check the ‘Alternative method’ section in the link @likecs linked.(press)

Lets say you have a odd ‘m’.(‘m’ refers to the power of the last term in a GP with ratio ‘x’). Take for eg 1+x+x^2+x^3+x^4+x^5+x^6+x^7. This can also be written as:
(1+x)(1+x^2+x^4+x^6) . Look at the right part. Instead of (1+x^2+x^4+x^6), you can write it as (1+(x*x)+(x*x)^2 +(x*x)^3 ). We basically reduced it to a GP again with half the number of terms and double the value of ‘x’. So we can keep doing this through recursion.

If instead m is even, for eg in 1+x+x^2+x^3+x^4+x^5+x^6, you can write it as (1+x)(1+x^2+x^4) + x^6. Only difference is that we have to add the last term into the result.

Since we are halfing the number of terms in each step, the recursion will take O(log m) time.
You can refer to my solution to the problem here. Take note that ‘n’ is the equivalent to m.(I used m variable for modulo)

1 Like

The problem is reducible to calculating sum of a GP modulo m. Let’s say a have k digits.
Then aaa… n times = a*(1 + 10^k + 10^(2k) + … 10^((n-1)k)). Let m1 = a%m and t = (10^k)%m.
Now the answer will be, (m1*m2)%m, where,
m2 = (1+t+t^2+t^3…+t^(n-1))%m. Which can be easily calculated using recursion just like modular exponentiation due to similar properties.

Code:- https://paste.ubuntu.com/23942973/ (Python)

1 Like

omg found the same question in another coding website

O…M…G!!

Off topic, but dude…are u google? XD

btw how do u know that the test cases were same?

1 Like

mathecodician has a really valid Q. I was wondering that myself!

I have already shared this link. See at the top of comment/