My solution involving prim's algorithm 145857604 gives wrong answer for this problem : 1513D - GCD and MST I understand the Kruskal's algorithm solution mentioned in the editorial, but cannot figure out why prims is failing here.

Problem Statement is something like : We can carry 2 kinds of toys, both have some weight and profit. We want to maximize the profit in a way that the total weight does not exceed the given total capacity. There are infinite amount of both toys.

Constraints : weights, profits of both kind of toys and capacity can have values between [1, 1e9].

I was thinking of a greedy approach to this, where we can maximize the profit / weight ratio but it doesn't always give the optimal answer. Specifically in the case when we have unused space left. Also, linear solution won't fit in the time bounds. I know this is a standard problem, but I always get stuck in them. I'd truly appreciate any help.

UPD : Example : Profit_of_A = 3, Profit_of_B = 5, Weight_of_A = 2, Weight_of_B = 3, Capacity = 10. Answer = 16, as we can carry 2 type B toys and 2 type A toys which gives us the maximum profit.

Problem : 1620C - BA-String My submission : 140259447

Can anyone please point out what am I doing wrong here?

The problem is 1557B - Moamen and k-subarrays. Here is my submission : 135732613

I am using two pointers to greedily count the already sorted sub-arrays of maximum length, and checking if it's less than k, in which case it should return YES otherwise NO.

Also, just wanted to express my gratitude for this platform where you people never hesitate to help noobs like me!

1559E - Mocha and Stars

Tutorial uses mobius function to solve this problem. How can we solve this using DP, as I have seen many people use it in their solutions.

Given a rooted tree having N nodes. Root node is node 1. Each ith node has some value , val[i] associated with it.

For each node i (1<=i<=N) we want to know MEX of the path values from root node to node i.

MEX of an array is smallest positive integer not present in the array, for instance MEX of {1,2,4} is 3

Example : Say we are given tree with 4 nodes. Value of nodes are [1,3,2,8] and we also have parent of each node i (other than node 1 as it is the root node). Parent array is defined as [1,2,2] for this example. It means parent of node 2 is node 1, parent of node 3 is node 2 and parent of node 4 is also node 2.

Node 1 : MEX(1) = 2 Node 2 : MEX(1,3) = 2 Node 3 : MEX(1,3,2) = 4 Node 4 : MEX(1,3,8) = 2 Hence answer is [2,2,4,2]

In worst case total number of Nodes can be upto 10^6 and value of each node can go upto 10^9.

Can anyone tell the optimal way to solve this problem?