Akash Jadhav

Posted on Nov 28

Private

1> Medium To Hard (Graph-Based DP with memoization)
Problem Description

Frankenstein, the alchemist, is on a quest to brew the elixir of life. In his attempts, he combines various ingredients and potions, but he has yet to succeed. Every time he brews something, he meticulously notes down the ingredients and their combinations.

For instance, when he combines "snakefangs" and "wolfbane", he discovers the "awakening" potion, and he records the recipe as:

awakening = snakefangs + wolfbane

Similarly, when three ingredients are required, he notes the recipe as:

thunderstorm = rain + wind + lightning

In general, the recipe would follow this format:

Potion 1 = Ingredient 1 + Ingredient 2
Potion 2 = Ingredient 1 + Ingredient 2 + Ingredient 3
Potion 3 = Ingredient 1 + Ingredient 2 + Ingredient 3 + Ingredient 4
and so on...

Each recipe requires magical orbs to brew. The number of magical orbs needed is equal to the number of ingredients minus one. If a potion is made from several ingredients, the total magical orbs required are the sum of orbs required for each ingredient.

An ingredient can either be an item or a potion. Items are already available, while potions are brewed from ingredients, possibly other potions. In his notes, Frankenstein always lists the result as a potion.

The problem is that sometimes the same potion can be brewed with different recipes, some requiring fewer magical orbs. Given a potion and Frankenstein's notes, you need to determine the minimum number of magical orbs required to brew that potion.

Constraints:

(0 < N < 20) (N is the number of recipes)

Input:

The first line contains an integer (N) representing the number of recipes.
The next (N) lines contain strings representing the recipes in the format: PotionName=Ingredient1+Ingredient2+...+IngredientN.
The last line contains the name of the potion that Frankenstein needs to brew.

Output:

Print a single integer representing the minimum number of magical orbs required to brew the given potion.

Examples:

Example 1:

Input:

4
awakening=snakefangs+wolfbane
veritaserum=snakefangs+awakening
dragontonic=snakefangs+velarin
dragontonic=awakening+veritaserum
dragontonic

Output:

Explanation:
In this example, there are two ways to brew dragontonic:

dragontonic = awakening + veritaserum:
- Brewing awakening requires 1 orb, and brewing veritaserum requires 1 orb.
- Total orbs required = 1 + 1 = 2 orbs.
dragontonic = snakefangs + velarin:
- Brewing snakefangs and velarin requires no orbs, as they are both ingredients.
- Total orbs required = 1 orb.

Thus, the minimum orbs required is 1.

Example 2:

Input:

6
oculus=thunderbrew+jellfish
felix=thunderbrew+pumpkin
wigenweld=thunderbrew+ladybug
wigenweld=oculus+felix
thunderbrew=pumpkin+firefly
maxima=pumpkin+ladybug
wigenweld

Output:

Explanation:
To brew wigenweld with the minimum number of magical orbs:

First, brew thunderbrew, which requires 1 orb.
Then, brew wigenweld using thunderbrew + ladybug, requiring 1 more orb.

Thus, the total orbs required is 2.

Answer

import java.util.*;
public class PotionBrewer {

    private static Map<String, List<List<String>>> potionRecipes = new HashMap<>();
    private static Map<String, Integer> potionMemo = new HashMap<>();

    public static void main(String[] args) {
        Scanner inputScanner = new Scanner(System.in);
        int recipeCount = inputScanner.nextInt();
        inputScanner.nextLine(); // Consume the newline

        for (int i = 0; i < recipeCount; i++) {
            String recipeLine = inputScanner.nextLine();
            String[] potionParts = recipeLine.split("=");
            String resultingPotion = potionParts[0];
            String[] requiredIngredients = potionParts[1].split("\\+");

            potionRecipes.putIfAbsent(resultingPotion, new ArrayList<>());
            potionRecipes.get(resultingPotion).add(Arrays.asList(requiredIngredients));
        }

        String targetPotion = inputScanner.nextLine();
        inputScanner.close();

        int minimumOrbs = calculateMinimumOrbs(targetPotion);
        System.out.print(minimumOrbs);
    }

