DALGONA - Editorial

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.

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