Hi. Thank you for participating in the BITCode July Round. We hope that you enjoyed the problems we prepared for you. Incase, if you weren’t able to solve them, here are the detailed explanations and solutions with tested code that you can read to figure out what went wrong in the contest.

Upsolving the problems is the most important thing to do after a contest. Here they are:-

Gajodhar and chocolates

Problem Link: Click Here
Author: Anuj
Topics Covered: Implementation Array math

Problem Setter’s Solution:

Problem Overview:
- Gajodhar possesses an array of integers, where each element represents the quantity of a specific type of chocolate. He decides to select only those chocolates whose quantity is even, as he has a particular liking for even numbers. The task is to determine the total number of chocolates he has after selecting only the even ones.
Algorithm Explanation:
- The problem can be solved using a simple iteration through the given array. We initialize a variable ‘totalChocolates’ to 0, which will store the sum of even chocolates. We then traverse through each element of the array and check if it is even (i.e., divisible by 2). If the element is even, we add its value to the ‘totalChocolates’. By the end of the loop, the ‘totalChocolates’ variable will contain the sum of all even chocolates.
Detailed Steps:
- Read the integer ‘n’ from the input, representing the size of the array.
- Create an array ‘arr’ of size ‘n’ to store the quantities of different types of chocolates.
- Initialize a variable ‘totalChocolates’ to 0.
- Read ‘n’ integers from the input and store them in the array ‘arr’.
- Traverse through the array using a loop from 0 to ‘n-1’. a. For each element ‘arr[i]’ in the array:
- Check if ‘arr[i]’ is even by using the condition ‘arr[i] % 2 == 0’. If it is even, add ‘arr[i]’ to the ‘totalChocolates’.
- Output the value of ‘totalChocolates’, which represents the total number of even chocolates Gajodhar has.

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;

    int arr[n];
    int totalChocolates = 0;

    for (int i = 0; i < n; i++) {
        cin >> arr[i];
        if (arr[i] % 2 == 0) {
            totalChocolates += arr[i];
        }
    }

    cout << totalChocolates << endl;

    return 0;
}

Special Addition

Problem Link: Click Here
Author: Anuj
Topics Covered: Implementation

Problem Setter’s Solution:

Initialization:
- Two integer variables n and m are declared to store the input numbers.
- An empty vector v is created to store the digits of the resulting sum. Add corresponding digits.
- The code enters a loop and iterates through the digits of n and m from right to left using the modulo operator (%).
- For each iteration, it extracts the rightmost digit of n and m, denoted as d1 and d2, respectively.
- The corresponding digits are then added together (d1 + d2) and the sum is pushed into the vector v.
- This step handles the addition of digits as per the algorithm’s rules. Add remaining digits.
- After the first step, one of the numbers (n or m) might still have some remaining digits to be processed.
- The code checks if there are any remaining digits in m. If so, it enters another loop to handle the remaining digits.
- In this loop, the rightmost digit of m is extracted using the modulo operator and pushed into the vector v. Add remaining digits (contd.).
- After handling the digits of m, the code checks if there are any remaining digits in n. If so, it enters another loop to handle them.
- In this loop, the rightmost digit of n is extracted using the modulo operator and pushed into the vector v. Print the sum.
- Finally, the code prints the elements of the vector v in reverse order, from right to left, which represents the sum of n and m.
- The reverse order ensures that the digits are printed correctly, from the most significant digit to the least significant digit.

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,m;
    cin>>n>>m;
    vector <int> v;
    while(n>0 && m>0)
    {
        int d1=n%10;
        int d2=m%10;
        v.push_back(d1+d2);
        n/=10;
        m/=10; 
    }
    if(m>0)
    {
        while(m>0)
        {
            int d=m%10;
            v.push_back(d);
            m/=10;
        }
    }
    if(n>0){
    while(n>0)
        {
            int d=n%10;
            v.push_back(d);
            n/=10;
        }
    }
   for(int i=v.size()-1;i>=0;i--)
    cout<<v[i];
}

Make them equal

Problem Link: Click Here
Author: Ritik Raj Pandey
Topics Covered: binary search, constructive algorithms, data structures, greedy , implementation, strings, two pointers.

Problem Setter’s Solution:

To solve the problem, we remove all occurrences of ‘b’ from both strings ‘a’ and ‘b’. If the modified ‘a’ and ‘b’ are not equal, it is impossible to make the strings equal since we can only swap adjacent characters with the given operations. In this case, the answer is “NO”. Otherwise, if ‘a’ and ‘b’ are equal after removing ‘b’s, we check whether the remaining characters ‘a’ and ‘c’ are in the correct order to be swapped with ‘b’.

