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.


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.


1 ≤ l ≤ 104 

1 ≤ k ≤ 104


Input : 

The first line contains T the number of test cases followed by 2*T lines containing l and k.


For every test case, output one line containing an integer, i.e. the minimal possible sum.

Sample Input:






Sample Output:



hide comments
Ishan: 2018-04-19 07:22:18

O((k+l)*log(l)) with C++ STL's priority queue is sufficient, just be careful not to use computation heavy floating point calculating like sqrt() etc.

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.

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