Vampire Ba le
Problem Statement: Select minimum blood units to ensure Stephan's power exceeds Damon's
remaining total
int minimalPower(string Mul -Vampire Power Balancing
blood) { #include <bits/stdc++.h>
vector<int> digits; using namespace std;
int total = 0;
for(char c : blood) { vector<int> mul VampirePower(const string& blood, int vampires) {
digits.push_back(c - '0'); vector<int> powers;
total += c - '0'; int total = 0;
} for (char c : blood) {
int val = c - '0';
sort(digits.rbegin(), powers.push_back(val);
digits.rend()); total += val;
int stephan = 0, damon = }
total; sort(powers.rbegin(), powers.rend());
for(int i=0; i<digits.size();
i++) { vector<int> results;
stephan += digits[i]; int start = 0;
damon -= digits[i]; int remaining = total;
if(stephan > damon)
return stephan; for (int v = 0; v < vampires; v++) {
} int currentPower = 0;
return total; while (start < (int)powers.size() && currentPower <= remaining -
} currentPower) {
currentPower += powers[start++];
}
remaining -= currentPower;
results.push_back(currentPower);
}
return results;
}
If side codes not work
#include <bits/stdc++.h>
Email Duplicates
using namespace std;
int countDuplicates(vector<int>& emails) {
int countDuplicatesStream(const vector<int>&
emails) {
unordered_map<int, int> freq;
unordered_map<int, int> freq;
int duplicates = 0;
int duplicates = 0;
for(int id : emails) {
for (int id : emails) {
if(freq[id]++ == 1) duplicates++;
freq[id]++;
if (freq[id] == 2) duplicates++; // Count only
once per duplicate
}
return duplicates;
}
return duplicates;
}
lexicographically largest substring.
string lastLexicoSubstr(string s) { Circular String Lexicographic Last Substring
char max_char =
*max_element(s.begin(), s.end()); #include <bits/stdc++.h>
string res; using namespace std;
for(int i=0; i<s.size(); i++) {
if(s[i] == max_char) { string lastLexicoSubstrCircular(const string& s) {
string candidate = s.substr(i); string doubled = s + s;
if(candidate > res) int n = s.size();
res = candidate; string maxSub = doubled.substr(0, n);
}
} for (int i = 1; i < n; i++) {
return res; string candidate = doubled.substr(i, n);
} if (candidate > maxSub) maxSub = candidate;
}
return maxSub;
}
Coin Game
Problem Statement: Find minimum star ng capital to avoid nega ve balance
int minStar ngCapital(vector<int>& steps) {
int min_balance = 0, current = 0;
for(int step : steps) {
current += step;
min_balance = min(min_balance, current);
}
return max(-min_balance, 0);
}
Mul -Currency Resource Balancing (Extension of Coin Game)
#include <bits/stdc++.h>
using namespace std;
long long minStar ngCapitalMul Currency(const vector<long long>& steps) {
long long minBalance = 0, current = 0;
for (auto step : steps) {
current += step;
minBalance = min(minBalance, current);
}
return max(-minBalance, 0LL);
}
Problem Recap
Given train mings and routes (i.e., a weighted graph), find the most efficient route and travel
me between two sta ons.
OR
A. Find the minimum fare between two sta ons with transfer limits.
B. Modify Dijkstra to handle me-dependent edge weights (e.g., peak/off-peak
mings).
C. Find the fastest route if some routes are temporarily closed (remove edges and
rerun).
#include <iostream>
#include <vector>
#include <queue>
#include <limits>
using namespace std;
typedef pair<int, int> pii; // (cost, node)
vector<int> dijkstra(int n, vector<vector<pii>>& graph, int src) {
vector<int> dist(n, INT_MAX);
priority_queue<pii, vector<pii>, greater<pii>> pq;
dist[src] = 0;
pq.push({0, src});
while (!pq.empty()) {
int cost = pq.top().first;
int u = pq.top().second;
pq.pop();
if (cost > dist[u]) con nue;
for (auto& edge : graph[u]) {
int v = edge.first;
int w = edge.second;
if (dist[v] > dist[u] + w) {
dist[v] = dist[u] + w;
pq.push({dist[v], v});
}
}
}
return dist;
}
// Example usage
int main() {
int n = 5; // number of sta ons
vector<vector<pii>> graph(n);
// Add edges: graph[u].push_back({v, weight});
graph[0].push_back({1, 10});
graph[0].push_back({2, 5});
graph[1].push_back({2, 2});
graph[1].push_back({3, 1});
graph[2].push_back({1, 3});
graph[2].push_back({3, 9});
graph[2].push_back({4, 2});
graph[3].push_back({4, 4});
graph[4].push_back({3, 6});
graph[4].push_back({0, 7});
int src = 0, dest = 4;
vector<int> dist = dijkstra(n, graph, src);
cout << "Shortest me from " << src << " to " << dest << " is " << dist[dest] << endl;
return 0;
}
------------------------------------------------------------------------------------------------------------------------------
Problem Recap
If 5 rickshaws serve 20 passengers per hour each, how many rickshaws are needed to serve
200 passengers in 2 hours?
#include <iostream>
#include <cmath>
using namespace std;
int main() {
int passengers = 200, hours = 2, perRickshawPerHour = 20;
int perRickshawTotal = perRickshawPerHour * hours;
int rickshaws = (passengers + perRickshawTotal - 1) / perRickshawTotal; // ceil division
cout << "Rickshaws needed: " << rickshaws << endl;
return 0;
}
Problem Recap
A number has digits in the ra o 2:3:4. If the sum of its digits is 81, what is the number?
#include <iostream>
using namespace std;
int main() {
int sum = 81;
int x = sum / 9;
int d1 = 2 * x, d2 = 3 * x, d3 = 4 * x;
cout << "The number is: " << d1 << d2 << d3 << endl; // Concatena on
return 0;
}
Problem:
Find the shortest path between two sta ons but with a maximum allowed number of
transfers (edges).
#include <bits/stdc++.h>
using namespace std;
struct State {
int node, dist, transfers;
};
int shortestPathWithMaxTransfers(int n, vector<vector<pair<int,int>>>& graph, int src, int dest,
int maxTransfers) {
vector<vector<int>> dist(n, vector<int>(maxTransfers+1, INT_MAX));
dist[src][0] = 0;
queue<State> q;
q.push({src, 0, 0});
while(!q.empty()) {
auto [u, d, t] = q.front(); q.pop();
if (u == dest) return d;
if (t == maxTransfers) con nue; // cannot transfer more
for (auto& [v, w] : graph[u]) {
if (dist[v][t+1] > d + w) {
dist[v][t+1] = d + w;
q.push({v, dist[v][t+1], t+1});
}
}
}
return -1; // no path found
}
OR
Shortest Mee ng Point Between Two Nodes
Given:
A directed or undirected graph represented as adjacency lists.
Two start nodes start1 and start2.
Goal:
Find the node in the graph that both nodes can reach such that the maximum of the two
distances (from start1 and start2) to this node is minimized. If mul ple nodes qualify, return the
one with the smallest index.
#include <bits/stdc++.h>
using namespace std;
// BFS to find shortest distances from a start node
vector<int> bfs(int start, const vector<vector<int>>& graph) {
int n = graph.size();
vector<int> dist(n, INT_MAX);
queue<int> q;
dist[start] = 0;
q.push(start);
while (!q.empty()) {
int u = q.front(); q.pop();
for (int v : graph[u]) {
if (dist[v] == INT_MAX) {
dist[v] = dist[u] + 1;
q.push(v);
}
}
}
return dist;
}
int shortestMee ngNode(int start1, int start2, const vector<vector<int>>& graph) {
vector<int> dist1 = bfs(start1, graph);
vector<int> dist2 = bfs(start2, graph);
int n = graph.size();
int minDist = INT_MAX;
int mee ngNode = -1;
for (int i = 0; i < n; i++) {
if (dist1[i] != INT_MAX && dist2[i] != INT_MAX) {
int maxDist = max(dist1[i], dist2[i]);
if (maxDist < minDist) {
minDist = maxDist;
mee ngNode = i;
}
}
}
return mee ngNode;
}
2. Detect Cycle in Directed Graph (Train Routes with Circular Dependencies)
Problem:
Given train routes as directed edges, detect if there is a cycle (which may represent scheduling
conflicts).
bool dfs(int u, vector<vector<int>>& graph, vector<bool>& visited, vector<bool>& recStack) {
visited[u] = true;
recStack[u] = true;
for (int v : graph[u]) {
if (!visited[v] && dfs(v, graph, visited, recStack)) return true;
else if (recStack[v]) return true;
}
recStack[u] = false;
return false;
}
bool hasCycle(int n, vector<vector<int>>& graph) {
vector<bool> visited(n, false), recStack(n, false);
for (int i = 0; i < n; i++) {
if (!visited[i] && dfs(i, graph, visited, recStack)) return true;
}
return false;
}
3. Number of Connected Components (Zones of Sta ons)
Problem:
Find how many disconnected zones (connected components) exist in the train network.
int countComponents(int n, vector<vector<int>>& graph) {
vector<bool> visited(n, false);
int count = 0;
for (int i=0; i<n; i++) {
if (!visited[i]) {
count++;
queue<int> q; q.push(i);
visited[i] = true;
while (!q.empty()) {
int u = q.front(); q.pop();
for (int v : graph[u]) {
if (!visited[v]) {
visited[v] = true;
q.push(v);
}
}
}
}
}
return count;
}
4. Minimum Spanning Tree (MST) of the Train Network
Problem:
Find the minimum total cost to connect all sta ons (e.g., laying new tracks).
int primMST(int n, vector<vector<pair<int,int>>>& graph) {
vector<int> key(n, INT_MAX);
vector<bool> inMST(n, false);
key[0] = 0;
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
pq.push({0,0});
int total = 0;
while(!pq.empty()) {
int u = pq.top().second;
int w = pq.top().first;
pq.pop();
if (inMST[u]) con nue;
inMST[u] = true;
total += w;
for (auto& [v, weight] : graph[u]) {
if (!inMST[v] && key[v] > weight) {
key[v] = weight;
pq.push({weight, v});
}
}
}
return total;
}
5. Shortest Path in Weighted Graph with Nega ve Edges (No Nega ve Cycles)
Problem:
Find shortest paths in a graph where some edges may have nega ve weights (e.g., delays or
penal es).
bool bellmanFord(int n, vector<tuple<int,int,int>>& edges, int src, vector<int>& dist) {
dist.assign(n, INT_MAX);
dist[src] = 0;
for (int i=0; i<n-1; i++) {
for (auto& [u,v,w] : edges) {
if (dist[u] != INT_MAX && dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
}
}
}
// Check nega ve cycle
for (auto& [u,v,w] : edges) {
if (dist[u] != INT_MAX && dist[u] + w < dist[v]) {
return false; // nega ve cycle detected
}
}
return true;
}
Problem Statement - Maximum Weight Node
Given a directed graph and a star ng node, find the maximum weight among all nodes
reachable from the start.
#include <bits/stdc++.h>
using namespace std;
int maxWeightNode(int start, vector<int>& weights, vector<vector<int>>& adj) {
int n = weights.size();
vector<bool> visited(n, false);
queue<int> q;
q.push(start);
visited[start] = true;
int maxWeight = weights[start];
while (!q.empty()) {
int u = q.front(); q.pop();
for (int v : adj[u]) {
if (!visited[v]) {
visited[v] = true;
maxWeight = max(maxWeight, weights[v]);
q.push(v);
}
}
}
return maxWeight;
}
Problem Statement - Largest Sum Cycle
Given a directed graph where each node has a weight, find the cycle with the largest sum of
node weights. If no cycle exists, return -1.
#include <bits/stdc++.h>
using namespace std;
int maxCycleSum = -1;
void dfs(int u, vector<vector<int>>& adj, vector<int>& weights, vector<bool>& visited,
vector<bool>& inStack, vector<int>& path) {
visited[u] = true;
inStack[u] = true;
path.push_back(u);
for (int v : adj[u]) {
if (!visited[v]) {
dfs(v, adj, weights, visited, inStack, path);
} else if (inStack[v]) {
// Cycle detected: sum weights in the cycle
int sum = 0;
for (auto it = path.rbegin(); it != path.rend(); ++it) {
sum += weights[*it];
if (*it == v) break;
}
maxCycleSum = max(maxCycleSum, sum);
}
}
inStack[u] = false;
path.pop_back();
}
int largestSumCycle(int n, vector<int>& weights, vector<vector<int>>& adj) {
vector<bool> visited(n, false), inStack(n, false);
vector<int> path;
maxCycleSum = -1;
for (int i = 0; i < n; ++i) {
if (!visited[i])
dfs(i, adj, weights, visited, inStack, path);
}
return maxCycleSum;
}
Nearest Mee ng Cell
Problem Statement
Given a directed graph and two star ng nodes, find the node that both can reach with the
minimal maximum distance from either start node. If there are mul ple, return the one with
the smallest index.
#include <bits/stdc++.h>
using namespace std;
vector<int> bfs(int start, vector<vector<int>>& adj) {
int n = adj.size();
vector<int> dist(n, INT_MAX);
queue<int> q;
q.push(start);
dist[start] = 0;
while (!q.empty()) {
int u = q.front(); q.pop();
for (int v : adj[u]) {
if (dist[v] == INT_MAX) {
dist[v] = dist[u] + 1;
q.push(v);
}
}
}
return dist;
}
int nearestMee ngCell(int start1, int start2, vector<vector<int>>& adj) {
vector<int> dist1 = bfs(start1, adj);
vector<int> dist2 = bfs(start2, adj);
int n = adj.size();
int minDist = INT_MAX, node = -1;
for (int i = 0; i < n; ++i) {
if (dist1[i] != INT_MAX && dist2[i] != INT_MAX) {
int d = max(dist1[i], dist2[i]);
if (d < minDist) {
minDist = d;
node = i;
}
}
}
return node;
}
DSA Solu on: Maximum Input Point (Farthest Common Reachable Node)
#include <bits/stdc++.h>
using namespace std;
vector<int> bfs(int start, const vector<vector<int>>& graph) {
int n = graph.size();
vector<int> dist(n, INT_MAX);
queue<int> q;
dist[start] = 0;
q.push(start);
while (!q.empty()) {
int u = q.front(); q.pop();
for (int v : graph[u]) {
if (dist[v] == INT_MAX) {
dist[v] = dist[u] + 1;
q.push(v);
}
}
}
return dist;
}
int farthestMee ngNode(int start1, int start2, const vector<vector<int>>& graph) {
vector<int> dist1 = bfs(start1, graph);
vector<int> dist2 = bfs(start2, graph);
int n = graph.size();
int maxMinDist = -1;
int node = -1;
for (int i = 0; i < n; ++i) {
if (dist1[i] != INT_MAX && dist2[i] != INT_MAX) {
int minDist = min(dist1[i], dist2[i]);
if (minDist > maxMinDist) {
maxMinDist = minDist;
node = i;
}
}
}
return node; // -1 if no such node exists
}