We record the positions of ‘a’s and ‘c’s in separate arrays for both ‘a’ and ‘b’. Then, we compare the positions to ensure that each ‘a’ in ‘a’ appears before the corresponding ‘a’ in ‘b’, and each ‘c’ in ‘a’ appears after the corresponding ‘c’ in ‘b’. If any ‘a’ in ‘a’ appears after the corresponding ‘a’ in ‘b’ or any ‘c’ in ‘a’ appears before the corresponding ‘c’ in ‘b’, it is impossible to make the strings equal.

In this case, the answer is “NO”. If all ‘a’s and ‘c’s appear in the correct order, the answer is “YES”, and Alex can make the strings equal without Harry noticing. The time and space complexity of the solution is O(n), where ‘n’ is the length of the strings ‘a’ and ‘b’, making it efficient for large input strings.

#include<bits/stdc++.h>
using namespace std;

void solve(){
        int n;
        cin>>n;
        string s,t;
        cin>>s>>t;
        string a,b;
        for(int i=0;i<n;i++){
                if(s[i]!='b')
                a.push_back(s[i]);
                if(t[i]!='b')
                b.push_back(t[i]);
        }
        if(a!=b){
        cout<<"NO\n";
        return;
        }
        vector<int>a_checks,a_checkt;
        for(int i=0;i<n;i++){
                if(s[i]=='a')
                a_checks.push_back(i);
                if(t[i]=='a')
                a_checkt.push_back(i);
        }
        for(int i=0;i<a_checks.size();i++){
        if(a_checks[i]>a_checkt[i]){
        cout<<"NO\n";
        return;
        }
        }
        
        vector<int>c_checks,c_checkt;
        for(int i=0;i<n;i++){
                if(s[i]=='c')
                c_checks.push_back(i);
                if(t[i]=='c')
                c_checkt.push_back(i);
        }
        for(int i=0;i<c_checks.size();i++){
        if(c_checks[i]<c_checkt[i]){
        cout<<"NO\n";
        return;
}
}
        
        cout<<"YES\n";
        
}
int main(){
        int m;
        cin>>m;
        while(m--){
               solve();  
        }
}

Help Binod

Problem Link: Click Here
Author: Mohit Pandey
Topics Covered: Segment tree

Problem Setter’s Solution:

Approach:

The requirement of the question is that for each group of size say ri, we move from left to right iterating over the hostels and whenever we find the hostel having enough rooms (hj >= ri) for the group we can assign those rooms and update the available rooms as (hj -= ri). The brute-force way to do this is O(n^2) and it will give TLE.
Optimizing:
- The observation is that we require the index of the leftmost hostels having enough rooms, so, therefore, we can maintain a max segment tree for the hostel’s array which will give us the maximum number of rooms available in each range of hostels.
- Now the little modification is that we create the segment tree array (say tree) of user-defined data type struct{ value, index}, hence, for the vertex v, tree[v].value gives the maximum rooms in the range that the vertex v holds and tree[v].index is the corresponding hostel’s array index of the same maximum value.
- Now we can query for each group, say for the group ri we start at the root vertex (say v) and go down the tree ,we first check the left child whether the value here is greater than equals to ri, if yes then we move left otherwise the target hostel lies on the right side hence we move right.
- When we reach our required vertex say (ver) corresponding to a single target hostel we update the value of this vertex here as tree[ver].value -= ri and return the index tree[ver].index.
- Similarly, we update the parent vertex value and index for each child while backtracking.
- The condition when there is no relevant hostel can be handled by comparing the max value of the segtree with the required group size in O(1)

Time Complexity: As for build it is O(n), for the query it is O(logn), the overall complexity becomes O(mlogn).

#include <bits/stdc++.h>
using namespace std;

 
struct Vertex{
  int value;
  int index;
};
const int MAXN=200011;
Vertex tree[4*MAXN];
#define INF -1e9+7;
 
// This generates a segment tree which can give me
// the maximum element in a range as well as the index of that element.
 
void build(int a[], int v, int tl, int tr){
 
    if(tl==tr){
        tree[v].value=a[tl];
        tree[v].index=tl+1;
        return;
    }
    int mid = (tl+tr)/2;
    build(a,2*v,tl,mid);
    build(a,2*v+1,mid+1,tr);
    if(tree[2*v].value >= tree[2*v+1].value){
       tree[v]=tree[2*v];
    }
    else{
       tree[v]=tree[2*v+1];
    }
}
 
