KOPC12A - K12 - Building Construction

no tags 

Given N buildings of height h1, h2, h3 ... hn, the objective is to make every building has equal height. This can be done by removing bricks from a building or adding some bricks to a building. Removing a brick or adding a brick is done at certain cost which will be given along with the heights of the buildings. Find the minimal cost at which you can make the buildings look beautiful by re-constructing the buildings such that the N buildings satisfy 

h1 = h2 = h3 = ... = hn = k (k can be any number).

For convenience, all buildings are considered to be vertical piles of bricks, which are of same dimensions. 

Input

The first line of input contains an integer T which denotes number of test cases .This will be followed by 3 * T lines, 3 lines per test case. The first line of each test case contains an integer n and the  second line contains n integers which denotes the heights of the buildings [h1, h2, h3 ... hn] and the third line contains n integers [c1, c2, c3 ... cn] which denotes the cost of adding or removing one unit of brick from the corresponding building.

T <= 15; n <= 10000; 0 <= Hi <= 10000; 0 <= Ci <= 10000;

Output

The output must contain T lines each line corresponding to a testcase.

Example

Input:
1
3
1 2 3
10 100 1000

Output:
120

hide comments
lucifer_1729: 2023-01-09 15:38:40

@canhnam357 can you explain your 2 pointer approach

canhnam357: 2022-08-12 02:40:15

done with O(nlogn) ,sort , two_pointer

Last edit: 2022-08-12 02:41:13
khssupriya: 2021-01-17 12:49:38

My first AC in one go T_T

prakharrrr4: 2020-10-14 06:44:29

For proof of unimodality refer this:
https://stackoverflow.com/questions/28415041/how-can-ternary-search-be-applied-for-the-spoj-challenge-kopc12a

tj2972001: 2020-08-12 14:27:57

If anybody gets AC with Ternary search then please look at my solution I am getting WA. Logic seems correct and I am getting right answer with every test case I am thinking. plz help :/ [Link to ideone: <snip>. You can ask me dought regarding my logic (..if any)

Last edit: 2022-07-25 21:02:58
jopdhiwaala: 2020-07-01 07:57:10

Ternary search and binary search both work.

aditya2020: 2020-06-24 11:44:18

@soham_12345 or anyone, could you pls help me solve this. I've got no clue. I've tried binary search btw 0 and max, also I've tried the most trivial solution of taking the max height and calculating the val for all of them, and then taking minimum of all of them

akarsh_raj: 2020-05-22 08:21:24

someone please explain the example.

thanos_tapras: 2020-03-06 23:03:28

Nice problem. Notes:
1. Must use long long in order to get AC (but no need for fast IO)

2. For all those asking for proof that the function is unimodal just think of this:
If you have a variable height starting from a minimum value and then increasing constantly, you can see that in the beginning the cost will be high (since every height will be much higher than the wanted height). As the expected height increases the cost reduces. At some point the function hits a minimum, which serves as the solution to this problem. After that the cost continues to increase since there is no way that a lower cost can be produced as the expected height increases.

limon_88: 2019-10-28 22:47:57

Must use long long int..

Last edit: 2019-10-28 22:48:23

Added by:Radhakrishnan Venkataramani
Date:2012-01-31
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own