## SQRMINSUM - Minimum Sum

no tags

```Suppose you have a list of integers, and a move is defined as taking one of the integers from the list and replacing it with its square root, rounded down to the nearest integer.
Given an integer `l` and an integer `k`, start with the array `[1, 2, 3, ..., l]` and find the minimal sum of the array after `k` moves.
Example
For `l = 5` and `k = 2`, the output should be`squareRoots(l, k) = 10`.
We start with `[1, 2, 3, 4, 5]`.After square rooting `5` to get `[1, 2, 3, 4, 2]` and then square rooting `3` to get`[1, 2, 1, 4, 2]`, we end up with a sum of `10`.Constraints:`1 ≤ l ≤ 104 ``1 ≤ k ≤ 104`` T=10000`Input : The first line contains T the number of test cases followed by 2*T lines containing l and k.Output:For every test case, output one line containing an integer, i.e. the minimal possible sum.Sample Input:25223274895Sample Output:1010647```

hide comments
 < Previous 1 2 Next > nadstratosfer: 2017-11-17 08:10:50 Good time limit so you get to see what you're doing right. Turns out you can even pass with pure Python! Coding style makes all the difference. Great problem. saurabh: 2017-03-22 14:04:03 can anyone help me what to use instead of priority queue to avoid TLE vengatesh15: 2017-03-07 09:59:06 easy one no need of priority queue .... avisheksanvas: 2016-07-12 08:49:07 It does indeed give the feel of a @vectar31 type problem ;) BTW, no queue nothing needed! Last edit: 2016-07-12 08:49:43 jinxer: 2016-06-30 15:27:31 @vectar31 Bro you're an inspiration to me. Can you please give me Your History of submission" (Plaintext Version)"..So that i Could follow it!!! Re: I am just average :) ! Ask Francky, numerix, min_25, Tjandra, Mitch :) ! Last edit: 2016-06-30 17:41:29 iharsh234: 2016-06-30 08:19:11 why priority queue in pypy gives TLE? Edit: Thanks Did it in too slow pypy..hehe Re: Because there are better ways to solve this problem. PyPy is too slow to beat the TL, faster languages might just manage to do that, but that is not what this problem expects you to do. Last edit: 2016-06-30 10:37:30 Shubhransh Srivastav: 2016-06-25 10:14:14 fast i/o+priority queue...just managed to beat the time limit :) mokinjay: 2016-06-17 01:33:29 U have given time limit 5second then how a soln of O(klog(l)) give tle..? even if constraints of k and l are not so large.. Re: Look at the number of test cases, It is 10^4. 10^4*(your calculations with each test case) will time out! Last edit: 2016-06-17 06:21:44 Piyush Kumar: 2016-06-14 15:06:49 @Bhuvanesh, i have updated that number of test cases=10000, and k<=10000, and l<=10000. Given your complexity, your number of calculations will be in the order of 10^9 which will time out. You need to do better with the complexity. Also, think about doing some pre computation. pvsmpraveen: 2016-06-14 14:30:10 Awesome sum! , AC in one go! Last edit: 2016-06-14 14:30:20

 Added by: Piyush Kumar Date: 2016-06-10 Time limit: 5s Source limit: 50000B Memory limit: 1536MB Cluster: Cube (Intel G860) Languages: All except: ASM64 GOSU JS-MONKEY Resource: Standard Pro Co