Almost Same Codes, One AC ,Other WA for PERCAPTA

I was solving PERCAPTA Problem from this June Cookoff
I am not able to understand why one code is getting AC and other WA although The Logic is same and 90% of code is also same.
I am applying DFS to solve the problem.

Problem- Click Here
AC Code-Click Here
WA Code-Click Here

It will be a great help if anybody figure out what is wrong in the WA Code.
Thank you so much in advance!

I’m not sure how the AC code passed. You are using floored down division because per is an integer datatype. So 3/5 will be stored as 0, but the actual contribution is 0.6.

(This doesn’t mean you have to you float or double for per, as that will cause precision loss).
Check out My Submission for the comparison part.

2 Likes

this show how weak test cases were.

2 Likes

Can You Elaborate?

so average income of any city is ( total per-capita income / population )

take example of three cities.

          per-capita income    population              
city 1:       3                    2
city 2:       6                    4
city 3:       10                  10

there average percapita incomes should be ( 1.5, 1.5, 1 ), you used int to store these values, so you code will read them as ( 1, 1, 1 ). which should have gave you wrong result, but it didn’t.

1 Like

It should be (1.5,1.5, 2)

my bad updated it.

1 Like

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

because double values are way more precise than float.

1 Like

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

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!

Should we always use double in place of float?

This was informative! Thanks!

What about this @aneee004 ?

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

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

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

1 Like

Yeah i Understood this.
Thank You So Much @sirearsh

1 Like

@aneee004 @sirearsh
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.

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