#1
  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. #2
  3. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,996
    Rep Power
    481
    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.
    [code]Code tags[/code] are essential for python code and Makefiles!
  4. #3
  5. 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.
  6. #4
  7. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,996
    Rep Power
    481
    Please show a failing lineup for my algorithm. Thank you.
    [code]Code tags[/code] are essential for python code and Makefiles!

IMN logo majestic logo threadwatch logo seochat tools logo