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.
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.
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.
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!
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!
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.
@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.
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()!