Almost Same Codes, One AC ,Other WA for PERCAPTA

help
12

Should we always use double in place of float?

13

This was informative! Thanks!

14

What about this @aneee004 ?

15

depends on the degree of precision you need a code.

in anee004’s code he first stored max ( percapita / population ) in two int values instead of storing their division result in a double or float.

next to compare to ratios of two cities :

insted of doing ( A / P ) == ( A’ / P’ )

he checked for cross product ( A * P’ ) == ( A’ * P )

simple mathematics here.

2 Likes
16

So I’m essentially storing perMax, but instead of storing it as a double, I’m storing the numerator in Amax, and the denominator in Bmax. So at any point the current perMax = Amax/Bmax.

Now to check if per[i] is greater than current maximum, we have to check if (A[i]/B[i]) > perMAx
or,
A[i]/B[i] > AMax/Bmax
or,
A[i] * Bmax > AMax * B[i]!
That’s how my if condition arises.

In the second part, I’m just marking all the nodes which have per = maxPer as ‘1’, for my dfs later.

1 Like
17

Thank You So Much.This was so helpful!!
@aneee004

1 Like
18

Yeah i Understood this.
Thank You So Much @anon41069019

1 Like
19

@aneee004 @anon41069019
If we Ignore the “float” part (because of weak testcases),
Can You Answer My Original Question(the one which started the discussion)?

The main change in the AC Code and WA code is mainly in the DFS Part.

20

Ummm… The dfs change is not really a change. It’s essentially the same thing. The “real” difference between the two submissions is the output format. In the “WA” submission, you have not added a “\n” after printing an.size()! :wink:

1 Like
21

Nice Observation Buddy!
Still Getting WA After printing “\n”
WA Solution-Click Here

22

I am Sure (perhaps) that DFS Part is Correct but Not able to figure out Why i am getting WA. Even The AC code is similar.

One Difference more i want to add,
In AC Code i used visit array int visit[200005]={0};
In WA code i used unordered_map for visit unordered_map<int,int>visit;

But i don’t think that map will lead to WA.

23

You are storing a[i]/b[i] in int. So, this will always give WA. eg 4/5 and 3/5 both are 0. But according to ques only 4/5 should be considered

24

Test Cases are Week Buddy,
Through using int i got AC

25

Can you share that code?

26

Friend,
Just scroll up and reach where the discussion started i have mentioned all links.
:slightly_smiling_face:

27

Your mistake

int d=s.top();
          if(visit[d]==0)
          ans.pb(d+1);
          s.pop();
          visit[d]=1;
2 Likes
28

But its Obvious that it’s not visited through this loop:

for(int j=0;j<adj[d].size();j++)
      {
        if(visit[adj[d][j]]==0 && maxper==per[adj[d][j]])s.push(adj[d][j]);
      }

Becuase this loop controls whether while loop will end or not.
Am i right?

29

Yeah you’re right. If it’s in the stack, it’s not visited.
Although I’m not able to figure out why your WA is not passing.

1 Like
30

See, your code marks visited when value is popped. So, it is possible that, some value was already in stack but it can again be pushed because it is not visited.

1 Like
31

@sebastian You are a Genius,
My WA Code Passed , i just added the if condition
My WA Changed AC code- Click Here

2 Likes