All Tracks Algorithms Graphs Maximum flow Problem

Tax Evasion



There are a group of n companies who are fed up with a new set of ‘transaction taxes’ - that state that if a large transaction between two companies falls in such-and-such bracket, there is a so-and-so per-cent tax levied on that, which comes at the expense of both the companies. Naturally they conspire to look for loopholes in the system, for which they consult you.
Over the past few days the companies had made several purchases among themselves, and thus owe each other certain amounts of money (say ‘imbalance’.) In light of these new taxes, they have decided to unite and help each other. They don’t care from which companies their money is coming from, as long as that they get / pay their share of imbalance.
E.g : If three companies A, B, and C have imbalances +20M$,-15M$ and -5M$ respectively, A could pay off B and C directly via a 15M$ and a 5M$ transaction, or A could pay B and C 10M$ each and then C would pay 5M$ to B via a third transaction, resulting in all transactions being <= 10M$.
That’s exactly why you’re being consulted : find the minimum amount x such that all imbalances can be satisfied by transactions involving <= x amount of money (thereby evading taxes as much as possible.) Note that some companies can have 0 imbalance, but will still help other companies for “future favours.” Also note that the government has imposed restrictions such that there can be only one transaction between any two companies, and in only one direction (i.e A gives some amount to B or B gives some amount to A, but not both. Also A cannot pay B twice.) Furthermore, all transactions must in integral multiples of the unit currency.

Input format and Constraints :

Input consists of a single test case. First line contains integer n, with 3 <= n <= 100. Second line contains a space-separated array a_i of n integers - the imbalances, with abs(a_i) <= 10^6, and sum(a_i) = 0.

Output format :

Single line with an integer that is the minimum value possible : x.

20 -15 -5
Time Limit: 2.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: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic


Initializing Code Editor...
Your Rating:


This Problem was Asked in

IIT Kharagpur

Challenge Name

CodeNite 2.0

View All Notifications