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

Contest Link: Learning Sprint-1 (Intermediate Track)

Problem: Jump & Reach
Problem Setter: @vok_8

Hint-1

Suppose you are at `step-(x)` (`x>=1`)

Then, one of the following will always be true:

1. Your last jump was from `step-(x-1)` to `step-(x)` (If `x>=1`)
2. Your last jump was from `step-(x-2)` to `step-(x)` (If `x>=2`)
3. Your last jump was from `step-(x-3)` to `step-(x)` (If `x>=3`)

Hint-2

Using conditions described in Hint-1, you can see that the recurrence relation for ways to reach `step-(x)` will be as follows:

• `ways_to_reach(x) = 1`, if `x=0`
• `ways_to_reach(x) = ways_to_reach(x-1)`, if `x=1`
• `ways_to_reach(x) = ways_to_reach(x-1) + ways_to_reach(x-2)`, if `x=2`
• `ways_to_reach(x) = ways_to_reach(x-1) + ways_to_reach(x-2) + ways_to_reach(x-3)`, if `x>=3`

Hint-3

The answer may not fit in a 32-bit Integer.

Hint-4

Using Simple Recursion will lead to complexity of `O(3^n)`.

So, we will store the values already calculated in an array, and use them wherever required. (Dynamic Programming).

Tutorial

Pre-compute the answer for all `n`, from `1` to `60` and then answer all the test cases in `O(1)`.

Use the Recursive Relation, from `Hint-2` to pre-calculate the ways (answer) for all `n`.

• Time Complexity: `O(n)` (Overall)

• Space Complexity: `O(n)`

Problem Setter's Code (C++)
``````#include <bits/stdc++.h>
using namespace std;
#define ll long long int
ll ways;
ll recur(int n)
{
{
return ways[n]; //just return that (no need to recur for that 'n' again)
}
if(n==1)
{
ways[n]=recur(n-1);
return ways[n];
}
else if(n==2)
{
ways[n]=recur(n-1)+recur(n-2);
return ways[n];
}
else //n>=3
{
ways[n]=recur(n-1)+recur(n-2)+recur(n-3);
return ways[n];
}
}
int main()
{
int t;
cin>>t;
for(int i=0; i<61; i++) //initialise the ways[] array as all (-1)'s (-1 means not calculated yet)
{
ways[i]=-1;
}
ways=1; //since you are at step-0, in the beginning
ways=recur(60); //recur for max. value (while finding the ways(60), we will also get the values for n<60, calculated)
{
int n;
cin>>n;
cout<<ways[n]<<endl;
}
return 0;
}
``````

Problem: Remove Sub-Array
Problem Setter: @vok_8

Hint-1

Think of `Binary Search` on the length of the sub-array to be removed.

Hint-2

For every index `i`, save the index `j`, the index till when the sub-array starting from `i` is increasing. (Let this array be named `inc_till[]`)

Hint-3

For every sub-array of size `mid` during `Binary Search`, check if the array becomes increasing after the removal of that sub-array using the `inc_till[]` array. (Reference from `Hint-2`)

Tutorial

Do `Binary Search` on the length of the sub-array to be removed.

Check for current `mid` in Binary Search, whether it is possible to remove any sub-array of size `mid` to make the array increasing.

If `YES`, then go to the `Left - Half` of the range `[l,r]`
Else, go to the `Right - Half` of the range `[l,r]`

Check out the `Code` below, for more clarity in the approach.

• Time Complexity: `O(n * lg(n))`

• Space Complexity: `O(n)`

There may be other approaches to the problem, as well.

