Help for problem PPNUM

kuruma · October 21, 2013, 12:30am

Hello @all,

I haven’t had any time to actually “attend” the cook-off, as I was busy with other things in the meantime… However, I still thought about this problem a bit, as I have read alike statements many times…

My idea was to devise some counting function such that the answer could be obtained in the fashion F®-F(L-1) where L and R stand for the left and right limits of the interval.

I also realized the “pattern” such that:

Sum(1,X) = 1*sum of i for i in (1, 9) + 2*sum of i for i in (10, 99)+ ... + length(X)*sum of i for i in (10^(length(X)), X)

but I couldn’t make any use of it besides this deduction…

I also thought about pre-computing all the values for the sums of numbers with same length and then just play with the offsets… Here’s my Python solution:

def summa(a,b):
	if a > b:
		return 0;
	else:
		return (a+b)*(a-b-1)/(-2)
	
L = [i*summa(pow(10,i-1),pow(10,i)-1) for i in range(1,10)]

i = int(raw_input())
while i > 0:
	l,u = [int(x) for x in raw_input().split()]
	x = len(str(l))
	y = len(str(u))
	answerl = 0
	answeru = 0;
	for j in range(x-1):
		answerl += L[j]
	answerl += (x*summa(pow(10,x-1),l))
	for jj in range(y-1):
		answeru += L[jj]
	answeru += (y*summa(pow(10,y-1),u))
	if len(str(l)) < len(str(u)):
		print (answeru-answerl+l)%1000000007
	else:
		print (answeru-answerl+2*l)%1000000007
	i-=1

which obviously gets WA veredict…

I tried to read some solutions (@mugurelionut , @alex_2oo8…) and they all use this same counting function approach…

I would like to know the logic they used in order to devise their correct counting scheme, as the rest is only implementation details…

Any tips will be great!!

Best regards,

Bruno

tijoforyou · October 21, 2013, 2:24am

Hi,

I can explain the idea I used in my program.

Sum of first N natural numbers, S_N = N*(N+1)/2

So, sum of numbers between X and Y, S_X,Y = S_Y - S_X-1 = Y*(Y+1)/2 - (X-1)*X/2

Now, we are given l and r.
If numdigits(l) == numdigits®, then answer is S_l,r

Otherwise, ans=0, and let numdigits(l) be x and numdigits® be y. So, we have x < y.

Now, we add S_{l,9_x} to ans, where 9_x is the number 9999… (9 repeats x times).

Similarly, we add S_10^y-1,r to ans.

Now, it remains to add all the numbers of lengths x+1, x+2, …, y-1

Sum of All numbers of length k, k in {x+1, x+2, …, y-1} is S_{10^k-1,10^k-1}

Add all these to ans, to get the final answer. Of course, at each step, at each step, we must multiply the partial sum with the corresponding length of digits.

Since the answer is to be given modulo 1,000,000,007 do the modulo operation as well, as necessary.

kcahdog · October 21, 2013, 2:31am

@kuruma I used the same logic you stated. Here is how i found out how to pre-compute:

Compute the sum from 1 to r assuming all have the length r i.e. len® * (r*(r+1))/2.

2)Now because you have assumed all have length r, you have taken some extra numbers in the answer which have to be removed. If you try to find them, you will find it is equal to sum(1-9) + sum(1-99) + sum(1-99) … sum(1-10^len®-1). You need to substract this from 1 to get value of goodness from 1-r.

3)To get this , you first observe the expression in 1.You can see numbers with length 1 less than r will be counted extra once, number with length 2 less will be counted twice and so on. If you simplify the exp. in 2 above, you will see sum(1-9) will occur in all of the sums (sum(1-9),sum(1-99)…) exactly len®-1 times, similarly sum(10-99) will occur len®-2 times and so on.

You can try to see this for small numbers like 10002,103,etc. Here is a link to my solution. Its not very clean but hopefully understandable.

P.S. By sum(1-9) , i mean sum of all numbers from 1-9. 1+2+…9. Just to make it a bit more clear.

kuruma · October 21, 2013, 2:42am

Hey @kcahdog,

It’s both frustrating and amazing how you have used almost the same idea I had, with that awesome insight which allowed you to pre-compute everything…

I couldn’t “see” that sort of pattern when summing from 1 to N, although I understood, at some point, that I was counting extra numbers… (In fact, you can see the if there in the end, which accounts for this extra counting, but, unfortunately, only for the case of length 2… My brain didnt let me go any further…)

Thanks for this answer though! I’m cleared out now

Sigh Still need lots of training

mugurelionut · October 21, 2013, 1:46pm

