Sum of GP
Pages: 12
Prakhar has very good knowledge about current affairs.He used to play live games like LOCO,Brainbaazi,etc.
There are N questions and K options for each question, rule of quiz is that if you attempt any wrong answer you will be eliminated from the quiz .Now, Prakhar wants to win the game anyhow ,he has infinite number of players who can play for him.But, he will appoint minimum players to win the game.
Now, your task is to determine the sum of total number of players who has attempted ith question for all (1<=i<=N). As the answer can be very large, print (sum of total number of players)% 10^9+7.
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains two space-separated integers N and K, denoting the number of questions and choices available for each question respectively.
For each test case, print the result in new line.
Sample Input:
1
3 3
Output:
39
Explanation:
1st question is attempted by 27 players,second by 9 and third by 3 players.So, the sum of total number of players is(27+9+3)=39. The answer will be 39%(10^9+7) = 39.
1 <= T <= 100000
1 <= N <= 1000000000
1 <= K <= 1000000000
The question seems too trivial to me that it is sum of GP from k to k^n , but it is giving Wrong Answer.I cant understand the reason , I even coded in Python but the same result ,Can someone please help.
There are N questions and K options for each question, rule of quiz is that if you attempt any wrong answer you will be eliminated from the quiz .Now, Prakhar wants to win the game anyhow ,he has infinite number of players who can play for him.But, he will appoint minimum players to win the game.
Now, your task is to determine the sum of total number of players who has attempted ith question for all (1<=i<=N). As the answer can be very large, print (sum of total number of players)% 10^9+7.
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains two space-separated integers N and K, denoting the number of questions and choices available for each question respectively.
For each test case, print the result in new line.
Sample Input:
1
3 3
Output:
39
Explanation:
1st question is attempted by 27 players,second by 9 and third by 3 players.So, the sum of total number of players is(27+9+3)=39. The answer will be 39%(10^9+7) = 39.
1 <= T <= 100000
1 <= N <= 1000000000
1 <= K <= 1000000000
The question seems too trivial to me that it is sum of GP from k to k^n , but it is giving Wrong Answer.I cant understand the reason , I even coded in Python but the same result ,Can someone please help.
Last edited on
@Repeater, On sites like codechef, WA means "Wrong Answer", TLE means "Time Limit Expired".
But is his description of the problem enough? He should link to the problem page, too.
And is GP supposed to mean "Geometric Progression"?
But is his description of the problem enough? He should link to the problem page, too.
And is GP supposed to mean "Geometric Progression"?
Last edited on
No idea why someone reported tpb's post. Seems pretty reasonable. Certainly wasn't me!
| Seems pretty reasonable. |
More reasonable than usual, that's for sure. Some kind of misunderstanding, perhaps?
@deathsstroke, I don't really understand the question. Can you post a link to it? You should also post your code.
@deathsstroke If you are handling large numbers properly and still facing WA , you are missing a very simple boundary case, think with some small examples, you'll figure it out.
Last edited on
| But I want to confirm that the answer should be sum of GP from k to k power n ? |
| 1 <= T <= 100000 |
In this example, there are three (N=3) questions, with four (K=4) possible answers per question. You need 4*4*4 players in order to get one success.
First question:
64 players attempt this question, 16 (number of players in this round / number of possible answers = 64 / 4 = 16) make it through to the next round.
Second question:
16 players attempt this question, 4 make it through to the next round.
Third question:
4 players attempt this question, 1 wins the game.
You are asked to determine how many players attempt question i;
| your task is to determine the sum of total number of players who has attempted ith question |
How many players attempt question 1 (i=1) ? 64
How many players attempt question 2 (i=2)? 16
How many players attempt question 3 (i=3)? 4
As you can see, the answer is NOT the sum of GP from k to k power n.
But what is T? Is T the number of games? Is each game different?
Last edited on
So the answer is 64+16+4 which is k power 3 + k power 2 + k
This is what I am saying
This is what I am saying
| So the answer is 64+16+4 which is k power 3 + k power 2 + k |
| number of players who has attempted ith question |
How many players attempted question 3? Four. Four players attempted question 3.
But you're saying 64+16+4 = 84 players attempted question three. That's more than the number of player in the game! How can 84 people have attempted question 3, when there were only 64 people playing the game at the start?
What is T? You haven't told us the whole question. What is T?
Last edited on
your task is to determine the sum of total number of players who has attempted ith question for all (1<=i<=N).So the answer is the number of players attempting 1st question + number of players attempting 2nd question + ... +number of players attempting nth question .
T are number of different test cases
T are number of different test cases
| So the answer is the number of players attempting 1st question + number of players attempting 2nd question + ... +number of players attempting nth question |
I believe that is incorrect.
I think you are to sum the number of people attempting test i, over all the tests.
When i = 6:
number of people attempting question six on test 1 +
number of people attempting question six on test 2 +
number of people attempting question six on test 3 +
number of people attempting question six on test 4 +
number of people attempting question six on test 5 +
...
number of people attempting question six on test T
The question is very unclear. If there is only one game being played, then
| the sum of total number of players who has attempted ith question |
Last edited on
I have edited the question with sample input and output ,I hope that it will become clear now
Fair enough. This does seem far more simple than I thought.
The sum you need is the sum, for round=1 to round=i, of
k^(N + 1 - round)
So if k=3, n=3, how many get as far as the first round?
3^(3+1-1) = 3^3 = 27
If k=3, n=3, how many get as far as the second round?
27 + 3^(3+1-2 ) = 27 + 3^2 = 27 + 9 = 36
If k=4, n=3, how many get as far as the first round?
4^(3 + 1 - 1) = 4^3 = 64
If k=4, n=3, how many get as far as the second round?
64 + 4^ ( 3 + 1 - 2) = 64 + 4^2 = 80
As you can see, the sequence is NOT just: k^1 + k^2 + k^3 + ... + k^n
The sequence is: k^n + k^(n-1) + k^(n-2) + ... + k^(n+1-i)
The sum you need is the sum, for round=1 to round=i, of
k^(N + 1 - round)
So if k=3, n=3, how many get as far as the first round?
3^(3+1-1) = 3^3 = 27
If k=3, n=3, how many get as far as the second round?
27 + 3^(3+1-2 ) = 27 + 3^2 = 27 + 9 = 36
If k=4, n=3, how many get as far as the first round?
4^(3 + 1 - 1) = 4^3 = 64
If k=4, n=3, how many get as far as the second round?
64 + 4^ ( 3 + 1 - 2) = 64 + 4^2 = 80
As you can see, the sequence is NOT just: k^1 + k^2 + k^3 + ... + k^n
The sequence is: k^n + k^(n-1) + k^(n-2) + ... + k^(n+1-i)
But i should be from i to n , substituting i=n in k^(n+1-i) gives k , so it is equivalent to what I was saying
@deathsstroke yes, it is sum of GP, but just think of a boundary case, take examples its very simple.
I am taking care of k=1 case and n=1 case , but I cannot find any other corner case
keep sure to check all boundary cases and along with that, make sure you handle large integers properly..
If I was setting the tests, I would have done it so that actually adding the values takes too long. I would make the time limit short enough that the value would have to be calculated directly, rather than by adding the individual terms.
Pages: 12