Summing SlopesProblem code: SUMSLOPE |
All submissions for this problem are available.
A digit in a number N is a minima if it is lesser than both the digits adjacent to it. Similarly, a digit is a maxima if it is greater than both the digits adjacent to it. The slope of N is the number of digits in N (leaving out the first and the last digit) which are either a minima or a maxima. Given A and B, count the sum of the slopes of all numbers between A and B.
Input :
The first line contains the number of test cases T. Each of the next T lines contains two integers A and B.
Output :
Output T lines one for each test case, containing the required sum for the corresponding test case.
Sample Input : 3 101 101 1 100 100 150
Sample Output : 1 0 19
Constraints : 1 <= T <= 50000 1 <= A <= B <= 1000000000000000 (10^15)
| Author: | syco |
| Date Added: | 11-04-2010 |
| Time Limit: | 1 sec |
| Source Limit: | 10000 Bytes |
| Languages: | ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, ERL, F#, FORT, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TEXT, WSPC |
Comments
SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:
Fetching successful submissions
What does source limit
What does source limit indicate?
how many characters can be in
how many characters can be in your code i assume
its the size of ur code in
its the size of ur code in terms of bytes..
ridiculous! my soln kept
ridiculous! my soln kept getting tle... later i submitted in C got ac. But my soln in c++ takes too little time and i think it should be given ac, i mean the time limit should be set to judge the soln order not to see how is the implementation, like if there is fast io or artihmatic optimization.
My code runs & gives desired
My code runs & gives desired output in DEV c++ ,but shows runtime error in the online judge
My code keeps getting TLE
My code keeps getting TLE even though it runs within 0.4 sec on my laptop for random 50000 cases. What maybe the problem. I'm using C++
A question, is the WA
A question, is the WA determined after the program finishes, or is determined during the execution of the program (which could stop the program before is termination)?
The time limit of this
The time limit of this problem is too strict.......
Ya i agree .. the time limit
Ya i agree .. the time limit is too strict .. This what happens every time with me .. I am able to solve them but not within the time limit .. Please could anyone give point out to any site that gives tips to reduce execution time of C programs ..
i am getting "internal error
i am getting "internal error occurred in the system" again and again??
Same to me, I can not submit
Same to me, I can not submit the code.
it is easy to get TLE man.
it is easy to get TLE man.
my ACed solution has not
my ACed solution has not appeared since 1h , damn.
Uh, who isn't getting
Uh, who isn't getting internal server error? I just submitted a simple junk spitting program, so i know it's not us contestants.
I too am gettting internal
I too am gettting internal system error!!!!
Admin or anyone please help......................
I think the internal server
I think the internal server error is just a front end mistake for the TLE, i got email notifications for mine...
Im going nuts trying to figure out what the "Best" answer is to this one. Maybe someone can pm some knowledge when the contest is done?
thnks...............
thnks...............
i have optimized my
i have optimized my program.
It runs in around 0.6 seconds on my computer for t= 50000 and A and B of order 10^15
It is still showing internal system error.............
please help....
I have been trying for last 18 hrs for this program..........
@sushil: Try now, it seems
@sushil: Try now, it seems judge is fixed now.
This is hard on the output.
This is hard on the output. Outputstream printing 50000 lines takes an upwards of 1.5 seconds. Why so ridiculous?
@all Could you please
@all
Could you please share your ideas as to how you solved/optimised the problem/solution ?
The way i attempted this
The way i attempted this question was slightly different than the approach in editorial. For computing a range Slopes(A,B) i computed Slopes_Till(B) - Slopes_Till(A) + Slopes_In(B). Where Slopes_Till is the sum of slopes from 0 to that number(excluding the number itself).
Now , i just had to devise an algorithm for Slopes_Till .. the algorithm was as follows
-> Divide the x digit number into x different ranges as in the following example . If the number is 74356, the ranges would be { (0 - 69999) , (70000 - 73999) , (74000 - 74299) , (74300 - 74349) , (74350 - 74355) }.The result would be such that any range could be written in the following format {Constant Number}{0}{n zeros} - {Constant Number}{N}{n 9's}. The idea of doing this was to allow as many 0-9 digit permutations as possible (the last segment of the range), the slopes of which can be precomputed.
Now for every range , sum of slopes would be the sum of the following 5 kind of slopes
i) From the complete permutation of the last n digits alone.
ii) The slopes where first digit of slope is from the middle segment. ie, slopes from 000,N99*10^(n-2).
iii) The slopes where middle segment digit forms the middle digit of slope. it'll be c00,cN9*10^(n-1)
iv) The slopes where middle segment digit is the last digit of slope. It'll be cd0,cdN*10^n. (c and d are corresponding digits in the first segment of the range)
v) The slopes from the first segment alone. It'll be the slope of that constant number * (N+1)*10^n
As you can see , the above would be a O(1) time algorithms if you precompute the powers of 10 , slopes from 0-1000 and sum of slopes from complete permutation of n digits. (The calculation of perutation slopes requires a dynamic programming algo, which more or less is the same algo as above ... without requiring steps after step ii. You can see that in my program)
While following the above algorithm, you have to be careful about the steps where you might additionally include 010 as your slope when its not applicable. Such slopes should be added if you're computing the slopes from say 1000 - 1999 and not when you're computing it from 0 - 999 (the first range ...).
PS : the O(1) time would be
PS : the O(1) time would be for an individual range , and since we're computing n ranges for an n digit number .. it'll take O(n) time.