A very easy way to compute F(X) (the answer for the interval 1…X) is as follows. First find the number of digits of X - say this number is D. For each number of digits P from 1 to D-1 we will add the sum of all the P-digit numbers, multiplied by P. The smallest number with P digits is 10^(P-1) and the largest number with P digits is 10^P - 1. The sum between two numbers U and V (inclusive) is V * (V+1)/2 - (U-1) * U/2 (i.e. the sum of 1+2+…+V minus the sum of 1+2+…+U-1).

After this we need to add the sum of the numbers from the smallest number with D digits to X, multiplied by D. The smallest number with D digits is 10^(D-1).

Then, just as you said, the answer for a query is F®-F(L-1). This approach requires no precomputation (it might help you to precompute the smallest and largest number for each possible number of digits, but you can also do this on the fly).

kuruma · October 21, 2013, 3:33pm

Hello @mugurelionut,

Thank you for your answer I knew that I had to devise such scheme which would allow me to give the answer to the problem in the form F®-F(L-1), but, as usual, I had some troubles in the implementation and eventually got lost in the middle of some details

I will try to implement this idea you’ve described and will post here again, in case I find some trouble along the way… (Which is, unfortunately, likely)

Thanks,

Bruno

thespacedude · October 21, 2013, 6:13pm

This has been immense help. I finally solved the problem. I hope I will be able to tackle these type of problems in the future by myself. Thanks a TON!

kuruma · October 21, 2013, 9:40pm

Hello @all and in particular @mugurelionut:

I have decided to try and implement your idea

Here’s what I have got so far:

int ndigs(int number)
{
	int nd = 0;
	while(number > 0)
	{
		nd++;
		number /= 10;
	}
	return nd;
}

long long int sum(long int a, long int b)
{
	return (b*(b+1))/2 - ((a-1)*a/2);
}

unsigned long long int f(int X)
{
	unsigned long long int answer = 0ULL;
	int D = ndigs(X);
	for(int p = 1; p < D; p++)
	{
		answer += (sum(pow(10,p-1), pow(10,p)-1)*p)%1000000007;
	}
	answer += (sum(pow(10,D-1),X)*D)%1000000007;
	return answer%1000000007;
}

Is the above code good, bad or horrible?

Because I’m still getting WA at it…

Best,

Bruno

hatim009 · October 21, 2013, 10:48pm

since 1<=l<=r<=10^9 check for the type…of X,number it should be long…and check for negative modulo also…

kuruma · October 22, 2013, 2:50am

I’ve fixed the data types so all should work fine with that… Also, to check for negative modulo isnt it enough to sum MOD to answer and then take it modulo MOD again?

mugurelionut · October 22, 2013, 4:20am

@kuruma: I see two possible errors. 1) the arguments a and b of your sum function should also be of long long type (at the moment you get overflow when computing b*(b+1) or (a-1)*a ; 2) in the sum function add “% MOD” (i.e. compute the sum modulo MOD) - otherwise you get overflow when multiplying by p in the f function.

kuruma · October 22, 2013, 4:49am

@mugurelionut, You were (obviously) right!! I have finally got AC answer
Thank you very, very much!!!

I hope I can save what I’ve learned for future problems!!

hatim009 · October 22, 2013, 8:06am

@kuruma will you please explain me how u solved this question…how u made the recurrence ralation…Thankyou.problem link http://www.codechef.com/BTCD2013/problems/PRSN

kuruma · October 22, 2013, 12:45pm

Hello,

That question is a “famous” programming question, as it had appeared on Google Code Jam before (which is why you see most top solutions being .txt files).

I used the explanation Google gave:

This problem is solved by dynamic programming. For each pair of cells a ≤ b, we want to compute dp[a][b], the best answer if we only have prisoners in cells from a to b, inclusive. Once we decide the location of c, the first prisoner between a and b to be released, we face the smaller sub-problems dp[a][c-1] and dp[c+1][b]. The final answer we want is dp[1][P].

It is clear we only need to solve those dp[a][b]'s where both a and b are either 1, P, or adjacent to a prisoner to be released. Thus the number of sub-problems we need to solve is just O(Q^2).

Taking this explanation into account the problem is very straightforward…

And well, it’s just a shame that some authors only copy problems+testcases, but, external contests aren’t to be taken “by heart”, I guess

Best,

Bruno

hatim009 · October 22, 2013, 7:20pm

Thanks Bruno…

kuruma · October 22, 2013, 7:47pm

You’re welcome @hatim009!

Actually, on almost all external contests it’s common to find such kind of problems… Which is somewhat bad, imho

hatim009 · October 23, 2013, 7:00pm

can you give me the link where the explanation is…

kuruma · October 23, 2013, 7:13pm

Here it is:

https://code.google.com/codejam/contest/189252/dashboard#s=a&a=2

hatim009 · October 23, 2013, 7:15pm

Thanks…

kuruma · October 23, 2013, 7:30pm

You are welcome sir