[Help] Doubt in failing Testcases in Codechef Starters 9 (Div 3) in XLSQUARE

Hey Friends,
I am little newbie here, but have good understanding of Data Structures…
Question: XLSQUARE
I have seen people have implemented solution like, take square-root of n, and then multiply that by a,
but I used another logic like this code, and was able to pass given testcases, but got WA after submission,

int remainder = 0;
if (n % 4 != 0)
    remainder++;

res = (n / 4) * a + remainder * a;

System.out.print(res);

what I was missing here or how can I make this code work?
Question Link: Contest Page | CodeChef
My Solution link: Solution: 49962596 | CodeChef

#include <iostream>
#include<bits/stdc++.h>
using namespace std;

int main() {

    int t;
    cin>>t;
    
    while(t--){
        
        int n,a;
        cin>>n>>a;
        
        cout<<floor(sqrt(n))*a<<endl;
        
    }

	return 0;
}

Why is this giving WA?

Your code fails for :-

1
25 2
Your O/P:- 14
Correct O/P :- 10
1 Like

I think you are trying to divide by 4 because you want to form a square of 2x2 with the blocks, but in fact, to create a big square of length X with smaller blocks of size 1 you need to put at least X^2 of them, using this logic the answer is just the length of the biggest square you can form with small squares (sqrt(x)) multiplied by the length of the smaller squares.

Can you please tell why my code is giving WA?
@pkpawan123 @alexbri @studboygd

I’m not familiar with floor, just do int sq = sqrt(n) and cout << sq * a << “\n”;

It is issue with sqrt() function in c++ , which has precision errors . In order to avoid those precision errors you need to store the result of floor ( sqrt( n ) ) in int or long long variable and then do operations on result .

I have faced same issue multiple times . You can check this blog in codeforces :- Precision issues in sqrt() function of C++ - Codeforces

Thank you!!

I think your logic is wrong because in fact i too thought of making squares in the multiple of 4 but that is not the correct logic. instead what you can do is draw a square and try to draw square adjacent to it .So the pattern will be something like 1,4,9,16,25 … try it yourself.
that is the the why people are taking the nearest square root of the number and multiplying the result with the ‘a’ which is edge of the identical squares
hence
Ans = edge * (nearest square root of n)

Try is yourself you will surely get the intuiton behind it. :smiley:

Because your logic might be wrong
the initution behind uisng square root is as follows:
you might remember that we use square units to denote the area(they can be km2,m2 etc)
now consider that a side of mega square is made up of n squares(like we used to make of n cm)
then it will have n*n square units
that is,it will contain n*n square(we used square as our unit instead of cm)
that is why we are taking square root instead of multiples of four
i hope it will explain why your logic is wrong