Hi. Thank you for participating in the BITCode June 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:-

Attend Classes

Problem Setter’s Solution:

To determine whether Priyanshu and Mohit need to attend more classes to meet the 75% attendance requirement.

  • First, we calculate the minimum number of classes required to meet the 75% attendance requirement. This is done by multiplying the total number of classes ‘n’ by 0.75:

  • minimum_classes = 0.75 * n

  • Next, we calculate the total number of classes attended by both Mohit and Priyanshu:

  • total_classes_attended = x + y

  • If the total_classes_attended is greater than or equal to the minimum_classes, it means they have already met or exceeded the 75% attendance requirement, and they do not need to attend more classes. In this case, we can output “NO”

  • If the total_classes_attended is less than the minimum_classes, it means they need to attend more classes to meet the 75% attendance requirement. In this case, we can output “YES”.

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, x, y;
    cin >> n >> x >> y;

    double minimum_classes = 0.75 * n;
    int total_classes_attended = x + y;

    if (total_classes_attended >= minimum_classes) {
       cout << "NO" << endl;
    } else {
     
        cout  << "YES" << endl;
    }

    return 0;
}

Optimal Eater

  • Problem Link: Click Here

  • Author: Anuj

  • Topics Covered: Sorting, Array, Greedy, Maths

Problem Setter’s Solution:

  • The code starts by taking input for the number of snack varieties, ‘n’, and the maximum amount of money Ritik can spend, ‘x’.

  • It then creates a vector ‘prices’ to store the prices of individual snacks and takes input for ‘n’ prices.

  • The code sorts the ‘prices’ vector in ascending order using the std::sort() function from the algorithm library.

  • Next, the code initializes two variables, ‘snacksCount’ and ‘totalCost’. ‘snacksCount’ keeps track of the number of snacks selected, and ‘totalCost’ represents the cumulative cost of the selected snacks.

  • The code then enters a loop that iterates through the sorted ‘prices’ vector. It checks if the current snack’s price, prices[i], can be bought within the remaining budget. If adding the current snack’s price to the ‘totalCost’ does not exceed ‘x’, it increments ‘snacksCount’ and adds the price to ‘totalCost’. If the budget is exceeded, the loop breaks since adding more snacks would exceed the budget limit.

  • After the loop, the code calculates the number of extra snacks that can be bought with the remaining money, ‘x - totalCost’, by dividing it by the price of the cheapest snack, ‘prices[0]’. This calculation is done using the line int extra=(x-totalCost)/prices[0];.

  • Finally, the code outputs the sum of ‘snacksCount’ and ‘extra’, which represents the total number of snacks Ritik can buy while maximizing the variety and utilizing the remaining budget.

This implementation follows a greedy approach by selecting snacks in ascending order of prices until the budget is exhausted. It also considers utilizing any remaining money to buy additional snacks of the cheapest variety.

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, x;
    std::cin >> n >> x;

    std::vector<int> prices(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> prices[i];
    }

    // Sort the prices in ascending order
    std::sort(prices.begin(), prices.end());

    int snacksCount = 0;
    int totalCost = 0;
    for (int i = 0; i < n; ++i) {
        // Check if the current snack can be bought within the budget
        if (totalCost + prices[i] <= x) {
            snacksCount++;
            totalCost += prices[i];
        } else {
            break; // Stop the loop since remaining snacks will exceed the budget
        }
    }

    // If there are remaining coins, buy additional snacks of minimum price.
     int extra=(x-totalCost)/prices[0]; 
    std::cout << snacksCount+extra << std::endl;

    return 0;
}

Ace The Test

Problem Setter’s Solution:

The provided code aims to find the maximum credit each friend can help Anuj achieve. It takes input ‘n’ and ‘s’, the number of friends and subjects respectively. Then, it reads the learning capacity ‘x’ of each friend and the time ‘t’ and credit ‘c’ for each subject. The code sorts the subjects based on their time requirements in ascending order. Finally, for each friend, it calculates the total credit they can contribute by iterating through the subjects and considering subjects with time requirements less than the friend’s learning capacity. The total credit for each friend is then printed.

