Skip to content
Programmingoneonone
Programmingoneonone
  • Home
  • CS Subjects
    • Internet of Things (IoT)
    • Digital Communication
    • Human Values
  • Programming Tutorials
    • C Programming
    • Data structures and Algorithms
    • 100+ Java Programs
    • 100+ C Programs
  • HackerRank Solutions
    • HackerRank Algorithms Solutions
    • HackerRank C problems solutions
    • HackerRank C++ problems solutions
    • HackerRank Java problems solutions
    • HackerRank Python problems solutions
Programmingoneonone

HackerEarth City and Fireman Vincent problem solution

YASH PAL, 31 July 2024
In this HackerEarth City and Fireman Vincent problem solution Fatland is a town with N cities numbered 1, 2, …, N, connected with 2-way roads. Vincent is a villian who wants to set the entire town ablaze. For each city, there is a certain risk factor E[i] for setting that city ablaze. But once a city c is set ablaze, all cities that can be reached from c will be set ablaze immediately.
The overall risk factor of setting some number of cities ablaze is the sum of the risk factors of setting each of the cities ablaze. Vincent’s goal is to set the whole town ablaze with minimal risk by picking some set of cities to set ablaze. Let M be the minimum risk he takes when setting the entire city ablaze. Calculate the number of ways to pick a set of cities to obtain a risk of M.
HackerEarth City and Fireman Vincent problem solution

HackerEarth City and Fireman Vincent problem solution.

count = 0
best = 10000000000000

g = [[] for _ in range(1005)]

v = [0] * 1005

def dfs(x):
global best
global count
if best == e[x]:
count += 1
if best > e[x]:
best = e[x]
count = 1

v[x] = 1
for i in g[x]:
if v[i] == 0:
dfs(i)

n = int(input())
e = [0]+list(map(int, input().split(' ')))
k = int(input())
for i in range(k):
x, y = map(int, input().split(' '))
g[x].append(y)
g[y].append(x)

ans = 1
for i in range(1, n+1):
best = 10000000000000
count = 0
if (not v[i]):
dfs(i)
ans = ans * count

print(ans%(10**9+7))

Second solution

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int lim = 1e3 + 1;
const int maxn = 1e3;
const int maxk = 1e3;

const int LL mod = 1e9 + 7;

vector<LL> E(lim);
vector<int> parent(lim);

int ancestor(int a)
{
if (a != parent[a])
parent[a] = ancestor(parent[a]);
return parent[a];
}

void merge(int a, int b)
{
a = ancestor(a);
b = ancestor(b);
if (a != b)
parent[a] = b;
}

int main()
{
int n;
scanf("%d", &n);
assert(1 <= n and n <= maxn);
for (int i = 1; i <= n; i++)
scanf("%lld", &E[i]);

for (int i = 1; i <= n; i++)
parent[i] = i;

int k;
scanf("%d", &k);
assert(1 <= k and k <= maxk);
for (int i = 1; i <= k; i++)
{
int city1, city2;
scanf("%d%d", &city1, &city2);
merge(city1, city2);
}
for (int i = 1; i <= n; i++)
parent[i] = ancestor(i);

map<int, multiset<int> > mp;

for (int i = 1; i <= n; i++)
mp[parent[i]].insert(E[i]);

LL ans = 1;

for (auto foo: mp)
{
LL cnt = 1;

int low = *(foo.second.begin());
foo.second.erase(foo.second.begin());

for (auto bar: foo.second)
{
if (bar != low)
break;
cnt++;
}

ans = (ans * cnt) % mod;
}

printf("%lldn", ans);
return 0;
}
coding problems solutions

Post navigation

Previous post
Next post

Pages

  • About US
  • Contact US
  • Privacy Policy

Programing Practice

  • C Programs
  • java Programs

HackerRank Solutions

  • C
  • C++
  • Java
  • Python
  • Algorithm

Other

  • Leetcode Solutions
  • Interview Preparation

Programming Tutorials

  • DSA
  • C

CS Subjects

  • Digital Communication
  • Human Values
  • Internet Of Things
  • YouTube
  • LinkedIn
  • Facebook
  • Pinterest
  • Instagram
©2025 Programmingoneonone | WordPress Theme by SuperbThemes