I found it very difficult to understand the solution, that is provided. Can someone hire a person who can tell this is Hindi, or may a bit more clearer English.
I don’t mean to sound rude, or I am not at all commenting on the coding skill of the Solution provider, but still, as I have paid for the subscription, it should be a bit more clear.
7 Likes
so i came up with this but 1 problem i couldn’t figure out for the even n , can anyone say this?
// bool isPerfectSq(long double n){
// if(n>=0){
// ll sr = sqrt(n);
// return (sr*sr == n);
// }
// return false;
// }
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); //this is fast I/O (inputput output) use header file <cstdio> ll t;cin>>t; while(t--){ ll n;cin>>n; ll x = sqrt(n); if(x*x == n){ if(x*x==n) cout<<0<<" "<<x<<endl; } else if(n%2==1){ int first = floor(x); int second = first-1; if((first*first)+(second*second)==n) cout<<second<<" "<<first<<endl; else cout<<-1<<endl; } else if(n%2==0){ int first = floor(x); int second = x-1; int third = x+1; if((first*first)+(first*first)==n) cout<<first<<" "<<first<<endl; else if((first*first)+(second*second)==n) cout<<first<<" "<<second<<endl; else if((second*second)+(second*second)==n) cout<<second<<" "<<second<<endl; else if((second*second)+(second*third)==n) cout<<second<<" "<<third<<endl; else if((third*third)+(third*third)==n) cout<<third<<" "<<third<<endl; else if((first*first)+(third*third)==n) cout<<first<<" "<<third<<endl; } } // int n;cin>>n; // cout<<(sqrt(n)); return 0;}
can anyone explain this one ? the editorial is …
From the problem statement, N’s largest odd factor is at most 10^5, we can assume N = n * 2^k, where n <= 10^5 and k >= 0.
-
When k % 2 == 0, if we can find some (a, b) that a^2 + b^2 = n, we can construct an answer:
A = a * 2^{k/2}
B = b * 2^{k/2} -
When k % 2 == 1, if we can find some (a, b) that a^2 + b^2 = 2n, we can also construct an answer:
A = a * 2^{ \lfloor k/2 \rfloor}
B = b * 2^{ \lfloor k/2 \rfloor }
So the problem reduced to find (a, b) for a^2 + b^2 = x, where x <= 2 * 10^5.
We can bruce all a and b <= sqrt(2e5), and store x = (a, b) in a map.
3 Likes
#include <bits/stdc++.h>
using namespace std;
#define fast()
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
#pragma GCC optimize(“O3”)
#pragma GCC Optimization(“unroll-loops”)
#pragma GCC target(“avx2”)
#define ll long long int
#define endl “\n”
#define debug(x)
for (auto element : x)
cout << element << " ";
cout << endl;
#define debugp(x)
for (auto element : x)
cout << element.first << " " << element.second << endl;
#define db(x) cout << #x << " = " << x << endl;
#define MAX2(x, y) ((x) >= (y) ? (x) : (y))
#define MIN2(x, y) ((x) >= (y) ? (y) : (x))
#define MIN3(x, y, z) MIN2(x, MIN2(y, z))
#define MAX3(x, y, z) MAX2(x, MAX2(y, z))
#define pb push_back
#define pf push_front
#define popf pop_front
#define popb pop_back
const ll MOD = 1e9 + 7;
const ll N = 1e5 + 10;
#define ni1(t)
ll t;
cin >> t;
#define ni2(a, b)
ll a, b;
cin >> a >> b
#define ni3(a, b, c)
ll a, b, c;
cin >> a >> b >> c
#define ni4(a, b, c, d)
ll a, b, c, d;
cin >> a >> b >> c >> d
#define ni5(a, b, c, d, e)
ll a, b, c, d, e;
cin >> a >> b >> c >> d >> e
#define ni6(a, b, c, d, e, f)
ll a, b, c, d, e, f;
cin >> a >> b >> c >> d >> e >> f
#define rep(i, a, b) for (ll i = a; i <= b; i++)
#define revrep(i, a, b) for (ll i = a; i >= b; i–)
#define mem0(a) memset(a, 0, sizeof(a))
#define vll(v, n)
vector v(n);
rep(i, 0, n - 1) { cin >> v[i]; }
#define array(arr, n)
ll arr[n];
rep(i, 0, n - 1) cin >> arr[i];
#define arrayx(arr, n, x)
ll arr[n];
rep(i, 0, n - 1) arr[i] = x;
#define printarray(arr, n) rep(i, 0, n - 1) cout << arr[i];
vector<pair<ll,ll>> square;
unordered_map<ll,ll> s;
void store(){
for(int i=0;ii<=1e5;i++) {
square.push_back(make_pair(ii,i));
s[i*i]=i;
}
}
int main(){
fast();
ni1(t);
store();
// for(int i=0;i<square.size();i++){
// cout<<square[i].first<<" “<<square[i].second<<endl;
// }
while(t–){
ni1(n);
ll odddivisor=0;
if(n%2) odddivisor=n;
else{
ll temp=n;
while(temp){
temp/=4;
if(temp%2) {
odddivisor=temp;
break;
}
}
}
bool flag=0;
ll multiplesquare=n/odddivisor;
//cout<<odddivisor<<” “<<multiplesquare<<” “<<endl;
if(s.find(multiplesquare)==s.end()) cout<<-1<<endl;
else{
for(int i=0;i<square.size();i++){
if(square[i].first>odddivisor) break;
if(s.find(odddivisor-square[i].first)!=s.end() && square[i].first!=odddivisor-square[i].first){
cout<<square[i].second*s[multiplesquare]<<” "<<s[odddivisor-square[i].first]*s[multiplesquare]<<endl;
flag=1;
break;
}
}
if(!flag) cout<<-1<<endl;
}
}
return 0;
}
can anyone help me out why it is giving runtime error?
It is giving time limit exceeded. Can you please show where I am going wrong in this submission please?
https://www.codechef.com/viewsolution/78413809
You will need to prepare the map first, then answering the T queries.
https://www.codechef.com/viewsolution/78325119
hey @iceknight1093
So knowing => X2+ Y2 = N
we can find X and Y for 4N, 8N, and so on. How do we find X and Y for 2N, 6N… ?
You solution seems to only find answers for 4KN
for example:
knowing 32+ 42 = 25
how do we find X and Y for X2+ Y2 = 50 ?
1 Like
now the solutions require money. isn’t it cheap? we do contest and then can’t upsolve for money. soln is really helpful
You’re correct that my code finds a solution for 4N knowing a solution for N. For this problem, that is enough because if N \gt 2 \times 10^5, then N will definitely be divisible by 4 because of the constraint on the largest odd divisor.
So while N \gt 2 \times 10^5 you can keep dividing by 4, and once you reach something \leq 2\times 10^5 you just bruteforce.
There is also a way to get a solution for 2N from a solution for N. The method of doing that is detailed in the editorial: see the “Proof” section.
Written editorials never have and never will be paid, I sure hope you didn’t pay anything to view this page.
Which part do you find unclear?
1 Like
I think for N which is not in the form of 4KN we should have to use brute force,
and the worst case TC will be 10 ^ 15 * 10 ^ 5
But that case never came because the largest odd factor of N is at most 10^5
For ex 10000000019 is not a valid test case, because the largest odd factor will be 10000000019 (which is greater than 10 ^ 5).
Also 2 * 10000000019, 6 * 10000000019, 8 * 10000000019 all these are invalid test cases
Please correct me if I am wrong
how ??
wouldn’t it be (A^2+B^2)/2=N/2;
Oh, I see your confusion, I used the same variable names.
What I meant was the following:
When N is even, there exists a pair (A_1, B_1) such that A_1^2 + B_1^2 = N if and only if there exists a pair (A_2, B_2) such that A_2^2 + B_2^2 = N/2.
Essentially, you can find an answer for N if and only if you can find an answer for N/2. This is the main reason why the given solution works at all.
3 Likes
@iceknight1093 thanks for the great explanation.
Most of the explanation revolves around 2n but in the actual code we are checking for 4n; I get it’s the same concept, but I’m not able to understand how 4n will always exist and why not 8n or 16n.
Thanks!
My code (and lots of other people’s) uses 4N simply because it’s easy to implement: you just multiply both A and B by 2.
It’s totally fine to use the 2N construction by doing (A, B) \to (A+B, A-B), you can see that the preparer’s code does exactly this. In fact, if you notice, the construction for 4N just comes from applying the construction for 2N twice, since (A+B)+(A-B) = 2A and (A+B)-(A-B) = 2B.
1 Like
What wrong in this code??
Cannot pass last two test cases
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define tc int t;cin>>t;while(t--)
void solve()
{
ll n,count = 0,flag = 0;
cin>>n;
while(n % 4 == 0)
{
n /= 4;
count++;
}
ll i , j ;
for(i = 0 ; i*i <= n ; i++)
{
j = n - i * i ;
ll root = sqrt(j);
if(root * root == j)
{
flag = 1 ;
j = root ;
break;
}
}
if(!flag)
cout << " -1 "<< endl;
else
cout << pow(2,count) * i << " " << pow(2,count) * j << endl ;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("error.txt","w",stderr);
#endif
tc solve();
return 0;
}
I have to use the type conversion
cout << (ll)powl(2,count) * i << " " << (ll)powl(2,count) * j << endl ;
Now it works
I don’t trust the sqrt function (and you shouldn’t either), this is just a safe way of computing it. It just so happens that this line is unnecessary for this specific problem, but I always use it when I take square roots.
1 Like
how did he came up with that construction . of 2n
why a+b and a-b and how?