PROBLEM LINK:
Practice
Div-3 Contest
Div-2 Contest
Div-1 Contest
Setter: Sarvesh Kesharwani
Tester: Yashodhan Agnihotri , Aman Singhal
DIFFICULTY:
EASY
PREREQUISITES:
Math
PROBLEM:
Given an integer N , print N integers in val-freq format such that sum of their squares is a perfect square.
EXPLANATION:
Since there are multiple approaches for this problem, two approaches shall be described here, one easy, and the other not so intuitive.
Approach 1
We can write N^2 = (N-2)^2 + 4N - 4 .
We will now simplify the RHS.
(N-2)^2 + 4N - 4 = (N-2)^2 + 2^2(N-1)
Here, we can clearly see RHS can be represented as the sum of squares of (N-2) and N-1 occurences of 2 .
We have our final answer as 1 occurrence of (N-2) and (N-1) occurrences of 2 .
Approach 2
If N is even :
We can assume a perfect square as (N-1) + x^2 , where (N-1) is the sum of 1^2 taken (N-1) times and x is any number.
Since N is even, N-1 will be odd, therefore N-1 can be written as :
N-1 = 2x + 1 , where x is an integer.
Adding x^2 to both sides gives us, N-1 + x^2 = (x+1)^2 , therefore we can say that our assumption was correct.
Therefore, now we just need to find the value of x . It can be found from N-1 = 2x + 1 and therefore, x = (N-2)/2 .
We have our final array consisting of (N-1) occurrences of 1 and 1 occurrence of (N-2)/2 .
If N is odd:
We can assume a perfect square as (N-2) + 2^2 + x^2 = (N+2) + x^2 , where (N-2) is the sum of 1^2 taken (N-2) times, 2^2 is the square of 2 and x is any number.
Since N is odd, N+2 will be odd, therefore N+2 can be written as :
N+2 = 2x + 1 , where x is an integer.
Adding x^2 to both sides gives us, N+2 + x^2 = (x+1)^2 , therefore we can say that our assumption was correct.
Therefore, now we just need to find the value of x . It can be found from N+2 = 2x + 1 and therefore, x = (N+1)/2 .
We have our final array consisting of (N-2) occurrences of 1 , 1 occurrence of 2 and 1 occurrence of (N+1)/2 .
Both solutions have O(1) time complexity.
SOLUTIONS:
Setter's Solution
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin >> t;
while (t--)
{
int n;
cin >> n;
map<int, int> mp;
if (n == 1) mp[1]++;
else if (n == 2) mp[3]++, mp[4]++;
else if (n % 2) mp[1] += n - 2, mp[2]++, mp[(n + 1) / 2]++;
else mp[1] += n - 1, mp[(n - 2) / 2]++;
cout << mp.size() << "\n";
for ( auto[x, y] : mp)
cout << x << " " << y << "\n";
}
return 0;
}
Tester's Solution (C++)
#include <bits/stdc++.h>
using namespace std;
void solve()
{
int tc;cin>>tc;while(tc--)
{
ll n;
cin>>n;
if(n == 1){
cout<<1<<"\n"<<1<<" "<<1<<"\n";
}else if(n == 2){
cout<<2<<"\n"<<3<<" "<<1<<"\n"<<4<<" "<<1<<"\n";
}else if(n == 3){
cout<<2<<"\n"<<1<<" "<<1<<"\n"<<2<<" "<<2<<"\n";
}else if(n == 4){
cout<<1<<"\n"<<1<<" "<<4<<"\n";
}else{
cout<<2<<"\n"<<2<<" "<<n-1<<"\n"<<(n-2)<<" "<<1<<"\n";
}
}
}
int main()
{
solve();
return 0;
}
Tester's Solution (Python)
import math
T=int(input())
for _ in range(T):
N=int(input())
x=0
for i in range(int(math.sqrt(N))):
x=x+1
if (N==1):
print(1)
print(1,1)
elif(N==2):
print(2)
print(3,1)
print(4,1)
elif (N==4):
print(1)
print(1,4)
else:
print(2)
print(2,N-1)
print(N-2,1)
For doubts, please leave them in the comment section, I’ll address them.
3 Likes
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define ll long long
// #define gcd __gcd
#define setbits(x) __builtin_popcountll(x)
#define zrobits(x) __builtin_ctzll(x)
#define mod 1000000007
#define mod2 998244353
#define maxe *max_element
#define mine *min_element
#define inf 1e18
#define pb push_back
#define all(x) x.begin(), x.end()
#define lb lower_bound
#define ub upper_bound
#define ins insert
#define sz(x) (int)(x).size()
#define mk make_pair
#define deci(x, y) fixed<<setprecision(y)<<x
#define w(t) int t; cin>>t; while(t--)
#define hemant ios_base::sync_with_stdio(false); cin.tie(nullptr)
#define PI 3.141592653589793238
#define mem0(x) memset(x,0,sizeof x)
#define mem1(x) memset(x,-1,sizeof x)
#define nl "\n"
#define yy cout<<"YES"<<"\n"
#define nn cout<<"NO"<<"\n"
#define vi vector<int>
#define vll vector<long long>
#define vvi vector<vector<int> >
#define ff first
#define ss second
#define debug(x) cerr << #x <<" "; _print(x); cerr << endl;
typedef unsigned long long ull;
typedef long double lld;
ll modular_expo(long long x, unsigned ll y, int p){ll res = 1;x = x % p;if (x == 0) return 0;while (y > 0){if (y & 1)res = (res*x) % p;y = y>>1;x = (x*x) % p;}return res;}
vector<ll> sieve(ll n) {ll *arr = new ll[n + 1](); vector<ll> vect; for (ll i = 2; i <= n; i++)if (arr[i] == 0) {vect.push_back(i); for (ll j = 2 * i; j <= n; j += i)arr[j] = 1;} return vect;}
ll primefactorscount(ll n){vector<ll> v1=sieve(n);ll cnt=0;for(ll i=0;i<sz(v1);i++){if(n%v1[i]==0){cnt++;}}return cnt;}
void _print(ll t) {cerr << t;}
void _print(int t) {cerr << t;}
void _print(string t) {cerr << t;}
void _print(char t) {cerr << t;}
void _print(lld t) {cerr << t;}
void _print(double t) {cerr << t;}
void _print(ull t) {cerr << t;}
template <class T, class V> void _print(pair <T, V> p);
template <class T> void _print(vector <T> v);
template <class T> void _print(set <T> v);
template <class T> void _print(deque <T> v);
template <class T, class V> void _print(map <T, V> v);
template <class T, class V> void _print(multimap <T, V> v);
template <class T> void _print(multiset <T> v);
template <class T, class V> void _print(pair <T, V> p) {cerr << "{"; _print(p.ff); cerr << ","; _print(p.ss); cerr << "}";}
template <class T> void _print(vector <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(set <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(deque <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(multiset <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void _print(map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void _print(multimap <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";};
void solve(){
w(t){
ll n;
cin>>n;
ll g=0;
if(n==1){
cout<<1<<nl;
cout<<1<<" "<<1<<nl;
continue;
}
if(n==2){
cout<<2<<nl;
cout<<3<<" "<<1<<nl;
cout<<4<<" "<<1<<nl;
continue;
}
ll k=n-2;
ll a=0,b=0;
for(ll i=1;i<=1000;i++){
for(ll j=1;j<=1000;j++){
ll sum=k+i*i+j*j;
long double s=sqrt(sum);
if(floor(s)==ceil(s)){
a=i;
b=j;
g=1;
break;
}
}
if(g==1){
break;
}
}
if(a==1 and b==1){
cout<<1<<nl;
cout<<1<<" "<<n<<nl;
continue;
}
if(a==b){
cout<<2<<nl;
cout<<1<<" "<<n-2<<nl;
cout<<a<<" "<<2<<nl;
continue;
}
if(a==1 and b!=1){
cout<<2<<nl;
cout<<1<<" "<<n-1<<nl;
cout<<b<<" "<<1<<nl;
continue;
}
if(a!=1 and b==1){
cout<<2<<nl;
cout<<1<<" "<<n-1<<nl;
cout<<a<<" "<<1<<nl;
continue;
}
cout<<3<<nl;
cout<<1<<" "<<n-2<<nl;
cout<<min(a,b)<<" "<<1<<nl;
cout<<max(a,b)<<" "<<1<<nl;
}
}
int32_t main() {
hemant;
solve();
}
Please check this solution. It is showing incorrect answer
2 Likes
We can always write
NxN = (N-1)x(4) + sqrt(NxN - ((N-1)x4));
it can be proven that (NxN - ((N-1)x4)) will always be a perfect square.
Hence, we get N - 1 numbers from first Term and Nth number from second term
PS:- Forgot to mention 1, 2, and 4 will need to be handled separately you can check them in my code.
link to my solution : https://www.codechef.com/viewsolution/55303754
How to approach such problems ? How did you think of "ok lemme represent N^2 = (N−2)^2+4N−4
" ?
6 Likes
Because it is incorrect. 1000 will not work. Even first 1000 square numbers will not work.
If you want to know how can you get to a solution you can try this.
I haven’t checked the editorial but here’s how I got to the solution →
Step1 → write down some perfect square numbers
1 4 9 16 25 36 …( and so on )
now you can see the differences between the perfect squares
3 5 7 9 11 … (and so on)
if you write this thing on paper now you can clearly see
3/2 = 1 and sqr(1) = 1 ; ( reminder: 3 was the difference between 1 and 4 )
5/2 = 2 and sqr(2) = 4 ; ( reminder: 5 was the difference between 4 and 9)
7/2 = 3 and sqr(3) = 9 ; ( reminder: 7 was the difference between 9 and 16)
so we can conclude for a odd number say X,
X/2 = Y and sqr(Y) = Z ; (then X will be the difference between Z and W)
so we can conclude W (a perfect square) = Z(a perfect square) + X ;
and best part is Z is nothing but sqr(X/2) , So now you can find a relation right ?
This overall conclusion is enough to reach the main solution. I am not telling the whole solution here.
(That’s how I reached the solution)
5 Likes
I have mentioned a thinking process, I guess that might help you.
1 Like
I guess if I take 1000 as input,
Then my output is,
2
1 999
5 1
and if you check it
(1^2+1^2…)999+5^2=999+25=1024 which is equal to the square of 32
Then what is incorrect in this can you explain me
Number of elements = 999+1 = 1000
Number of distinct elements = 2 (1,5)
I didn’t mean 1000 as an input. I meant just Brute-forcing first 1000 values will not work.
Then the compiler should show TLE
But it is showing wrong answer
That is why i am asking what is incorrect
Here, the catch was this solution worked for every n except, n = 1,n = 2, n = 4.
2 Likes
I haven’t mentioned it, but tackled them in my code you can check out!
bro, I meant that if you only run your loop till 1000 it will not cover all the testcases.
Check for n = 100644000
.
Ya bro you are right
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define ll long long
// #define gcd __gcd
#define setbits(x) __builtin_popcountll(x)
#define zrobits(x) __builtin_ctzll(x)
#define mod 1000000007
#define mod2 998244353
#define maxe *max_element
#define mine *min_element
#define inf 1e18
#define pb push_back
#define all(x) x.begin(), x.end()
#define lb lower_bound
#define ub upper_bound
#define ins insert
#define sz(x) (int)(x).size()
#define mk make_pair
#define deci(x, y) fixed<<setprecision(y)<<x
#define w(t) int t; cin>>t; while(t--)
#define hemant ios_base::sync_with_stdio(false); cin.tie(nullptr)
#define PI 3.141592653589793238
#define mem0(x) memset(x,0,sizeof x)
#define mem1(x) memset(x,-1,sizeof x)
#define nl "\n"
#define yy cout<<"YES"<<"\n"
#define nn cout<<"NO"<<"\n"
#define vi vector<int>
#define vll vector<long long>
#define vvi vector<vector<int> >
#define ff first
#define ss second
#define debug(x) cerr << #x <<" "; _print(x); cerr << endl;
typedef unsigned long long ull;
typedef long double lld;
ll modular_expo(long long x, unsigned ll y, int p){ll res = 1;x = x % p;if (x == 0) return 0;while (y > 0){if (y & 1)res = (res*x) % p;y = y>>1;x = (x*x) % p;}return res;}
vector<ll> sieve(ll n) {ll *arr = new ll[n + 1](); vector<ll> vect; for (ll i = 2; i <= n; i++)if (arr[i] == 0) {vect.push_back(i); for (ll j = 2 * i; j <= n; j += i)arr[j] = 1;} return vect;}
ll primefactorscount(ll n){vector<ll> v1=sieve(n);ll cnt=0;for(ll i=0;i<sz(v1);i++){if(n%v1[i]==0){cnt++;}}return cnt;}
void _print(ll t) {cerr << t;}
void _print(int t) {cerr << t;}
void _print(string t) {cerr << t;}
void _print(char t) {cerr << t;}
void _print(lld t) {cerr << t;}
void _print(double t) {cerr << t;}
void _print(ull t) {cerr << t;}
template <class T, class V> void _print(pair <T, V> p);
template <class T> void _print(vector <T> v);
template <class T> void _print(set <T> v);
template <class T> void _print(deque <T> v);
template <class T, class V> void _print(map <T, V> v);
template <class T, class V> void _print(multimap <T, V> v);
template <class T> void _print(multiset <T> v);
template <class T, class V> void _print(pair <T, V> p) {cerr << "{"; _print(p.ff); cerr << ","; _print(p.ss); cerr << "}";}
template <class T> void _print(vector <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(set <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(deque <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(multiset <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void _print(map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void _print(multimap <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";};
void solve(){
w(t){
ll n;
cin>>n;
ll g=0;
if(n==1){
cout<<1<<nl;
cout<<1<<" "<<1<<nl;
continue;
}
if(n==2){
cout<<2<<nl;
cout<<3<<" "<<1<<nl;
cout<<4<<" "<<1<<nl;
continue;
}
ll k=n-2;
ll a=1,b=1;
int ch=0;
for(ll i=1;i<=9999;i++){
for(ll j=1;j<=9999;j++){
ll sum=k+i*i+j*j;
long double s=sqrt(sum);
if(floor(s)==ceil(s)){
a=i;
b=j;
g=1;
break;
}
}
if(g==1){
ch=1;
break;
}
}
// if(ch==1){
// cout<<"True";
// }
if(a==1 and b==1){
cout<<1<<nl;
cout<<1<<" "<<n<<nl;
continue;
}
if(a==b){
cout<<2<<nl;
cout<<1<<" "<<n-2<<nl;
cout<<a<<" "<<2<<nl;
continue;
}
if(a==1 and b!=1){
cout<<2<<nl;
cout<<1<<" "<<n-1<<nl;
cout<<b<<" "<<1<<nl;
continue;
}
if(a!=1 and b==1){
cout<<2<<nl;
cout<<1<<" "<<n-1<<nl;
cout<<a<<" "<<1<<nl;
continue;
}
cout<<3<<nl;
cout<<1<<" "<<n-2<<nl;
cout<<min(a,b)<<" "<<1<<nl;
cout<<max(a,b)<<" "<<1<<nl;
}
}
int32_t main() {
hemant;
solve();
}
This worked
I just sat and wasted my one hour on this
#include<bits/stdc++.h>
using namespace std;
bool isvowel(char m){
if( m=='a' || m=='e' || m=='i' || m=='o' || m=='u')
return true;
else
return false;
}
int main(){
int T;
cin>>T;
while(T–){
int n; int count =0; int ans = INT_MAX;
cin>>n;
string s; string p;
cin>>s>>p;
for(int j =‘a’;j<=‘z’;j++){
for(int i=0;i<n;i++){
if(s[i]=='?')
s[i]=j;
else if(p[i]=='?')
p[i]=j;
}
for(int i=0;i<n;i++){
if(isvowel(s[i])!=isvowel(p[i]))
count = count+2;
else if(s[i]==p[i]){
continue;
}
else
count++;
}
ans=min(ans,count);
}
cout<<ans<<endl;
}
return 0;
}
can u pls tell me my mistake???
#include<bits/stdc++.h>
using namespace std;
bool isvowel(char m){
if( m=='a' || m=='e' || m=='i' || m=='o' || m=='u')
return true;
else
return false;
}
int main(){
int T;
cin>>T;
while(T–){
int n; int count =0; int ans = INT_MAX;
cin>>n;
string s; string p;
cin>>s>>p;
for(int j =‘a’;j<=‘z’;j++){
for(int i=0;i<n;i++){
if(s[i]=='?')
s[i]=j;
else if(p[i]=='?')
p[i]=j;
}
for(int i=0;i<n;i++){
if(isvowel(s[i])!=isvowel(p[i]))
count = count+2;
else if(s[i]==p[i]){
continue;
}
else
count++;
}
ans=min(ans,count);
}
cout<<ans<<endl;
}
return 0;
}
can u pls tell me my mistake???
for(int i=0;i<n;i++){
if(s[i]=='?')
s[i]=j;
if(p[i]=='?') // modified here
p[i]=j;
}
1 Like
First of all the loop will be for(char j =‘a’;j<=‘z’;j++)
The he condition will not be if else if,
if(s[i]==’?’)
s[i]=j;
if(p[i]==’?’)
p[i]=j;
1 Like
`
ll n;
cin >> n;
if (n == 1)
{
cout << 1 << "\n";
cout << 1 << " " << 1 << "\n";
}
else if (n == 2)
{
cout << 2 << "\n";
cout << 3 << " " << 1 << "\n";
cout << 4 << " " << 1 << "\n";
}
else
{
cout << 2 << "\n";
cout << 2 << " " << n - 1 << "\n";
cout << n - 2 << " " << 1 << "\n";
}
`
Update : The error here was that n=4 needs to be handled separately.
strcmp
December 23, 2021, 9:36am
22
So basically W(perfect square) = (x/2 * x/2) + x
where x is and odd number.
This made the problem so easy. Nice observation !!
1 Like