Solution:

  • Initialize a fixed-sized array ‘a’ of length ‘x’ (1e5) to store the learning capacity of each friend.
  • Read the values of ‘s’ and ‘b’, representing the number of friends and subjects, respectively.
  • Read ‘s’ integers and store them in the array ‘a’, representing the learning capacity of each friend.
  • Create an array of pairs ‘dg’ of length ‘b’ to store the time and credit for each subject.
  • Read ‘b’ pairs of integers and store them in ‘dg’, representing the time and credit for each subject.
  • Sort the array ‘dg’ in ascending order based on the first element of each pair (time).
  • For each friend’s learning capacity in array ‘a’:
  • Find the position of the first subject in ‘dg’ whose time requirement is greater than the friend’s learning capacity using the lower_bound function.
  • Calculate the total credit that the friend can contribute by summing up the credits of subjects before this position.
  • Print the total credit for the friend.
  • Return 0 to indicate successful execution of the program.

Time Complexity:

Reading inputs: O(s + b), since we read ‘s’ integers for the learning capacity and ‘b’ pairs for the subject details. Sorting the array ‘dg’: O(b log b), as we sort ‘b’ elements based on the time requirements. For each friend’s learning capacity: Finding the position using lower_bound: O(log b) Summing up the credits: O(b) Therefore, the overall time complexity is O(s + b + b log b + s * (log b + b)).

Space Complexity:

Array ‘a’ of length x (1e5): O(x) or O(1), as it has a fixed size. Array ‘dg’ of length ‘b’: O(b), as it stores ‘b’ pairs. Therefore, the overall space complexity is O(max(x, b)) or O(max(1e5, b)), which can be simplified to O(max(1e5, b)).

#include<bits/stdc++.h>
using namespace std;
int main(){
    
    long long x=1e5;
    int s,b,a[x];
    cin>>s>>b;
    pair <int,int> dg[b];
    for(int i=0;i<s;i++){
        cin>>a[i];
    }
    for(int i=0;i<b;i++){
        cin>>dg[i].first>>dg[i].second;
    }
    
    sort(dg,dg+b);
    for(int i=0;i<s;i++){
    int f = lower_bound(dg,dg+b,make_pair(a[i],10000000))-dg; 
    int sum=0;
    for(int j=0;j<f;j++){
    sum+=dg[j].second;
    }
    cout<<sum<<" ";
    }
    
    return 0;
    }

Admin Building

Problem Setter’s Solution:

This question can be solved using concept of trees and depth first search traversal technique.The buildings 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 are given the initial admin building which we can consider as the root of tree.The longest path is the maximum distance from root to a vertex among all vertices. Now we are required to shift the root to the neighbouring vertices with “c” permissions required for each shift such that the difference between length of longest path and permissons required is maximized(which is denoted by ease).

To solve this problem,we first calculate the depth for each vertex.Let for a vertex v its depth be depth[v]. All the values of depth[v] can be calculated by a single depth-first search.

We introduce several auxiliary quantities. Let for vertex v the values down1[v],down2[v] are the two largest distances to the leaves in the subtree of vertex v of the given tree. We will also introduce the value up[v] , the maximum distance to the leaf outside the subtree of the vertex v. The values of down1[v] and down2[v] are easily recalculated by walking up the tree from the bottom and maintaining two maximum distances to the leaves. Let p be the ancestor of the vertex v . Then to recalculate up[v] , we need to go up to p and find the maximum distance to a leaf outside the subtree v . If the leaf farthest from p is in the subtree v , then you will need to take down2[p], otherwise down1[p].

For v , we define the maximum distance to the leaf, as dist[v]=max(down1[v],up[v]) . Now let’s calculate for each vertex v the cost of the tree if v becomes the root. It is not profitable for us to take extra steps, so the cost of operations will be equal to cdepth[v] . Then the cost of the tree will be equal to the value of kdist[v]−c*depth[v] .

It remains to go through all the vertices, take the maximum of the tree values and get an answer. It is easy to see that such a solution works for O(n) .

#include<bits/stdc++.h>

using namespace std;

struct Value {
    long long value = 0;
    int vertex = 0;
};

vector<vector<int>> nei;
vector<vector<int>> depth_vertex;
vector<int> depth;
vector<int> parent;

void dfs(int v, int p = -1, int cnt = 0) {
    depth_vertex[cnt].push_back(v);
    depth[v] = cnt;
    parent[v] = p;
    for (int u : nei[v]) {
        if (u == p) continue;
        dfs(u, v, cnt + 1);
    }
}

