To load or not to load
All submissions for this problem are available.
Due to rapid expansion, Grofers wants to build a large distributed storage system on the web. Millions of users will store terabytes of data on its servers.
One way to design such a large system would be to hash each user’s login id, partition the hash ranges into equal sized buckets, and store the data for each bucket of users on a single server For this scheme, mapping a user to a server is a simple hash computation. However, if a small number of users occupy a large fraction of the storage space, hashing will not achieve a balanced partition. One way to solve this problem is to make the hash buckets have non uniform width based on the load in that hash range.
You have n users and m servers.
- User i requires B(i) units of storage space. You design a strategy which finds numbers K(1) through K(m) such that all users between K(j) and K(j+1) get assigned to server j.
- Your strategy minimizes the load on the most heavily loaded server. Given the array B, number of servers m and number of users n,
- your program should output the Load on the most heavily loaded server.
The first line of input is two integer value , the total number of User N, total number of Server M and the second line has space separated integers which are the user storage requirements .
Output single lines, the load on the most heavily loaded server
- 1 ≤ N ≤ 100000
- 1 ≤ M ≤ 100000
Input: 5 2 2 3 1 5 1 Output: 6
[2 3 1 5 1] so starting three user will be served by first system and last three user will be served by last server.
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.