< Back to forum

Editorial of RECode 3.0

Birthday and Chocolates Solution : 

Chetan will get the sum of chocolates given by his friends. Thus, the required answer will be A + B.
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
 
 
int main() {
    int a,b;
    cin>>a>>b;
    cout<<(a+b);
    return 0;
}

Saptarshi's Challenge Solution : 

The substring which occurs maximum number of times will be of length 1. Every character of a string is a palindromic substring. We are simply required to count the maximum number of times any character appeared in the string. This is because if there exits a palindromic substring 's' of length greater than 1 and occurs k number of times, then at least one of character of substring 's' will appear a minimum of 2*k times. Thus, there is a contradiction. For example, if we find a substring 'abcba' which occurs 5 times. We can always consider substring 'a' which will occur atleast 10 times and will be the required substring.
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
 
 
int main() {
    int n;
    cin>>n;
    string s;
    cin>>s;
    int l = s.size();
    int cnt[26] = {0};
    int ans = 0;
    for(int i = 0;i<l;i++){
        cnt[s[i] - 'a']++;
        ans = max(cnt[s[i]-'a'] , ans);
    }
    cout<<ans;
    
    return 0;
}

Natural Number Solution : 

We know the formula for sum of integers from 1 to n. It is given by (n*(n+1))/2. To find sum of integers in the range l to r, we will find sum of integers from 1 to l-1 using above formula and subtract it from sum of integers from 1 to r. This will give the required answer. Thus our answer will be (r*(r+1))/2 - ((l-1)*l)/2;
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
 
 
int main() {
 
    int t;
    cin>>t;
   
    while(t--)
    {
        int a, b;
        cin>>a>>b;
       
        int suma =  (a-1)*(a);
        suma = suma/2;
       
        int sumb = (b)*(b+1);
        sumb = sumb/2;
       
        cout<<sumb-suma<<"\n";
    }
    return 0;
}

Help Vishvanath Solution :

Lets first, sum all the weights of mishtis and if this sum is not properly divisible by 200 then answer is "NO" else in all the other cases answer is "YES" except when all the mishtis are of weight 200 miligram and their count is odd then answer is "NO".
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
 
 
int main() {    
    int t;
    cin>>t;
    int arr[t];
    int c1 = 0;
    int c2 = 0;
    int sum = 0;
    for(int i = 0 ; i < t ; i++)
    {
        cin>>arr[i];
       
        if(arr[i] == 100)
            c1++;
        else
            c2++;
       
        sum += arr[i];
    }
   
    sum = sum/2;
 
    int find = 0;
   
    while(find < sum)
    {
        if(sum - find >= 200 && c2 > 0)
        {
            find += 200;
            c2--;
        }
        else if(sum - find >= 100 && c1 > 0)
        {
            find += 100;
            c1--;
        }
        else
        {
            cout<<0;
            return 0;
        }
    }
    if(sum == find)
        cout<<1;
    else
        cout<<0;
   
   
    return 0;
}

Jadoo and Numbers Solution : 

By checking some trivial cases you can find that there is some pattern and for any number n, the number of ways is 2^(n-1). Now we are going to prove this by induction. We can make a general formula out of it. Let f(n) be the number of partitions of an integer n. 

f(1) = 1 and f(2) = 2

As n can be split in n, {1,n-1} and {n-1,1} and last two terms have one common solution {1,1,1...} so in mathematical form :)

f(n) = 1(without any spliting) + f(n-1) + f(n-1) - 1(for common solution)

f(n) = 2*f(n-1)

if we solve this recurrence relation then we get f(n) = 2^(n-1)
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
 
 
long long pwr(long long b,long long p,long long m){
    long long ans =1;
    while(p){
        if(p&1)
            ans = (ans*b)%m;
        b = (b*b)%m;
        p/=2;
    }
    return ans;
}
 
int main() {
    int t;
    cin>>t;
    while(t--){
        long long mod = 1000000007;
        long long n;
        cin>>n;
        cout<<pwr(2LL,n-1,mod)<<endl;
    }    
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */  
    return 0;
}

Update and find max Solution :

We can use segment tree, fenwick tree etc to solve this question, but we are intrested in some simple approach which is prefix sum. Lets say if we need to add x to the range [l,r] that is equivalent to first make arr[l] = arr[l] + x, arr[r+1] = arr[r+1] - x and then take the prefix some of the array. so first perform all the queries and, then take a prefix sum and find the maximum of this array which is the required answer.
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
 
 
 
int main() {
 
    long long int sze, k;
    cin>>sze>>k;
   
    long long int arr[sze+1];
   
    for(long long int i = 0 ; i<sze+1 ; i++)
        arr[i] = 0;
   
    long long int maxi = -1000000000000009;
    long long int p = 0;
   
    while(k--)
    {
        long long int a,b,c,d;
        cin>>a>>b>>c;
        if(a == 1)
        {
            cin>>d;
            arr[b-1] += d;
            arr[c] -= d;
        }
        else{
           
            for(long long int i = 1 ; i < sze ; i++)
            {
                arr[i]+=arr[i-1];
            }
           
            for(long long int i = b-1; i <c ; i++)
            {
                if(maxi < arr[i])
                    maxi = arr[i];
            }    
        }
    }
   
    cout<<maxi<<"\n";
   
    return 0;
}

 

Asked by: rishup132 on April 7, 2019, 1:04 p.m. Last updated on April 7, 2019, 1:04 p.m.


Enter your answer details below:


Preview

Enter your comment details below:

Preview




1 Answer(s)

avatar

Another approach for the question Jadoo and numbers will be:

We can write n as a sum of n 1's. That is:

1 + 1 + 1 + .... (n times) = n

So, number of gaps where we can partition (every plus sign) is equal to exactly (n-1). For every gap, we have 2 choices, either we partition there or not. So, the final answer is 2*2*2*......(n-1) times = 2^(n-1). We can use modular exponentiation of simple loop to calculate this.

Saptarshi_Dey last updated on April 7, 2019, 1:04 p.m. 0    Reply    Upvote   

Instruction to write good question
  1. 1. Write a title that summarizes the specific problem
  2. 2. Pretend you're talking to a busy colleague
  3. 3. Spelling, grammar and punctuation are important!

Bad: C# Math Confusion
Good: Why does using float instead of int give me different results when all of my inputs are integers?
Bad: [php] session doubt
Good: How can I redirect users to different pages based on session data in PHP?
Bad: android if else problems
Good: Why does str == "value" evaluate to false when str is set to "value"?

Refer to Stack Overflow guide on asking a good question.