Do it for FUN | SUMFIのBlog

[Codeforces] Croc Champ 2012 - Round 2 B. Word Cut 2023-03-26|PSCodeforces|Problem Solving-Dynamic Programming-KMP

Croc Champ 2012 - Round 2 B. Word Cut

[LeetCode] Collect Coins in a Tree 2023-03-26|PSLeetCode|Problem Solving-Dynamic Programming-DFS

There exists an undirected and unrooted tree with n nodes indexed from 0 to n - 1. You are given an integer n and a 2D integer array edges of length n - 1, where edges[i] = [ai, bi] indicates that there is an edge between nodes ai and bi in the tree. You are also given an array coins of size n where coins[i] can be either 0 or 1, where 1 indicates the presence of a coin in the vertex i.

Initially, you choose to start at any vertex in the tree. Then, you can perform the following operations any number of times:

Collect all the coins that are at a distance of at most 2 from the current vertex, or

Move to any adjacent vertex in the tree.

Find the minimum number of edges you need to go through to collect all the coins and go back to the initial vertex.

Note that if you pass an edge several times, you need to count it into the answer several times.

[LeetCode] Minimum Operations to Make All Array Elements Equal 2023-03-26|PSLeetCode|Segment Tree-Problem Solving

2602. Minimum Operations to Make All Array Elements Equal

You are given an array nums consisting of positive integers.

You are also given an integer array queries of size m. For the ith query, you want to make all of the elements of nums equal toqueries[i]. You can perform the following operation on the array any number of times:

Increase or decrease an element of the array by 1.

Return an array answer of size m where answer[i] is the minimum number of operations to make all elements of nums equal to queries[i].

Note that after each query the array is reset to its original state.

[LeetCode] Prime Subtraction Operation 2023-03-26|PSLeetCode|Problem Solving-Binary Search-Greedy-Sieve of Eratosthenes

2601. Prime Subtraction Operation

You are given a 0-indexed integer array nums of length n.

You can perform the following operation as many times as you want:

Pick an index i that you haven’t picked before, and pick a prime p strictly less than nums[i], then subtract p from nums[i].

Return true if you can make nums a strictly increasing array using the above operation and false otherwise.

A strictly increasing array is an array whose each element is strictly greater than its preceding element.

[LeetCode] K Items With the Maximum Sum 2023-03-26|PSLeetCode|Problem Solving-Math-Greedy

2600. K Items With the Maximum Sum

There is a bag that consists of items, each item has a number 1, 0, or -1 written on it.

You are given four non-negative integers numOnes, numZeros, numNegOnes, and k.

The bag initially contains:

numOnes items with 1s written on them.

numZeroes items with 0s written on them.

numNegOnes items with -1s written on them.

We want to pick exactly k items among the available items. Return the maximum possible sum of numbers written on the items.