Editorial of RECode 3.0

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;
}

 

rishup132
Ritesh Gupta
rishup132

Please Log in to answer

Note: Your answer should not be too short. Please wait a few seconds for the editor to load



Please make sure the answer is not too short

1 Answer

rishi_07
rishi_07 17:29, Oct 06
Saptarshi Dey

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.




Please make sure the answer is not too short
1 Upvotes
Comments
No Comments yet