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:

2

5

2

2327

4895


Sample Output:

10

10647


hide comments
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
Bhuvnesh Jain: 2016-06-14 06:06:56

@Piyush, what is the expected time complexity? Mine is O(k log(l)), which is giving TLE, with and without fast I/O.

Edit: Thanks for the update, Solved it, trying for reducing the time and reaching the expected solution. Nice problem :)

Re: Glad you liked it :)

Last edit: 2016-06-16 12:42:24

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