    private static int calculateMinimumOrbs(String potion) {
        if (!potionRecipes.containsKey(potion)) {
            return 0; // Base ingredient requires no orbs
        }

        if (potionMemo.containsKey(potion)) {
            return potionMemo.get(potion);
        }

        int minimumOrbsRequired = Integer.MAX_VALUE;

        for (List<String> recipe : potionRecipes.get(potion)) {
            int currentOrbsRequired = recipe.size() - 1; // Orbs required for this recipe
            for (String ingredient : recipe) {
                currentOrbsRequired += calculateMinimumOrbs(ingredient); // Add orbs for sub-ingredients
            }
            minimumOrbsRequired = Math.min(minimumOrbsRequired, currentOrbsRequired);
        }

        potionMemo.put(potion, minimumOrbsRequired);
        return minimumOrbsRequired;
    };
};

2> Easy To Medium (Greedy/string)

Here's a clean version of the problem statement:

Problem: JustifyWords

Problem Description:

Given a list of K words and two integers N and M, you are tasked with arranging the words into N lines following these rules:

Each line can contain no more than M characters.
Each word should appear entirely on one line.
If multiple words are on a line, they should be separated by a single space.

The goal is to determine the maximum number of words that can be arranged within the N lines of length M.

Constraints:

(0 < K < 25)
(0 < N < 10)
(0 < M < 10)
Words will contain only lowercase alphabets.

Input:

The first line consists of an integer K, representing the total number of words.
The next K lines each consist of one word.
The last line consists of two space-separated integers N and M, representing the number of lines and the maximum number of characters per line, respectively.

Output:

Print a single integer denoting the maximum number of words that can be arranged into the N lines.

Time Limit: 1 second

Examples:

Example 1:

Input:

8
i
hello
how
going
u
whatsapp
help
hmm
5 5

Output:

Explanation:

We have 8 words to arrange in 5 lines, each having a maximum of 5 characters.

One way to arrange the words to fit the maximum number of words is:

how_i
going
u_hmm
help_
hello_

Here, 7 words can be fitted. There could be other valid combinations, but we are interested in the maximum number of words that can be accommodated.

Example 2:

Input:

6
a
is
b
be
it
a
5 4

Output:

Explanation:

We have 6 words to arrange in 5 lines, each with a maximum of 4 characters. One possible arrangement is:

a_is
b_be
it_a
____

Here, all 6 words can fit, and that is the maximum possible arrangement.

3> Hard (Graph)
BusCount

Problem Description

As the Transportation In-Charge of a reputed company, your responsibility is to ensure that buses are available for every employee and that they arrive on time.

Since pandemic restrictions have been lifted, but not completely, the number of people allowed on buses is still limited. Employees have started visiting the office regularly.

You are given an M x M matrix, which represents the distance between each location. The value in the i-th row and j-th column represents the distance between the i-th place and the j-th place. Assume that all locations are connected by roads and that the first location is the office. The distance between the i-th place and the j-th place is the same as the distance between the j-th place and the i-th place. The top-left element of this matrix (0, 0) is the office location.

The number of people boarding the bus at each location is known a priori and is part of the input.

Given the number of people that a bus can accommodate at one time (post restrictions), determine the number of buses required to pick up all employees. A bus can start from any location but must take only the shortest path from that location to the office. The bus can pick up employees at locations along its route. Assume that there is only one shortest route between the office and each remaining location.

Constraints

( 1 < M < 12 )
( 0 \leq \text{Distance between locations} \leq 300 )
( 0 \leq \text{Total number of employees} \leq 500 )

Input

First line consists of a single integer ( M ), representing the number of locations including the office.
Next ( M ) lines consist of ( M ) integers separated by space, representing the distance matrix.
Next line consists of ( M-1 ) space-separated integers, representing the number of employees boarding at each corresponding location.
Last line consists of an integer representing the number of people that can travel in the bus at one time.

Output

Print a single integer representing the minimum number of buses required to pick up all employees.

Time Limit (secs)

1

Examples

Example 1

Input

Output

Explanation

The below diagram represents the above input.

Based on the input, there are four locations, which we can denote as 0, 1, 2, and 3. The first location is the office, represented as (0).

The shortest paths between each location and the office are:

Location 1 → Office
Location 2 → Office
Location 3 → Location 2 → Office

The number of buses required will be 4:

One bus from Location 1
Two buses from Location 2
One bus from Location 3

The two buses start from Location 2. One bus picks up a full load from Location 2 and heads to the office, and the remaining two people board the bus coming from Location 3.

