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

Reach on time 1

Problem Setter’s Solution:

Explanation:

The code starts by including the necessary header for input/output operations and using the namespace std to simplify the use of standard library components without needing to prefix them with std::.

In the main() function, an integer variable x is declared. This variable will store the number of minutes Abhishek left before he was supposed to reach college.

The cin » x; statement is used to read input from the user. It prompts the user to enter a value for x, which represents the minutes Abhishek left early.

The code then enters an if statement to check whether the value of x is less than 30, which is the time it takes Abhishek to reach college.

If the condition x < 30 is true, it means Abhishek left less than 30 minutes early, and he won’t be able to reach college on time. In this case, the code prints “NO” using cout « “NO”;.

If the condition x < 30 is false, it means Abhishek left 30 minutes or more early, and he will be able to reach college on time. In this case, the code prints “YES” using cout « “YES”;.

Finally, the return 0; statement ends the main() function and indicates successful execution of the program.

#include <iostream>
using namespace std;

int main() {
    int x;
    cin >> x;  // Minutes Abhishek left before he was supposed to reach

    if (x < 30)
        cout << "NO";
    else
        cout << "YES";
    return 0;
}

Substring Removal 3

  • Problem Link: Click Here

  • Author: Saurabh

  • Topics Covered: problem tags: string, implementation

Problem Setter’s Solution:

To acquire a new string in which no prefixes are repeated. • First, we see if there are any character we can never remove. • Now, we can observe that, we can’t remove the rightmost occurrence of a letter. • Then, we can remove all the occurrences of the letter except the rightmost occurrence of the letter. • We can store the frequency of all the letters in a map. • Then, we iterate through the whole string and as soon as we find that occurrence of a letter is one or less than one. We break from the loop and print the rest of the string from that position.

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

void prefix(string s)
{
   map<char, int> m;
   int i = 0;
   for (i = 0; i < s.size(); i++)
      m[s[i]]++;
   for (i = 0; i < s.size(); i++)
   {
      if (m[s[i]] <= 1)
      {

         break;
      }
      m[s[i]]--;
   }
   for (; i < s.size(); i++)
      cout << s[i];
   cout << endl;
   return;
}

int main()
{
   
      string s;
      cin >> s;
      prefix(s);
   
}

Complete the Tasks

Problem Setter’s Solution:

It focuses on minimizing the time required to complete tasks using a combination of assigned employees and Peter. It starts by reading the task data for each test case. Task data, representing assigned employee times and Peter’s times, are organized into pairs and sorted based on the assigned times.

The initial iteration calculates the total time needed to complete all tasks using assigned employees. By subtracting Peter’s time from the total, this evaluates the potential time savings if Peter takes on tasks.

Subsequently, another iteration identifies tasks that Peter should handle to optimize completion time. This selection is made based on comparing assigned times and adjusted total time. By considering the tasks with the highest assigned times first, the approach effectively minimizes the total time by assigning Peter tasks that would have taken the longest with assigned employees.

In terms of complexity, the time complexity is primarily driven by the sorting step and is O(n log n), where n is the number of tasks. The space complexity remains O(n) due to the storage required for task data pairs. Additional variables introduced during the process occupy constant space.

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

void solve(){
    	int n;
		cin >> n;
		vector<pair<int, int>> s(n);
		for (auto& i : s)
			cin >> i.first;
		for (auto& i : s)
			cin >> i.second;
 
		sort(s.begin(), s.end());
		long long sum = 0;
		for (auto& i : s)
			sum += i.second;
		long long ans = sum;
		for (auto& i : s) {
			sum -= i.second;
			ans = min(ans, max((long long) i.first, sum));
		}
 
		cout << ans << endl;
}
 
int main() {
	int tests;
	cin >> tests;
	while (tests--) {
	solve();
	}
	return 0;
}

Baldev the destroyer.

Problem Setter’s Solution:

Define the number of portals to cross starting from a room as the portal_length of that room. For each room that hasn’t been visited, we want to find its portal_length. Call the room we are performing dfs from the start. As we perform dfs from the start, keep track of the rooms seen, in order, in the path queue and keep track of steps, the length of the path (which is also the portal_length of the start). When we reach a room that has already been visited (call this room the repeat), add the portal_length of the repeat to the current step count because we would continue to visit all of the rooms that repeat would go on to visit.

Once we have path and steps we can calculate the portal_length of all the rooms in this path. We know the repeat will always be the room at the end of the path, but it may appear elsewhere as well. We can break this down into two cases:

  1. The repeat was visited twice in the current path. The rooms in the path between the two occurrences of the repeat form a cycle.
  2. The repeat only appears at the end of the current path. All of the rooms in the path are not part of a cycle.