Problem Setter's Code (C++)
``````#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
vector<int> v(n);
for(auto &x:v)
{
cin>>x;
}
vector<int> inc_till(n);
for(int i=0; i<n; i++)
{
int left=i;
while(i<n-1 && v[i]<=v[i+1]) //iterate till the sub-array starting from index 'left' is increasing
{
i++;
}
int right=i;
//the sub-array [left,right] is increasing
for(int ind=left; ind<=right; ind++) //so, for all 'ind', belonging to [left,right], inc_till[ind]=right
{
inc_till[ind]=right;
}
}
int l=0, r=n-1; //Binary Search Range -> [0,n-1] (Min. Possible Ans=0, Max. Possible Ans=n-1)
while(l<=r) //Perform 'Binary Search'
{
int mid=(l+r)/2;
bool possible=false;
for(int i=0; i<n; i++) //we are trying to remove sub-array starting from index 'i', of length 'mid'
{
int left=i;
int right=i+mid-1;
//sub-array to be removed, in consideration -> [left,right]
if(right>=n) //'no' sub-array of length 'mid' is remaining to check
{
break;
}
if(left==0) //[0,right] is the sub-array, in consideration
{
if(inc_till[right+1]>=n-1) //just check that the sub-array [right+1,n-1] is increasing
{
possible=true;
break;
}
}
else if(right==n-1) //[left,n-1] is the subarray, in consideration
{
if(inc_till>=left-1) //just check that the subarray [0,left-1] is increasing
{
possible=true;
break;
}
}
else //[left,right] is the subarray, in consideration, where left!=0 & right!=n-1
{
if(v[left-1]<=v[right+1]) //only possible to remove this subarray [left,right], when v[left-1]<=v[right+1]
{
if(inc_till>=left-1 && inc_till[right+1]>=n-1) //just check if subarrays [0,left-1] & [right+1,n-1] are increasing
{
possible=true; //possible, since subarrays [0,left-1] & [right+1,n-1] are increasing & v[left-1]<=v[right+1]
break;
}
}
}
}
if(possible) //'mid' is a possible answer
{
r=mid-1; //go to 'left' range (smaller ans (< mid) is possible)
}
else
{
l=mid+1; //go to 'right' range (only values >=mid is/are possible as answer)
}
}
return 0;
}
``````

Problem: Valid Sub-Sequences
Problem Setter: @vok_8

Hint-1

Recursively go through all sub-sequences of the given array.

Hint-2

Use `std::set/std::map` (in C++) or `dictionary` (in Python) to store the sub-sequences with `sum=x`, because we have to print the “distinct sub-sequences”.

Tutorial

Recursively traverse over all sub-sequences of the given array.

For each sub-sequence, find its sum and if it is equal to `x`, then add it to the `set` or `dictionary` or `map` of the valid-subsequences.

Then, print all the valid sub-sequences in increasing order.

• Time Complexity: `O(2^n)`

• Space Complexity: `O(n * (2^n))`

Problem Setter's Code (C++)
``````#include <bits/stdc++.h>
using namespace std;
set<vector<int>> ans;
void rec(vector<int> &arr, int index, vector<int> sub_subqeuence, int &target_sum)
{
{
if(int(sub_subqeuence.size())!=0) //check for current sub-sequence
{
int sum=0;
for(auto val:sub_subqeuence)
{
sum+=val;
}
if(sum==target_sum) //if current sub-sequence is valid, add it to the set of 'ans'
{
ans.insert(sub_subqeuence);
}
}
}
else
{
rec(arr,index+1,sub_subqeuence,target_sum); //sub-sequence without including arr[index]
sub_subqeuence.push_back(arr[index]);
rec(arr,index+1,sub_subqeuence,target_sum); //sub-sequence including arr[index]
}
return;
}
int main()
{
int n;
cin>>n;
vector<int> v(n);
for(auto &x:v)
{
cin>>x;
}
int target_sum;
cin>>target_sum;
vector<int> curr; //to store the current sub-subqeuence
rec(v,0,curr,target_sum); //recursively go through all the subsequences
for(auto sub_subqeuence:ans)
{
for(auto num:sub_subqeuence)
{
cout<<num<<" ";
}
cout<<"\n";
}
return 0;
}
``````