int query(int v, int tl, int tr, int num){
 
     if(tree[v].value < num)
        return 0;
   
    if(tl==tr){
 
        tree[v].value = tree[v].value - num;
        return tree[v].index;
    }
 
 
   int mid = (tl+tr)/2;
 
   if(tree[2*v].value >= num){
      int idx = query(2*v,tl,mid,num);
      if(tree[2*v].value >= tree[2*v+1].value){
        tree[v] = tree[2*v];
      }
      else{
        tree[v]=tree[2*v+1];
      }
      return idx;
   }
   else{
      int idx= query(2*v+1,mid+1,tr,num);
       if(tree[2*v].value >= tree[2*v+1].value){
         tree[v]=tree[2*v];
      }
      else{
       tree[v]=tree[2*v+1];
      }
 
      return idx;
   }
 
   
 
}

void solve(){
 
    int n,m;
    cin >> n >> m;
    int h[n],r[m];
    for(int i=0;i<n;i++)cin >> h[i];
    for(int i=0;i<m;i++)cin >> r[i];
    build(h,1,0,n-1);
 
    for(int i=0;i<m;i++)
    cout << query(1,0,n-1,r[i]) << " ";
 
}
int main(){
solve();
return 0;
}

Help Priyanshu

Problem Link: Click Here
Author: Abhishek Mondal
Topics Covered: Trees ,Dp

Problem Setter’s Solution:

This question can be solved using trees and dynamic programming.The Houses can be considered as vertices of Tree and roads can be considered as its edges.From the question we can see that there is no cycles,no multiple edges and no self loops.

We have to count the sum of distances for all pairs of vertices. For each edge, we should add to the answer the number of times this edge appears in a path between some two vertices. If sv denotes the size of the subtree of the vertex v (we can first root the tree in 1), we should add sv·(n - sv) to the sum.
In this problem, the answer is around S/k, where S is the answer for the known problem described above. But for each path with length L, we should add ⌈L/k⌉ =(L + f(L,k))/k to the answer, where f(L, k) says how much we must add to L to get a number divisible by k (f(10, 3) = 2, f(11, 3) = 1, f(12, 3) = 0). We know the sum of because it’s in total. What remains is to compute the sum of f(L, k).
To achieve that, for each remainder modulo k, we want to know the number of paths with length that has this remainder. For example, if k = 3 and there are 200 paths with remainder 1, they all have f(L, k) = 2, so we should add 200·2 to the answer.

Let’s root the tree in any vertex and do bottom-up dp. For each subtree we compute the k values: for each remainder modulo k how many paths (starting from the root of this subtree) have this remainder. We can merge two subtrees in O(k2), so the total complexity is O(n·k2).

#include <bits/stdc++.h>
using namespace std;
const int nax = 2e5 + 5;
vector<int> edges[nax];
int count_subtree[nax][5];
int total_subtree[nax];
long long answer;
int n, k;

int subtract(int a, int b) {
	return ((a - b) % k + k) % k;
}

void dfs(int a, int par, int depth) {
	count_subtree[a][depth % k] = total_subtree[a] = 1;
	for(int b : edges[a])
		if(b != par) {
			dfs(b, a, depth + 1);
			for(int i = 0; i < k; ++i)
				for(int j = 0; j < k; ++j) {
					// compute distance modulo k
					int remainder = subtract(i + j, 2 * depth);
					// compute x such that (distance + x) is divisible by k
					int needs = subtract(k, remainder);
					answer += (long long) needs
							* count_subtree[a][i] * count_subtree[b][j];
				}
			for(int i = 0; i < k; ++i)
				count_subtree[a][i] += count_subtree[b][i];
			total_subtree[a] += total_subtree[b];
		}
	// in how many pairs we will count the edge from 'a' to its parent?
	answer += (long long) total_subtree[a] * (n - total_subtree[a]);
}

int main() {
	scanf("%d%d", &n, &k);
	for(int i = 0; i < n - 1; ++i) {
		int a, b;
		scanf("%d%d", &a, &b);
		edges[a].push_back(b);
		edges[b].push_back(a);
	}
	dfs(1, -1, 0);
	assert(answer % k == 0);
	printf("%lld\n", answer / k);
}

Happy Learning!!!

BITCode July Round Editorial

Editorial

Gajodhar and chocolates

Problem Setter’s Solution:

Problem Overview:

Algorithm Explanation:

Detailed Steps:

Special Addition

Problem Setter’s Solution:

Initialization:

Make them equal

Problem Setter’s Solution:

Help Binod

Problem Setter’s Solution:

Approach:

Optimizing:

Help Priyanshu

Problem Setter’s Solution: