Sunday, November 9, 2014

SRM 636 Div 2 250-pt

Problem
http://community.topcoder.com/stat?c=problem_statement&pm=13480&rd=16079

Note
This is one of the harder 250 point problems i've ran into. Looking at the stats this seems to be the case for others as well; only 67% correct and 195 avg points.

Code
public int count(int[] stones)
{
int stonesPerBucket = getStonePerBucket(stones);

int posActions = 0;
int negActions = 0;

for(int i = 0; i < stones.Length; i++)
{
int xFerAmt = stonesPerBucket - stones[i];
if (xFerAmt % 2 != 0)
return -1;

if(xFerAmt < 0)
negActions += xFerAmt;
else if (xFerAmt > 0)
posActions += xFerAmt;
}

if (posActions + negActions == 0)
return posActions / 2;
else
return -1;

}
public int getStonePerBucket(int[] stones)
{
int sum = 0;
foreach(int i in stones)
sum+=i;

int want = sum / stones.Length;

return want;

}

Analysis
i really overthought this one at first. My initial solution, which failed many cases, looped through and tried to add/substract stones between the buckets. After thinking about it some more I realized this didn't have to be that hard. Just need the difference between the # of stones in each bucket and the required stones per bucket, and the negative differences must balance with the positive balances.

Lesson learned - need to understand the problem statement fully before jumping into the coding. In other words, need to interpret the problem and come up with a design for the solution before jumping into implementing the code.

No comments:

Post a Comment

There was an error in this gadget