someone provide with a approach to solve this problem on spoj:SPOJ.com - Problem BYTEFOOD
@zealfire : I hope you realize that this is a CHALLENGE problem and you are not expected to give an OPTIMAL answer . Any answer as such is correct if it conforms to output format and makes sense . You will get a score based on how good your score was compared to the best score among all competitors . Your normalized score would be your_score / best_score .
If you a simple approach to start with , just go to the closest shop and come back . And print this as output for each test case and you will get some score .
I will attempt this problem over next day or two and let you know of what approach I came up with .
Meanwhile you should not get dejected if it takes time for others to reply to you . After all , we are not paid to answer people here . This is an educational platform but not a e-commerce educational platform to connect coaches to students . However , commenting on your question for the purpose of reviving the thread is perfectly fine 
@zealfire : The naive solution I told has a raw score of 2,572,816 and normalized score of [0.016pts] .
The best score on SPOJ is 168,853,672 .
You might struggle with WA on this question if you dont come back within m minutes or you spend time at a shop when food is not available . You can put checks for that in the naive approach and dont visit any shop at all if your selected shop violates the constraints .
A link to solution int JAVA with naive approach is : CodeChef: Practical coding for everyone .
Will let you know something better in time to come .
@zealfire : An approach of keeping the priority of a shop as ( max_profit_possible_at_shop ) / ( distance_of_shop_from_current_position + distance_of_source&destination ) , gives a score of 131521480
[0.836pts] at Code Chef . You need to keep on adding shops according to max_priority till you can no longer add any shop without violating constraints or you have already all shops .
@zealfire : Taking priority as max_profit_possible_at_shop / ( distance_of_shop_from_current_position + time_spent_at_shop ) and allowing for shopping times of 1 to maxShopTime gives a score of 1.0 on Code Chef .
Link to solution in JAVA : CodeChef: Practical coding for everyone
1 Like
-
Initialize time as 0 , numVisited as 0 , make boolean [] visited for shops and initialize as false
-
while((time< m)&&(numVisited < n)) {
2.1 maxPriority = 0; maxIndex = 0; timeSpent = 0;
2.2 for(int i = 0 ; i < n ; i++) {
2.1.1 see if it possible to go from current position to shop i and return to starting point after spending some time say ‘q’ at the shop . If it is possible see whether the shop has enough food left for it to give you for ‘q’ minutes at the time we may reach the shop . If both things are possible , then set the priority of the shop as a double value = q * bi / ( distance_shop_to_current_pos + q ) .
If the priority is greater than maxPriority then update maxPriority ,timeSpent and maxIndex .
2.2 } (for loop closes )
2.3 If maxPriority > 0 , update time , current position , visited array , numVisited etc . and print the shop number ( which is maxIndex + 1 , since shops are indexed started at 1 ) and timeSpent else break out of while loop .
2.4 } ( while loop closes )
days have passed but still no reply to this question,please someone atleast give a hint.thankx
thanks,but it will be very kind of you if you explain your solution a bit more
because java is not very much understandable to me
@zealfire : I have described the algorithm step by step in a seperate answer since it didn’t fit in the comments . Let me know if you have any doubts .