All Tracks Algorithms Dynamic Programming Problem

Study- Flyover



The King of PicLand has ordered his disciples to make a flyover (see the figure).

The Disciples being very obedient, they fulfilled the order quickly. The flyover is now opened for General Public use. But the King is very tensed . He ordered his statistician “ Rohan” to measure the effectiveness of the flyover over a course of time . Rohan goes to the place daily and notes down the time taken by his favourite bus to go from A to B ,marks this time as positive and the time taken by the bus on its return journey as negative. As the bus is getting used. The time taken by the bus to cross the flyover increases . After a number of days he opens his copy to see the noted “times” but he is very upset to see that he has noted some invalid values.

You being his Friend, decided to help him . Rohan asks you to do two things .One to tell him the number of possible valid values and the second is to tell him the sum of these valid values.



The first line of input consists an integr , N , the size of the array.

The Second line of input consists of N space separated integers representing the values that Rohan noted down in form of an array A[I].


The Output should contain two space separated integers .

First is the number of possible values and second is the sum of all the possible time . i.e. the sum of all the mod values of these possible values.


$$1 \le N \le 5000.$$

$$1 \le A[i] \le 100000$$. $$A[i] \ne 0$$.

2 -2 -3 -3 4 -5 7 -8
6 29

The required sequence is 2,-3,4,-5,7,-8.

Here the Bus starts its journey from A to B (which is positive) (The bus can start its journey from B to A .. in that case the time would be negative).

The bus takes 2 secs to go from A to B (indicated by a positive sign) .

It then returns back which is indicated by a negative sign . So, it takes 3 secs to go from B to A.(as the time has to increase after every journey . So -2 is not chosen and said to be an invalid entry)

The bus then goes from A to B , takes 4 secs.(positive sign)

Then it takes 5 secs to return from B to A. (negative sign)

And so on.....

The total time taken by the bus for all these journeys =2+3+4+5+7+8=29.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Scala 2.11.8, Swift, Visual Basic


Initializing Code Editor...
Your Rating:


View All Notifications