Atcoder Beginner Contest - 163

D - Sum of Large Numbers

Problem Statement : here

Solution - 

The tricky part is the addition of 10^100. So, let us assume that we are using k numbers to generate our sum. Clearly, in this case, the coefficient of 10^100 will be k. If we would have used k+1 terms, the coefficient would have differed and this makes the two numbers different. So the cases like 1+ 8 = 3+5+1 are not possible, because each of them has different coefficients of 10^100. So, what we are left with? 

Given k -> number of terms, what are the possible values of the sum I can get? 

So, if I calculate the minimum possible sum and the maximum possible sum, then I claim that we can get any number in between this sum range. It is a well-known fact. So, we use it in order to solve this question. The proof - intuitive that can be taken to convince is :

min-sum  = 0 + 1 + 2 + 3 .......... + k-1

max-sum = n-(k-1) + n-(k-2) + n-(k-3) + ....... + n

To get any sum in this range, we can start distributing the difference between given value and min-sum to 0 (until it becomes n-(k-1)), remaining to 1 and so on up to k-1 (until it becomes n).

The code : 

ll modp(ll a, ll b){ ll res = 1; while(b>0){ if (b&1) res = (res*a)%M1; a = (a*a)%M1; b>>=1; } return res; } ll minsum[200005]; void solve() { ll n,k; cin>>n>>k; minsum[1] = 0; ll maxsum = (((n*(n+1))%M1)*modp(2,M1-2))%M1; rep(i,2,n+2){ minsum[i] = (minsum[i-1] + i-1 + M1)%M1; } ll ans = 0; rep(i,k,n+2){ ans = (ans + maxsum - minsum[n-i + 1] - minsum[i] + 1 + M1)%M1; } cout << ans << endl; }

Math #1 : Binary Search - GSC Triple Threat 2020

Does a Solution Exist??

Problem Statement - here

Problem - You are given a positive integer z, and you need to find if there exist two positive integers x, and y such that the given equation is satisfied.

Input:
The first line of input contains T denoting the number of testcases. T testcases follow. Each testcase contains a single line of input containing z.

Output:
For each testcase, in a new line, print "Yes"(without quotes) if the equation can be satisfied, else print "No" (without quotes).

Constraints:
1 <= T <= 100
1 <= z <= 263-1

Solution : 

Given the range of z, it appears that multiple test cases are there so, there must be some time solution...But there is indeed no constant time solution...the equation reduces to finding the solution of x*x + y*y  = z where both x&y are positive integers. By the heading of the post, it is clear that we will apply a binary search for finding the solution. BUT, why does it work?

Assume 2 pointers -> i and j. Let x,y be the values satisfying x*x + y*y = z.

Currently: i < = x and j >=y

so, whenever we have i*i + j*j > z; we will decrease our j. we cannot decrease our i because the optimal value (x) is still greater than i.

Whenever we have i*i + j*j < z; we will increase our i. we cannot increase j because the optimal value (y) is still greater than j.

Onc can see that we will converge to the solution fairly easily. 

Something that is new here is we are handling 2 pointers without a mid for our binary search!

Here is the code : 

void solve()
{
    // Here ll means long long int
    ll n;
    cin>>n;
    ll low = 1;
    ll high = ceil(sqrt(n));
    bool flag = 0;
    while(low<=high){
        ll val = low*low + high*high;
        if (val == n){
            flag = 1;
            break;
        }
        else if (val < n) low++;
        else high--;
    }
    if (flag) cout << "Yes" << endl;
    else cout << "No" << endl;

}