Editorial: Learning Sprint-1 (CodeChef College Chapters - Beginner Track)

editorial
, , , , , , , , , , ,
1

Contest Link: Learning Sprint-1 (Beginner Track)

Problem: Print Sub-Array
Problem Setter: @vok_8

Tutorial

We have to just input the array and print the array from position l (index l-1) to position r (index r-1).

Algorithm Snippet (If input of array is in 0-indexing) 
for i=l-1 to i=r-1
{
      print(a[i])
}
Algorithm Snippet (If input of array is in 1-indexing) 
for i=l to i=r
{
      print(a[i])
}

  • Time Complexity: O(n)

  • Space Complexity: O(n) (Also, possible in O(1))

Problem Setter's Code (C++) 
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int arr[n];
    for(int i=0; i<n; i++) //0-indexing
    {
        cin>>arr[i];
    }
    int l,r; 
    cin>>l>>r; //Input is in 1-indexing (Position)
    for(int i=l-1; i<=(r-1); i++) //0-indexing
    {
        cout<<arr[i]<<" ";
    }
    cout<<"\n";
    return 0;
}

Problem: Derive Good String
Problem Setter: @vok_8

Hint-1

We don’t have to do anything about the characters which only occur once.

Hint-2

Also, we don’t have to do anything about the characters which don’t occur in the string.

Tutorial

We only need to remove x-1 occurrences of all the characters, which occur x times, where x>1.

  • Time Complexity: O(string length), per test case.

  • Space Complexity: O(string length), per test case. (Also, possible in O(1), per test case)

Problem Setter's Code (C++) 
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    cin>>t; //'t' test cases
    while(t--)
    {
        string s;
        cin>>s;
        int n=int(s.length());
        int countt[26]; //to store count of characters
        for(int i=0; i<26; i++) //initialise count of all characters to 0
        {
            countt[i]=0; 
        }
        for(int i=0; i<n; i++) //traverse the string to derive count of all characters
        {
            int index_of_character=s[i]-'a'; //for 'a'=0, 'b'=1, 'c'=2, .. , 'z'=25
            countt[index_of_character]++;
        }
        int ans=0;
        for(int i=0; i<26; i++)
        {
            if(countt[i]>1) //if count of character is > 1
            {
                ans+=(countt[i]-1);
            }
        }
        cout<<ans<<"\n";
    }
    return 0;
}

Problem: Get on the String
Problem Setter: @vok_8

Hint

There is only 1 subsequence of length n for a string, of length n.

Tutorial

Since, there is only 1 subsequence of length n for a string, of length n, the answer will be the string itself.

  • Time Complexity: O(n)

  • Space Complexity: O(n) (Also, possible in O(1))

Problem Setter's Code (C++) 
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    string s;
    cin>>s;
    cout<<s<<"\n";
    return 0;
}

Problem: Is Sum Possible
Problem Setter: @vok_8

Hint-1

The minimum sub-array sum will be 0 and maximum sub-array sum will be 100*n, for the given array, according to the given constraints.

Hint-2

Pre-compute the sub-array sums and the store the count of each sub-array sum (in O(n^2) or O(n^3)), before the queries, so that you don’t have to compute the count of queried sum, for each query.

Tutorial

Pre-compute the sub-array sums and the store the count of each sub-array sum (in O(n^2) or O(n^3)), before the queries, so that you don’t have to compute the count of queried sum, for each query.

For each query,

  • If x<0 or x>100*n, output 0. (Since those sums aren’t possible for any sub-array of given array)
  • Else, output the pre-computed count.

  • Time Complexity: O(n^3) (Also, possible in O(n^2))

  • Space Complexity: O(n)

Problem Setter's Code (C++) 
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int arr[n];
    for(int i=0; i<n; i++) //get the array input
    {
        cin>>arr[i];
    }
    int countt[(100*n)+1]; //to store count of possible sub-array sums, of given array
    for(int i=0; i<(100*n)+1; i++) //initialise values in countt[] array
    {
        countt[i]=0;
    }
    for(int l=0; l<n; l++) //precompute count of possible sub-array sums (in O(n^3))
    {
        for(int r=l; r<n; r++)
        {
            int sum_of_subarray_from_l_to_r=0;
            for(int ind=l; ind<=r; ind++) //to calculate sub-array sum of sub-array [l,r]
            {
                sum_of_subarray_from_l_to_r+=arr[ind];
            }
            countt[sum_of_subarray_from_l_to_r]++; //increment the count of current sub-array sum
        }
    }
    int q;
    cin>>q; //input 'q', the number of queries
    while(q--) //answer the queries
    {
        int x;
        cin>>x;
        if(x<0 || x>(100*n)) //case when 'x' isn't a possible sum of any sub-array of the given array
        {
            cout<<0<<"\n";
        }
        else
        {
            cout<<countt[x]<<"\n";
        }
    }
    return 0;
}

Feel free to ask your queries/doubts and share your ideas in the comment section.

3 Likes
2

Nicely played with the constraints!

1 Like