 DALGONA - Editorial

Practice

Div-3 Contest

Div-2 Contest

Div-1 Contest

Setter: Sarvesh Kesharwani
Tester: Yashodhan Agnihotri , Aman Singhal

EASY

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++;
else if (n == 2) mp++, mp++;
else if (n % 2) mp += n - 2, mp++, mp[(n + 1) / 2]++;
else mp += 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();
}

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.

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