BRKSTRNG - Breaking String

no tags 

A certain string-processing language allows the programmer to break a string into two pieces. Since this involves copying the old string, it costs n units of time to break a string of n characters into two pieces. Suppose a programmer wants to break a string into many pieces. The order in which the breaks are made can affect the total amount of time used. For example, suppose we wish to break a 20 character string after characters 3, 8, and 10 (numbering the characters in ascending order from the left-hand end, starting from 1). If the breaks are made in left-to-right order, then the first break cost 20 units of time, the second break costs 17 units of time, and the third breaks costs 12 units of time, a total of 49 units of time (see the sample below). If the breaks are made in right-to-left order, then the first break costs 20 units of time, the second break costs 10 units of time, and the third break costs 8 units of time, a total of 38 units of time.

The cost of making the breaks in left-to-right order:

thisisastringofchars     (original)
thi sisastringofchars    (cost:20 units)
thi sisas tringofchars   (cost:17 units)
thi sisas tr ingofchars  (cost:12 units)
                         Total: 49 units.

The cost of making the breaks in right-to-left order:

thisisastringofchars     (original)
thisisastr ingofchars    (cost:20 units)
thisisas tr ingofchars   (cost:10 units)
thi sisas tr ingofchars  (cost: 8 units)
                         Total: 38 units.

Input:

There are several test cases! In each test case, the first line contains 2 integers N (2<=N<=10000000) and M (1<=M<=1000, M<N). N is the original length of the string, and M is the number of the breaks. The following lines contain M integers Mi (1<=Mi<N) in ascending order that represent the breaking positions from the string's left-hand end. Read input till EOF.

(There wont be more than 100 cases)

Output:

For each test case, output in one line the least cost to make all the breakings.

Sample Input:

20 3
3 8 10
20 4
2 3 8 10

Sample Output:

37
40



hide comments
kagami_taiga7: 2016-01-19 12:14:51

@mohit hahaha chutiya

mohit: 2016-01-19 12:11:17

nice question :)

Last edit: 2016-01-19 14:31:24
B S Sachin Govind: 2014-12-10 09:04:41

can u please explain how it is 37 ans of first case whil above it is explained as 38

Last edit: 2014-12-10 09:12:03
B S Sachin Govind: 2014-12-09 22:29:48

how to read till eof

--ans(Francky)--> http://lmgtfy.com/?q=c%2B%2B+eof

Last edit: 2014-12-10 00:51:55
Shafaet: 2013-11-26 13:16:49

@Shaka Shadows: Authors of faster solutions user priority queue, i am not sure how those solutions work, my solution is O(M^2).

Shaka Shadows: 2013-08-30 14:30:12

@Shafaet: Is it possible to solve this with a complexity better than O(M ^ 2)? My ACed solution has that complexity, but the running time is way worse than the other AC so far.

J.A.R.V.I.S.: 2013-08-29 14:31:35

clrs problem


Added by:Shafaet
Date:2013-08-28
Time limit:1s-2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Author: Wei, Qizheng, Source: ZOJ Monthly, June 2007