FRUSTRATED!!!! plz someOne Help in HackerEarth's " Telecom Towers" problem?

general
, , , , ,
1

i am getting frustrated with this problem, but not able to find what is going wrong with my approach
PLEASE SOME ONE HELP

problem link:- Telecom Towers

mysolution link in java:-- solution1
mySolution Link for those who dont want to unlock solution solution2

my solution is partially accepted, 8 out 51 test cases were accepted

MyApproach:-##

after seeing editorial i came to know that this problem will be solved using maximum bipartite matching

  1. created a graph which have only those nodes in edges which have distance equal to d
  2. applied bipartite algo, to find max flow, max flow or(total maximum augementing path count will be our answer)
2

Your submission is locked :frowning:
Have to solve that before looking at ur soln…

3

Bro, One more solution link updated… if u don’t want to unlock

4

Your soln fails at -

4 1
0 1
0 2
1 0
2 0

Answer should be 2. You have assumed that graph is a connected component.

Similar Question - http://codeforces.com/contest/687/problem/A (Do try this.)

My failed approach - http://codeforces.com/contest/687/submission/38090506 (Exact same approach as yours).

Click to view

You will need a loop for temp from 0 to n-1 (If 0 based indexing).

I cannot modify your soln to get AC because I understand java less. Due to its similarity with c++ . I found the mistake but cannot add more to it.

Pseudo code -

Click to view

int ans=0;

for(temp=0;temp<n;++temp)

if(visited[temp]==true)
continue;

your current code… Bfs/Dfs with current implementation

find no of 1 and 2 which are marked now.
add minimum of both to answer.

My AC approach-

Click to view

http://codeforces.com/contest/687/submission/38090585 .

2 Likes
5

thankx Brother , u saved me, “dil se dua nikal rhi h tumhare liye”, bhagwan tumhe jaldi jaldi 7 star bna de…
passed all test cases except 1 due to poor bipartite matching algo…
but
“find no of 1 and 2 which are marked now. add minimum of both to answer.” will not work otherwise for every bipartite problem solution will be min of “number of element in both group”

for example:- there are 3 nodes in group 1(marked color 1) named as 1,2,3 and 3 nodes in group2(marked color=2) named as a,b,c…
now connections are as followed:-
1->a,b,c
2->a
3->a
ur answer is min(3,3)=3 but actual is 2

1 Like