Example 2

Input

5  
0 10 10 60 60  
10 0 30 10 10  
10 30 0 30 30  
60 10 30 0 30  
60 10 30 30 0  
15 15 15 15  
25

Output

Explanation

For this example, the following diagram (not shown) would depict only the shortest path from each location to the office. Three buses will originate from locations 2, 3, and 4 respectively. The buses starting from locations 3 and 4 will need to travel through location 1. Since they have enough seats to pick up the employees from location 1, three buses are sufficient. Therefore, the output is 3.

4> Medium (2d Matrix)

Block Extraction

Problem Description

Aarya is playing with LEGO bricks, each a one-unit square. She connects the bricks to form various shapes, creating what is known as a block. Thus, a block is an amalgamation of bricks in four possible directions: top, bottom, left, and right.

Each such block she created is assigned a unique identity number. Using the blocks she created, Aarya assembled a matrix with dimensions ( N \times M ). This matrix is positioned upright on the ground. Now, Aarya wants to pick up the block numbered ( K ) from the matrix, starting from the top. The rules to pick up the desired block are as follows:

A block can be easily removed only if there are no other blocks on top of it.
It is guaranteed that there are no empty spaces within the matrix.
If block ( K ) is partially inside block ( L ) and can't be picked directly from the top, she will need to remove block ( L ).

A careful look at the matrix tells us that apart from block ( K ), all other blocks will need to be removed to pick block ( K ).

To collect a block, we need to understand it as collecting all blocks with the same identity. A block numbered ( K ) may span across multiple rows. To pick up all blocks with identity ( K ), Aarya needs to remove all blocks stacked above any occurrence of ( K ).

Input:

The first line consists of two space-separated integers, denoting ( N ) and ( M ) (the number of rows and columns of the matrix).
The next ( N ) lines consist of ( M ) space-separated integers denoting the front view of the matrix assembled by Aarya.
The last line consists of an integer ( K ), denoting the identity number of the block which Aarya wants to pick up, from the top of the matrix.

Output:

Print a single integer denoting the number of blocks she needs to remove to pick up the block with identity ( K ).

Examples

Example 1:

Input:

Output:

Explanation:

The matrix is 5 rows and 5 columns.
It is composed of blocks with identities 1, 2, 3, 4, 5, 6, 7, 8, and 9.
Aarya wishes to collect all blocks with identity 1. Block 1 spans across 3 rows (rows 3, 4, and 5).
To collect block 1, we must remove all blocks stacked above it.
The blocks to be removed are 2, 3, 4, 5, 7, 8, and 9, resulting in 7 blocks being removed.

Example 2:

Input:

Output:

Explanation:

The matrix is 6 rows and 3 columns, composed of blocks with identities 1, 2, 3, 4, 5, 6, and 7.
Aarya wishes to collect all blocks with identity 6. Block 6 appears in row 5.
To collect block 6, we must remove all blocks stacked above it. These are blocks 1, 2, and 3.
Therefore, the number of blocks to be removed is 3.

Example 3:

Input:

4 6
1 1 6 6 6 7
2 3 3 3 8 3
3 3 5 3 3 3
4 9 9 14 14 14
5

Output:

Explanation:

The matrix is 4 rows and 6 columns.
It is composed of blocks with identities 1, 2, 3, 5, 6, 7, 8, 9, and 14.
Aarya wishes to collect all blocks with identity 5. Block 5 appears in the third row.
To collect block 5, we must remove all the blocks stacked above it. These are blocks numbered 1, 2, 3, 6, 7, and 8.
Therefore, the number of blocks to be removed is 6.

Constraints:

( 0 \leq ) number of blocks ( \leq 500 )
( 1 \leq N, M \leq 50 )
A block will never be fully enclosed by another block, meaning it won't be surrounded on all four sides.

This concludes the complete problem statement with three examples. Let me know if anything else is required!

DEV Community

Private

Answer

Problem: JustifyWords

1

Block Extraction

Examples

Example 1:

Example 2:

Example 3:

Constraints:

Top comments (0)

Read next

CSS NEW LOGO BACKSTORY

Was This Text written by a Human? We asked Real Humans (Part I)

What Most People Get Wrong About the Term SSR

🚀 Java: Versatile and Platform-Independent Language