Next Week Algorithm.Level 500. TopCoder.

[Seabook]

Next week Algorithm. Post here first. Have fun guys.

Problem Statement
????
A city has several different tax schemes. In each scheme, the taxpayer pays a percentage of his income plus a fixed base amount every year. Each citizen is free to choose an optimal tax scheme for his income after the end of each year.
You will be given two int[]s, fixedBase and percent (elements with equal indices describe the same tax scheme). Given an index of a tax scheme, return the minimal non-negative income this scheme is optimal for (choosing any other tax scheme results in a tax which is strictly greater). If this scheme is not optimal for any income, return -1.
Definition
????
Class:
OptimalTax
Method:
optimalIncome
Parameters:
int[], int[], int
Returns:
double
Method signature:
double optimalIncome(int[] fixedBase, int[] percent, int index)
(be sure your method is public)
????

Notes
-
The return value must be within 1e-9 absolute or relative error of the actual result
Constraints
-
fixedBase and percent will contain between 2 and 50 elements, inclusive.
-
fixedBase and percent will contain the same number of elements.
-
Each element of fixedBase will be between 0 and 10000, inclusive.
-
Each element of percent will be between 0 and 100, inclusive.
-
index will be between 0 and number of elements in fixedBase - 1, inclusive.
Examples
0)

????
{10, 5, 3}
{0, 10, 20}
0
Returns: 50.0
The first scheme forces a taxpayer to pay 10 units of tax regardless of income. The second scheme leads to the same tax for an income of 50. The first scheme is optimal for any income greater than that.
1)

????
{6000, 435, 3325, 2345, 0}
{ 0, 45, 33, 13, 100}
3
Returns: 5968.75

2)

????
{1, 0, 0, 0}
{9, 6, 7, 8}
0
Returns: -1.0

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

Thanks,
Seabook

[Seabook]

No guys do this algorithm? Come on, Passion.

Btw, what's the best developing machine you guys think?
For me, 2 monitors is a must, and maybe Mac OS X， I7, 8g Memo,  256g SSD, etc. Of course, I am a Java guy.

[Jeff Huang]

MacOS X.... You don't have too many choose, do you?

[Seabook]

MacOS X integrated with FreeBSD, which is easy to use since Dos Sucks.
And I found MacOS X have almost all the usual softwares and you can do pretty much everything .

Thanks,
Seabook

[Jeff Huang]

Should it be 

{435, 3325, 2345, 0} 

{45, 33, 13, 100} 

3 ?

[Jeff Huang]

package tapp;

import static org.junit.Assert.assertEquals;

import org.junit.Before;

import org.junit.Test;

/**

 * Basically this is a mathematical issue.

 *

 */

public class OptimalTaxTest {

static class Example {

final int[] fixedBase;

final int[] percents;

final int index;

final double result;

public Example(int[] fixedBase, int[] percents, int index, double result) {

super();

this.fixedBase = fixedBase;

this.percents = percents;

this.index = index;

this.result = result;

}

}

Example[] examples = new Example[] {

new Example(

new int[] { 10, 5, 3 }, 

new int[] { 0, 10, 20 }, 

0,

50.0),

new Example(

new int[] { 435, 3325, 2345, 0 }, 

new int[] { 45, 33, 13, 100 }, 

2, 

5968.75),

new Example(

new int[] { 1, 0, 0, 0 }, 

new int[] { 9, 6, 7, 8 }, 

0,

-1.0) };

@Before

public void setUp() {

}

static class OptimalTax {

static double optimalIncome(int[] fixedBase, int[] percents, int index) {

if(percents.length != fixedBase.length)

throw new IllegalArgumentException("size");

int size = fixedBase.length;

if(index<0 || index>=size)

throw new IllegalArgumentException("index");

//compare the gradient

for(int k=0; k<size; ++k) {

if(k == index)

continue;

if(percents[k] <= percents[index])

return -1.0;

}

//find the cross points

double maxCross = -1;

for(int k=0; k<size; ++k) {

if(k == index)

continue;

double cross = 1.0 * 

(fixedBase[k] - fixedBase[index]) 

/ (0.01 * (percents[index] - percents[k]));

if(cross > maxCross)

maxCross = cross;

}

return maxCross;

}

}

@Test

public void testAlgorithm() {

for (Example ex : examples) {

double optimalIncome = OptimalTax.optimalIncome(ex.fixedBase,

ex.percents, ex.index);

assertEquals(ex.result, optimalIncome, 0.0001);

[Seabook]

Thanks for the solution.
I will try to do this tomorrow. I am busy with reinstalling my OS.
 I will post next week's algorithm later.

Thanks,
Seabook

[Seabook]

More like a math, fairly easy.

package com.seabook.google.algorithm;

public class OptimalTax {
   
    public static void main(String[] args) {
        OptimalTax ot = new OptimalTax();
       
        ot.optimalIncome(new int[]{10, 5, 3}, new int[]{0, 10, 20}, 0);
        ot.optimalIncome(new int[]{6000, 435, 3325, 2345, 0}, new int[]{ 0, 45, 33, 13, 100}, 3);
        ot.optimalIncome(new int[]{1, 0, 0, 0}, new int[]{9, 6, 7, 8}, 0);
    }
   
    public double optimalIncome(int[] fixedBase, int[] percent, int index) {
        //TODO basic checks
        // However the problem should avoid some bad params, still prefer to do some simple checks.
       
        int mainBase = fixedBase[index];
        double mainPercent = (percent[index] == 0 ? 0: percent[index]/100.0);
       
        double optimalIncome = -1d;
        double calcValue = 0.0d;
        int tempBase = 0;
        double tempPercent = 0d;
        for (int i = 0; i < fixedBase.length; i ++) {
            if (i == index) {
                continue;
            }
            tempBase = fixedBase[i];
            tempPercent = (percent[i] == 0 ? 0 : percent[i]/100.0);
            double calcBase = (tempBase - mainBase);
            double calcPercent = (mainPercent - tempPercent);
            calcValue  = calcBase / calcPercent;
            if (shouldKeeptheValue(calcBase, calcPercent)) {
                if (calcValue > optimalIncome) {
                    optimalIncome = calcValue;
                }
            }
        }
        System.out.println(optimalIncome);
        return optimalIncome;
    }

    private boolean shouldKeeptheValue(double calcBase, double calcPercent) {
        if (calcPercent < 0 && calcBase < 0) {
            return true;
        }
       
        return false;
    }
}