Almost Same Codes, One AC ,Other WA for PERCAPTA

help
6

It should be (1.5,1.5, 2)

7

my bad updated it.

1 Like
8

I corrected my Solution by taking in account the float values.
But i am getting WA by using Float and getting AC using double

AC code-Click Here
WA Code- Click Here

Can You tell why this happened?

1 Like
9

because double values are way more precise than float.

1 Like
10

As I had mentioned. DO NOT USE FLOAT! You will get precision loss at some point. Never use float. You can do the comparison by taking cross product. Double should also not pass, if there are strong test cases!

2 Likes
11

Can You explain following part of your code:

int Amax = A[0], Bmax = B[0];
	for(int i = 1; i <n; i++)
	{
		if(A[i]*Bmax > Amax*B[i])
		{
			Amax = A[i];
			Bmax = B[i];
		}
	}
	vector<int> ct;
	vis.assign(n, 0);
	for(int i = 0; i < n; i++)
	{
		if(A[i]*Bmax == B[i]*Amax)
		{
			vertices.push_back(i);
			vis[i] = 1;
		}  
	}

I know in the first part you are calculating maximum per capita income but can you please explain(Mathematically) why it works?
Also, Please Explain the second part of the above code.
Thanks in Advance!

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?