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:- Ubuntu Pastebin (Python)
1 Like
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/