A coding contest based on algorithms, data structures and problem solving, was organized in assocaition with Codechef and Training & Placement Cell, BIT Sindri.
This is the editorial for all the problems. We welcome suggestions and improvement on this editorial by .
Authors are : Hanzala Sohrab (IT 2018), Adarsh Kumar Sinha (ECE 2018), Adarsh Kumar Mandal (IT 2018)
Examination Conundrum (EXCON)
Implementation based
In this problem, the first thing to do is to find the total length L of all the videos. 24 hours = 1440 minutes. If the total length is greater than 24 hours (i.e. 1440 minutes), output -1. Otherwise, find the difference between 1440 and L. Let d = 1440 - L. Then the hour at which Chef should start watching is the integral value d / 60 and the minute is d \% 60 (i.e. the remainder when d is divided by 60.)
#include<bits/stdc++.h>
using namespace std;
int main() {
cin.sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while (t--)
{
int i, n, s = 0;
cin >> n;
int l[n];
for (i = 0; i < n; ++i)
cin >> l[i];
for (i = 0; i < n; ++i)
s += l[i];
if (s > 1440)
cout << "-1\n";
else
{
int hours = (1440 - s) / 60;
int minutes = (1440 - s) % 60;
cout << hours << ' ' << minutes << '\n';
}
}
return 0;
}
Chef And Numbers (CHEFNUMS)
Number Theory, Implementation based
Let’s iterate over the first number of the pair, let it be x . Then we need to count numbers from 1 to m with the remainder of dividing 5 equal to (5 - x mod 5) mod 5. For example, you can precalc how many numbers from 1 to m with every remainder between 0 and 4.
#include<bits/stdc++.h>
using namespace std ;
#define ll long long
int main () {
#ifndef ONLINE_JUDGE
freopen( "input.txt" , "r" , stdin );
freopen( "output.txt" , "w" , stdout );
#endif
int n, m;
cin >> n >> m;
ll ans = 0 ;
int r = m / 5 ;
int rm = m % 5 ;
int a[ 5 ];
// we precal how many numbers from 1 to m with every remainder
// between 0 to 4 and store in array a .
a[ 0 ] = 0 ;
a[ 1 ] = r;
a[ 2 ] = r;
a[ 3 ] = r;
a[ 4 ] = r;
for ( int i = 1 ; i <= rm; i++) {
a[i]++;
}
for ( int i = 1 ; i <= n; i++) {
int rq = 5 - (i % 5 );
ans += a[rq];
}
cout << ans << endl ;
}
Treasure Hunt (TRHUNT)
Implementation based
In this problem, no matter where the treasure is hidden, Chef has to walk a maximum distance of 4 units. So, the possible distances are : 1, 2, 3, 4. The answer to this problem can simply be obtained by calculating the number of steps required to bring 1 (one) to the center of the matrix. Find the difference between the center row (row 3) and the row where 1 is present. Also, find the difference between the center column (column 3) and the column where 1 is present. The answer can be obtained by adding the results from above steps.
#include <bits/stdc++.h>
using namespace std;
int main() {
cin.sync_with_stdio(false);
cin.tie(0);
long long int t;
cin >> t;
while (t--)
{
long long int i, j, c = 0, ro = -1, co = -1, m[5][5];
char e;
for (i = 0; i < 5; ++i)
for (j = 0; j < 5; ++j)
{
cin >> m[i][j];
if (m[i][j])
{
ro = i + 1;
co = j + 1;
}
}
cin >> e;
cout << abs(3 - ro) + abs(3 - co) << '\n';
}
return 0;
}
Paths (PATHS1)
Math, Catalan Numbers, Permutations & Combinations
This problem is similar to the problem of finding the number of monotonic lattice paths from point (0,0) to point (N, N) in a square lattice of size N×N, which do not pass above the main diagonal (i.e. connecting (0,0) to (N,N)), which in turn, is an application of Catalan Numbers. The answer can be easily found by calculating the N-th Catalan number.
#include<iostream>
using namespace std;
// Returns value of Binomial Coefficient C(n, k)
unsigned long int binomialCoeff(unsigned int n, unsigned int k) {
unsigned long int res = 1;
// Since C(n, k) = C(n, n-k)
if (k > n - k)
k = n - k;
// Calculate value of [n*(n-1)*---*(n-k+1)] / [k*(k-1)*---*1]
for (int i = 0; i < k; ++i)
{
res *= (n - i);
res /= (i + 1);
}
return res;
}
// A Binomial coefficient based function to find nth catalan
// number in O(n) time
unsigned long int catalan(unsigned int n) {
// Calculate value of 2nCn
unsigned long int c = binomialCoeff(2*n, n);
// return 2nCn/(n+1)
return c/(n+1);
}
// Driver program to test above functions
int main()
{
cin.sync_with_stdio(false);
cin.tie(0);
int t, i, n;
cin >> t;
while (t--){
cin >> n;
cout << catalan(n) << '\n';
}
return 0;
}
Encypted String (ENSTR)
Strings, Burrows - Wheeler transform
This problem is based on the Burrows - Wheeler transform that is used for restructuring data in such a way that the transformed message is more compressible. Take a string, for example, banana. Its Burrows - Wheeler transform is annb\aa. As can be seen, most of the similar characters appear together. So, the string has become more compressible. The most important application of Burrows - Wheeler transform is found in biological sciences where genomes(long strings written in A, C, T, G alphabets) don’t have many runs but they do have many repeats.
#include<bits/stdc++.h>
using namespace std;
string BWT(const string& text) {
string result = "";
// write your code here
string s = text, x;
int i, l = text.length();
vector<string> m(l);
for (i = 0; i < l; ++i)
{
s = s[l - 1] + s.substr(0, l - 1);
m[i] = s;
}
sort(m.begin(), m.end());
for (i = 0; i < l; ++i)
result += m[i][l - 1];
return result;
}
int main() {
cin.sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while (t--)
{
string text;
cin >> text;
cout << BWT(text) << endl;
}
return 0;
}
Lucky Integer (LUCKINT)
Dynamic programming
For Subtask 1 (30 points): For the smaller constraints, brute force approach can be used considering all possiblities of operations (i.e, + and - ). By generating all possible integers check if it is a Lucky Integer. For considering operation before each digit , it is suggested to store the number N as a string. If |S| denotes the length of the the string, Time Complexity for this approach = O(|S|^2
For Subtask 2 (100 points): For larger constraints, above approach may not fit the time complexity. For this a better approach is Dynamic Programming. For each DP state, we store a sum derived at before position. Hence, DP[prev_sum][curr_pos] state is used for memoization. Each DP state signifies “The number of ways in which a Lucky Integer can be generated using the prev_sum as the previous sum and cur_pos as the current position in the digits string”. Therefore, in other terms it can be stated that we are asked to find DP[prev_sum=0][cur_pos=0]. For filling up each DP state, a recursive apporach has been used. During each recursion call, we first use a ‘+’ on the prev_sum and ascend the cur_pos to cur_pos + 1 and call the recursive function with the updated parameters, lets assume that this call returns a number ‘opnWithPlus’. After a ‘+’ operation we use a ‘-‘ operation on prev_sum again in the same function and call the recursive function with cur_pos+1, lets assume that this call returns a number ‘opnWithMinus’. Lets add these two and call it ‘totalWays’. Hence,
totalWays = opnWithPlus + opnWithMinus
This totalWays stored in each recursive call denotes the total number of ways to get a lucky Integer for a number N with a previous sum as prev_sum and current position as cur_pos. Now as the recursive method is ready, one can observe that there may be several cases/calls where we have prev_sum and a cur_pos which was already called before, so in order to avoid recomputation with the same arguments, we can store every prev_sum and cur_pos in the DP[prev_sum][cur_sum] which basically denotes the total number of ways/operations to form a Lucky Integer.
Base Case : When the cur_pos reaches the position string.length() + 1, we know that all the digits are considered. Hence at this position, prev_sum denotes the final number obtained by the operations. Hence, this returns 0 if N is not divisible by prev_sum and 1 when N it is.
About the DP state : We take the DP[500][20] for convenience. As the maximum sum of digits can be 9X9X9X..(18 times) which for the convenience can be taken as 200, Similarly the minimum of the digits can be -200. Therefore we choose 500 as the max prev_sum so as we could use every non negative index of the DP ( As the minimum would be 250-200=50 and 250+200=450, 250 has been considered as datum). Hence we will use dp[200+sum][cur_pos] as DP state.
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define elif else if
#define PI 3.1415926535897932384
#define MOD 1000000007
using namespace std;
string s;
ll t;
ll n;
ll dp[500][20]; // dp[prev_sum][cur_pos]
ll countWays(ll prev_sum, ll cur_pos){
if( cur_pos==s.size() ){ // BASE CASE
if(prev_sum<=0){
return 0; // If prev_sum obtained was non positive, we know it can't be a divisor of N
}
if( n % prev_sum==0 ){
return 1; // If prev_sum is a divisor, return 1 as a Lucky Integer was obtained
}
return 0; // Else return 0
}
if(dp[250+prev_sum][cur_pos]!=-1){
return dp[250+prev_sum][cur_pos]; // If the state was encountered before, return this value
}
ll totalWays;
int opnWithPlus = countWays(prev_sum+(s[cur_pos]-'0'),cur_pos+1); // recursive call using prev_sum + current digit
int opnWithMinus = countWays(prev_sum-(s[cur_pos]-'0'),cur_pos+1); // recursive call using prev_sum - current diit
totalWays = opnWithPlus + opnWithMinus;
return dp[250+prev_sum][cur_pos] = totalWays; // Store this dp state with prev_sum and cur_pos
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
scanf("%lld",&t);
while(t--){
scanf("%lld",&n); // The number N
s = to_string(n);
memset(dp,-1,sizeof(dp)); // Setting each dp state to be -1 so that we know if we had encountered it before or not
printf("%lld\n",countWays(0,0));
}
}