Religious People

#1

I am not getting the aproach …
what I am trying is greedy …
if temple cost is less than road cost then I return (templeCost*n)

else I perform bfs for each component and count the total roads assuming one temple per component …
Now i m not getting that is it must for a greedy aproach that there needs to be only one temple per component or there can more than one temple …

assuming that we have only one temple … then … that temple is needed to be constructed on which city ? … I thought that it should be on one with max roads emerging from it(basically indegree).

got tle

#2

see, u are to a large extend correct with the approch
i`ll let u through once again

this is correct

then we proceed to the condition when cost of road is less that of temple
firstly we`ll calculate the total no of components, and store no of nodes each indepenent component has in a array / vector

so since each component requires to have ateast 1 temple we build just 1 temple [since it is costly ]in each component.
then suppose if a component has 4 nodes out of it 1 node now has a temple, so we need 3 road mantainence
so
final formula becomes when road cost is less than temple building cost

sum = no of component * cost of temple
+
for( no of component - 1 : in each component )
sum += ( no of component * cost of road repair )

#3

u can use dfs to find no of components
its easier.
also store no of nodes in each connected component since it is used later in the calculation

#4

so is it compulsory that we need to have only one temple ?

#5

yes u see, the if suppose u build two temple then u`ll incur extra (cost of temple - cost of road )
like when u can spend 2 rs why spend 3rs in building the extra temple when having 1 temple can serve the purpose in that connected component, all nodes can access that single temple

#6

and does it matter that which city is getting the temple ?
I mean the no of roads emerging from a city does matter from road connections to be minimum
so I can assume any city to be src … or any specific one (for eg one with the max indegree in a component)

#7

any node can get the temple build on it does not matter, all cities are connected to it through some route

#8

https://ideone.com/bvQQnw … this is my code and cant get where am i going wrong

#9

line 51 bfs(node, visited)-1 * road + temple hona chaiye

#10

nhi hoga … i m counting only the roads required to reach other city … not the total elements a components

#11

code is unavaible ! please use cb ide

#12
#13

Bro
the code would fail
in the following test case

3 1 2 1
1 2
like there are 3 nodes but we are given details about 1 edges connecting 1 ->2 2->1

so there since u are using a map as adjList u cannot given it size equal to no of nodes

hence the no of component being calculated is wrong

refer the below code

#14

i have taken this to consideration also … the components with only one components wont be traversed using my map… so for that i build temple at that cities … which have no road … just refer the for loop just before the return cost statement in my religious people function

#16

BRO sab test cases to correct answer de rahe h !
what have u been asking me since then

#17

wait what … mere nhi de rhe the 4 din se …ab de rhe h !!!

#18

Well I guess it was really a pain for both of us … but ab i dont know how in the world … mera same code chal rha h

#19

Hell Yes.
I was like debugging it since day before yesterday , debugged for 2 hrs yesterday then submitted with little change, all came out well,
then tried submitting ur code directly and it was 100% correct.!

#20

lol… this was one of a kind debugging for me … aint really know what is wrong with hackerblocks

#21

anyways thanks for the efforts

1 Like