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:
- Your last jump was from
step-(x-1)tostep-(x)(Ifx>=1) - Your last jump was from
step-(x-2)tostep-(x)(Ifx>=2) - Your last jump was from
step-(x-3)tostep-(x)(Ifx>=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, ifx=0 -
ways_to_reach(x) = ways_to_reach(x-1), ifx=1 -
ways_to_reach(x) = ways_to_reach(x-1) + ways_to_reach(x-2), ifx=2 -
ways_to_reach(x) = ways_to_reach(x-1) + ways_to_reach(x-2) + ways_to_reach(x-3), ifx>=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[61];
ll recur(int n)
{
if(ways[n]!=-1) //already calculated
{
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[0]=1; //since you are at step-0, in the beginning
ways[60]=recur(60); //recur for max. value (while finding the ways(60), we will also get the values for n<60, calculated)
while(t--) //answer 't' test-cases
{
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[0]>=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[0]>=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)
}
}
cout<<l<<"\n"; //answer=l
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(index==int(arr.size())) //no more elements ahead
{
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;
}
Feel free to ask your queries/doubts and share your ideas in the comment section.