For rooms inside a cycle, the repeating room when starting from that room is itself. For all the rooms in the path but outside the cycle, the room that repeats when starting from each room will still be the repeat.

Since the rooms outside the cycle all have paths ending at the repeat, each one’s portal_length is 1 less than the previous’. So, as we iterate through the rooms along the path that are outside the cycle, the portal_length will decrease by 1 each time, starting from the start with a portal_length of steps. Once we get to the cycle, the portal_length of the rooms will all be equal to the portal_length of the repeat, which is the length of the cycle.

#include <iostream>
#include <queue>
using namespace std;
void dfs(int room);

bool visited[200000]{};
int destinations[200000];
int portal_length[200000]{};
queue<int> path;
int steps = 0;

int main() {
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> destinations[i];
		destinations[i]--;
	}
	for (int i = 0; i < n; i++) {
		if (!visited[i]) {
			steps = 0;
			dfs(i);
			int decrement = 1;
			// for each room in current path, calculate portal_length
			while (!path.empty()) {
				// we are in the cycle; all nodes have same portal_length
				if (path.front() == path.back()) { decrement = 0; }
				portal_length[path.front()] = steps;
				steps -= decrement;
				path.pop();
			}
		}
	}
	for (int i = 0; i < n; i++) { cout << portal_length[i] << " "; }
	cout << endl;
	return 0;
}

void dfs(int room) {
	// add room to path
	path.push(room);
	if (visited[room]) {
		// add portal_length of the repeat room to current step count
		steps += portal_length[room];
		return;
	}
	visited[room] = true;
	steps++;
	dfs(destinations[room]);
}

Attack The Warriors

Problem Setter’s Solution:

Let p[A] is the probability for Warrior A from the statement. Its clear to understand that you can describe the state by using pair of integers (A,B), where A is a number of the Warrior with smallest index, B — the second Warrior from the left. It is clear to understand that Warrior with indexes j≥ B will be living. After that we will use bfs on the states (A,B).State (0,1) is always visitable, because it is initial. We will push it in the queue. After that, there are only three transitions from current state (A,B).

  1. (B+1,B+2) — this transition is possible if and only if p[A]>0 and there are some Warrior with index j ≥ B, which has non-zero value p[j]>0.
  2. (A,B+1) — this transition is possible if and only if p[A] > 0 и there are no Warrior with index j ≥ B, which has p[j] = 100.
  3. (B,B+1) — this transition is possible if and only if p[A] ≠ 100 and there are some Warrior with index j ≥ B, which has non-zero value p[j]>0.

After that you are to determine number of states, which has distance from state (0,1) less or equal to k. Also you should be careful, that if there are only one Warrior, that he doesnot attack.

#include <iostream>
#include <queue>
#include <cstring>
#include <cstdio>


using namespace std;

#define pb push_back
#define mp make_pair
#define ft first
#define sc second

typedef pair<int,int> pt;

const int N = 3000 + 50;
int n, k, p[N], d[N][N], sufP[N], sufO[N];

int main() {

	cin >> n >> k;
	for(int i = 0; i < n; i++)
		cin >> p[i];
	queue < pt > q;
  	for(int i = n - 1; i >= 0; i--) {
  	 	if (i + 1 != n) {
  	 	 	sufP[i] = sufP[i + 1];
  	 		sufO[i] = sufO[i + 1];
  	 	}
  	 	sufP[i] += (p[i] > 0);
  	 	sufO[i] += (p[i] == 100);
  	}
  	q.push(mp(0, 1));
	
	d[0][1] = 1;

	int ans = 1;

	while (!q.empty()) {
		pt cur = q.front(); q.pop();

		int A = cur.ft, B = cur.sc;
		                        

		if (A >= n || B >= n || d[A][B] > k)
			continue;	
		            
		if (p[A] > 0 && sufP[B] > 0 && d[B + 1][B + 2] == 0) {
			d[B + 1][B + 2] = d[A][B] + 1;
			ans ++;
			q.push(mp(B + 1, B + 2));
		}

		if (p[A] > 0 && sufO[B] == 0 && d[A][B + 1] == 0) {	
			d[A][B + 1] = d[A][B] + 1;
			ans ++;              
			q.push(mp(A, B + 1));
		}

		if (p[A] != 100 && sufP[B] > 0 && d[B][B + 1] == 0) {
			d[B][B + 1] = d[A][B] + 1;
			ans ++;
			q.push(mp(B, B + 1));
		}
	}

	cout << ans << endl;
}

Happy Learning!!!