Game of Codes(ExtContest)-Anurag and Squares

general
, ,
1

Please help me debug the code for Anurag And Squares Question Here ; My solution giving WA

Please help me find a test case that will give WA on my code, or explain to me why this logic will not work, and correct approach if my solution is completely wrong.

Thanks!

2

Hey for input:37 output should be 26 but your code gives 42.

Your approach is incorrect . check this for correct approach https://math.stackexchange.com/questions/214234/tiling-a-minimal-perimeter-region-with-n-unit-squares

1 Like
3

Try this test case:

13

Expected output: 16
Your code gives: 18

Correct approach(for numbers which are not perfect squares):
Consider 2 numbers a and b which are perfect squares such b>a and b is the immediate perfect square after a. There are exactly 2*sqrt(a) numbers between a and b. If we consider the first sqrt(a) numbers after a and arrange that many number of squares, they will have a minimum perimeter equal to 2 plus the minimum perimeter of a squares when they are arranged. Similarly, when the next sqrt(a) numbers after a are arranged in terms of squares, they will have a minimum perimeter equal to 4 plus the minimum perimeter of a squares when they are arranged.
The following solution works completely fine:

    ll m,n,p;
	cin>>m;
	p=sqrt(m);
	n=pow(p,2);
	if(m==n) cout<<4\*sqrt(n);
    else if((m-n)<=sqrt(n)) //the first sqrt(n) numbers after n
    {
	    cout<<(4\*sqrt(n)+2);
	}
	else //the next sqrt(n) numbers after n
    cout<<(4*sqrt(n)+4);

Consider the test case 13
m=13
p=sqrt(13)=3
n=pow(3,2)=9
m-n>sqrt(n),i.e., 13-9>3
Thus, ans = 4*sqrt(n)+4 = 4*3+4 = 16

1 Like