void solve() {
    int n, root = 1;
    long long k_wei, cost;
    cin >> n >> k_wei >> cost;

    nei.clear();
    nei.resize(n + 1);
    depth_vertex.clear();
    depth_vertex.resize(n + 1);
    depth.clear();
    depth.resize(n + 1);
    parent.clear();
    parent.resize(n + 1);

    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        nei[u].push_back(v);
        nei[v].push_back(u);
    }

    dfs(root);

    vector<pair<Value, Value>> down(n + 1);

    for (int tin = n; tin >= 0; --tin) {
        for (int v : depth_vertex[tin]) {
            for (int u : nei[v]) {
                if (u == parent[v]) continue;
                if (down[u].first.value + 1 > down[v].first.value) {
                    down[v].first.value = down[u].first.value + 1;
                    down[v].first.vertex = u;
                }
            }
            for (int u : nei[v]) {
                if (u == parent[v] || u == down[v].first.vertex) continue;
                if (down[u].first.value + 1 > down[v].second.value) {
                    down[v].second.value = down[u].first.value + 1;
                }
            }
        }
    }

    vector<long long> up(n + 1, 0);

    for (int tin = 1; tin <= n; ++tin) {
        for (int v : depth_vertex[tin]) {
            int p = parent[v];
            up[v] = up[p] + 1;
            if (down[p].first.vertex == v) {
                up[v] = max(up[v], down[p].second.value + 1);
            } else {
                up[v] = max(up[v], down[p].first.value + 1);
            }
        }
    }

    long long ans = -1e17 ;

    for (int v = 1; v <= n; ++v) {
        ans = max(ans, k_wei * max(up[v], down[v].first.value) - cost *  (long long)(depth[v]));
    }

    cout << ans << endl;

}

int main()
{
   solve();
    return 0;
}

Minimize The Cost

Problem Setter’s Solution:

This question can be solved using graphs and dynaming programming.The buildings can be considered as vertices of graph and roads can be considered as edges. From the question we can see that the graph formed by the buildings and roads has no self loops and no mutiple edges.

Note that in any shortest path, we cannot return to the previous vertex. let us consider that the current vertex is v , the previous vertex is u . The current distance d(v)=d(u)+1 (the shortest distance to vertex v ), let the shortest distance to vertex t be d(t) . Then, if we return to the vertex u , the shortest distance from it to t is d(t)−d(u)=d(t)−d(v)+1 . If we add to the current distance, we get: (d(v)+1)+(d(t)−d(v)+1)=d(t)+2 . Thus, we get a path at least 2 longer than the shortest one. Thus, our answer consists of only simple paths( a simple path is a path in a graph which does not have repeating vertices.)

If the answer consists only of simple paths, then we will simply add vertices to the queue when traversing bfs twice (on the first visit, and on the next visit, when the distance to the vertex is equal to the shortest +1 ). And we will also count the number of ways to get to that vertex. Then we can output the answer as soon as we get to the vertex t the second time for processing. After that we can terminate the loop. The Time Complexity of this approach will be O(n+m) since we only need bfs.

#include <bits/stdc++.h>

using namespace std;


#define sz(v) (int)v.size()
#define eb emplace_back
#define mt make_tuple

const int INF = INT_MAX >> 1;
const int mod = 1e9 + 7;

void csum(int &a,int b) {
    a = (a + b) % mod;
}

int s, t;
vector<int> us;
vector<int> dist;
vector<int> dp[2];
int bfs(vector<vector<int>> &g) {
    queue<tuple<int,int,int>> q;
    q.push(mt(s, 0, 0)); //[v, dist, count]

    int ans = 0, mnd = INF;
    us[s] = 1;
    dp[0][s] = 1;
    dist[s] = 0;
    while(!q.empty()) {
        auto [v,d, x] = q.front(); q.pop();
        
        if (v == t) {
            if (mnd == INF) {
                mnd = d;
            }
            csum(ans, dp[x][v]);
        }
        if (d == mnd + 1) continue;
        for (int p : g[v]) if(d <= dist[p]) {
            dist[p] = min(dist[p], d+1);
            csum(dp[d - dist[p] + 1][p], dp[x][v]);
           
            if(us[p] == 0 || (us[p] == 1 && dist[p] == d)) q.push(mt(p, d+1, us[p]++));
        }
    }
    return ans;
}


void solve() {
    int n,m; cin >> n >> m;
    cin >> s >> t;
    us.resize(n+1);
    dp[0].resize(n+1);
    dp[1].resize(n+1);
    dist.resize(n+1);
    for(int i=0;i<n+1;i++){
        us[i] = dp[0][i] = dp[1][i] = 0;
        dist[i] = INF;
    }

    vector<vector<int>> g(n+1);
    for(int i=0;i<m;i++){
        int a,b; cin >> a >> b;
        g[a].eb(b);
        g[b].eb(a);
    }

    cout << bfs(g) << '\n';
}

int main() 
{
    solve();   
}

Happy Learning!!!