Thread: Need Help with the algorithm for this question.

1. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Nov 2013
Posts
3
Rep Power
0

Need Help with the algorithm for this question.

There is a fictional company called fooBar in fooLand. The CEO of fooBar, fooMan, directs all managers to minimize the total hike that they give to employees, while ensuring that the hike is fair to them. Usually, this is done by giving more hike to employees who are rated better. So, for example, if an employee is rated 2 and is given hike 3x, an employee rated 3 should be given a hike greater than 3x. Hikes are always in multiples of x only and the minimum hike to be given to any employee is x.

This year, however, a wicked manager, barMan comes up with a brilliant strategy. He assumes that each employee would get to know the hike of only the two employees who sit next to him (one on the left, one on the right). And therefore, he reasons(using whole of his analytical left brain), that as long as he could make hikes fair for each employee with respect to the two employees that sit next to him, he would fulfill the dual objective of being "fair" as well as minimizing the total hike given. Just for clarification, the employees of each team sit in one big line.

barMan hires you to calculate the hike to be given to each employee. Over to you. You are supposed to come up with the total hike number that will excite barMan and make him roll on the floor laughing. You are given that no two employee sitting next to each other would have a common rating.

Input:

The order of rating of each employee should be in the order in which they sit. First line will be the value of x. The second line will be the number of employees 'n'. The next 'n' lines specify the rating of each employee. Rating can be integers from 1 to 105. (weird, right?)

1 <= n <= 105.
1 <= x <= 104.

Sample input 1:

10
4
1
4
6
2

Output:
70

Why?
If we have the hikes as first employee gets 10, second gets 20, third gets 30 and fourth gets 10, we satisfy all our constraints.
2. Offhand, I'd think the algorithm should assign a salary increase ("raise", or "hike") of 1 to all the local minimums.

Then use successively larger "hikes" until you reach the maximum in each direction.

I think we're not finished yet, because the width of the peak and the order in which you assign "hikes" can violate the rules at the top. I'm fairly certain the algorithm can be simpler than measuring peak heights from each side.
Then again, this procedure might be WRONG!
Code:
```
*   *  <-----visualize mountain profile
*   *
*
1 2 3 2 1  <-----ratings

Assign from left to right.  First step, put 1 at the minimums

*   *  <-----visualize mountain profile
*   1
1
----------

Assign from left to right.  Second step, working upward from first minimum

3   *  <-----visualize mountain profile
2   1
1
----------

Assign from left to right.  Second step, working upward from second minimum

2   2  <-----visualize mountain profile
2   1
1   ^
-----|----

OOPS!  We overwrote a value with a smaller assignment.
Deal with it.```
3. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Nov 2013
Posts
3
Rep Power
0
Sorry, but the above method doesn't work, its correct for suitable cases only.
4. Please show a failing lineup for my algorithm. Thank you.