solution for diet plan problem in codevita
Answers
Next, to be in the top 100, you again require at least a little experience in competitive programming and I assume that you are good enough to at least get a rank in Round-1 and clear it. You must be good with implementation and easy problems at the very least. Try sharpening your skills with standard problems on sites like GeeksforGeeks. CodeVita does not have too high level competitive programming problems like Max Flow, Segment Trees, Bit-masking DP, etc. All you need to do is practice those standard problems from recursion, patterns, pattern matching, dynamic programming, etc. You could improve a bit if you practice implementation category of problems on
Now, if cracking to you, means getting job interview(s) from TCS and just getting a rank regardless of where you are in the standings, I assume that you are not too hands on with competitive programming or even programming in some cases. You can still make it happen. Here is how:
From my experience, most of the problems in codevita lie in following categories:
Maths: Learn the standard topics like Sieve of Eratosthenes, Modular Exponentiation, Prime Factorization, GCD, LCM, Factorials, nCr, nCr modulo m, Modular Inverse, Fibonacci Series, etc.
Fundamental Algorithms: Binary Search (Try as many variations of problems using it as possible), Sorting using comparators &custom data structures, Pattern Matching (Rabin-Karp / KMP / Z-Algorithm), DFS, BFS. If you find a bit more time, proceed to some more graph algorithms like Dijkstra, Kruskal, etc.
Standard Implementation: Matrix Rotation, Array Transformations, Pattern Printing, Pattern Finding, etc. You can try to solve codevita problems from previous years to get an idea of patterns and standard implementation stuff. You can also find a lot of them on the links I mentioned above.
Standard Recursion / Dynamic Programming: Most of the recursion / dynamic programming problems are variations of standard problems like Coin Sum, Subset Sum, Knapsack, Min Cost Path, DFS with memoization, DFS in matrices, mathematical problems that break down into sub-problems that can be solved using recursion, etc.
Data Structures: A lot of problems are standard implementation problems that require basic or sometimes tricky use of Data Structures like Strings, Stacks, Queues, Priority Queues, Sets, HashMaps, Big-Integers etc. The only important point here is to be smart in choosing the language to solve a problem. For example, I always preferred Python in case of problems involving Big-Integers or too many strings as it is often easier. It is totally up to you what language you use but at least learn the use of standard data structures in that language.
These topics will cover almost all problems. Also, I would like to mention that CodeVita used to have a problem that required chess notations in the years prior to 2017. They have most probably been discontinued. But you can spend an hour or two learning about them if you wish.
A few other important tips:
Sit in the practice round, it helps you get the feel of the competition and makes you familiar with the interface.
The competition is 6 hours long. Choose a time slot that suits you best, in the 24 hour window you get in round 1. The time window used to be 3 PM on Day 1 to 3 PM on Day 2. I preferred either solving it late in the night (12 to 6) or early in the morning (7 to 1), the reason being that the servers are very stable by this time and I either felt refreshed in the morning after a good sleep or had my most productive hours at night. Choose the time slot that suits you. I would still suggest not being too early (3 PM Day 1) and neither being too late (8 AM or later on Day 2). Remember that you cannot exceed the 3 PM time on Day 2 and you must start at least 6 hours before it.
When you sit for the competition, have some food around you. It’s a long competition that requires energy. Your mind won’t work if your stomach decides otherwise.
In case you find errors in your code, try debugging and think of corner cases by dry running the solution on paper. Also cross check your optimized solution with brute force solutions. There is sufficient time for it, if you are smart about it. CodeVita is good with corner cases. Submit as many times as you need to but try to solve the problem.
Last, and the most important point.
Answer:
Concept:
The multinational company TCS conducted campaign through Codevita to hire people.
Explanation:
Arnold intends to follow a diet that his nutritionist has recommended. The Nutritionist advised him on the amount of total protein, carbs, and fats he should consume on a daily basis. Arnold conducts an online food shop search and compiles a list of the amount of protein, carbs, and fats in a single unit of various foods.
His goal is to consume as much protein, carbohydrates, and fats as possible while staying under the recommended limits. He also wants to sample as many different foods as possible. That instance, he does not desire a lot of one food item but none of the others. To meet the goal, several combinations of 'units of food products' are feasible. Mathematically, diversity is greater if the difference between the number of units of the most popular food item and the number of units of the least popular food item is as little as feasible.
To solve this problem, he multiplies all of the elements by the largest number of units feasible, ensuring that the total amount of protein, carbs, and fats does not exceed the allowed limit. For example, if overall nutrition is 100P, 130C, and 130F (where P stands for Protein, C for Carbohydrates, and F for Fats), and two separate food products, Item A and Item B, have the following nutritional value:
Item A - 10P, 20C, 30F
Item B - 20P, 30C, 20F
Then he can have (maximum feasible) 2 units of each item because 3 units will exceed the carbohydrate and fat allowance.
He next selects foods to complete the remaining nutrients. He selects one additional unit from the maximum amount of food items available. He repeats this method until he can't add another unit of any food to his diet without going over the authorized limit. He can choose one more unit of item B or one more unit of item A in this case. If he has two sets of meals, the priority is given to meeting the protein, carbohydrate, and fat requirements in that order. As a result, he opts for item B.
You will be given the highest amount of nutrients required as well as nutrients found in various foods. After making his decision using the process outlined above, you must determine the amount of nutrients for which there is a deficiency in comparison to the prescription. In this case, he still needs 20P, 0C, and 10F to meet his goal.
Constraints
Number of Food Items <= 10
Maximum amount of Nutrients is less than 1500 i.e. x +y + z <= 1500
The amount of P, C, and F in two food items will not be the same
P, C, and F values in input can be in any order
The output should be in order - P, C, F
Input
First-line contains the maximum limit of nutrients in the following format.
xP yC zF, where x, y and z are integers
Second-line contains nutrient composition of different food items separated by pipe (|).
Output
Print the shortfall for each nutrient type, fulfilled separated by space.
E.g. If the output is 10P, 20 C, 30 F, then print "10 20 30" (without quotes).
Time Limit
1
Example
Input
100P 130C 130F
10P 20C 30F|20P 30C 20F
Output
20 0 10
Explanation
Having 2 units of item A and 3 units of item B provides - 2 * [10P 20C 30F] + 3 * [20P 30C 20F] = 100P, 130C, 120F. This is the best combination that can reduce the shortfall [20P, 0C, 10F] without exceeding his prescription. In contrast, if 3 units of A and 2 units of B are chosen then 3 * [10P 20C 30F] + 2 * [20P 30C 20F] = 70P, 120C, 130F produces a shortfall of [30P, 10C, 0F]. However, since protein shortfall in this case is more than the previous combination, this is not the right combination to follow.
#SPJ3