Hello cf,

I'm trying to solve this 0/1 Knapsack problem:

We have N items with each item characterized by weight, price and color (white, blue, red or black).

We have to choose 12 items with maximum total price such as the sum of their weights is <= W and the choosed items fullfill these conditions:

• only 1 white item
• between 3 and 5 blue items
• between 3 and 5 red items
• between 1 and 3 black items

I tried this backtracking solution (take or leave current item and continue) wich work fine:

int go(int i, int numW, int numBlue, int numR, int numBlack, int currWeight) {
    if (i == N)
        // checkMin check that we have the minumum number of each colored item
        return (checkMin(numW, numBlue, numR, numBlack) && numW + numBlue + numR + numBlack == 12) ? 0 : -10000; 
    int res = -10000;
    res = max(res, go(i + 1, numW, numBlue, numR, numBlack, currWeight));
    //canAddItem check if we can add current item without exceeding the max Weight and not excedding the max number of each colored item
    if (canAddItem(items[i], numW, numBlue, numR, numBlack, currWeight)) {  
        if (items[i].color.equals("W")) numW++;
        if (items[i].color.equals("Blue")) numBlue++;
        if (items[i].color.equals("R")) numR++;
        if (items[i].color.equals("Black")) numBlack++;
        res = max(res, items[i].value + go(i + 1, numW, numBlue, numR, numBlack, (items[i].weight + currWeight)));
    }
    return res;
}

boolean checkMax(int numW, int numBlue, int numR, int numBlack) {
    return numW <= 1 && numBlue <= 5 && numR <= 5 && numBlack <= 3;
}

boolean checkMin(int numW, int numBlue, int numR, int numBlack) {
    return numW == 1 && numBlue >= 3 && numR >= 3 && numBlack >= 1;
}

boolean canAddItem(Item item, int numW, int numBlue, int numR, int numBlack, int currWeight) {
    if (item.color.equals("W")) numW++;
    if (item.color.equals("Blue")) numBlue++;
    if (item.color.equals("R")) numR++;
    if (item.color.equals("Black")) numBlack++;
    currWeight += item.cost;
    return checkMax(numW, numBlue, numR, numBlack) && currWeight <= W && numW + numDef + numMid + numAtt <= 12;
}

This work fines but with an exponential complexity so I tried to add memoization (caching: dp[i][currWeight][numW][numBlue][numR][numBlack]) but it doesn't work anymore.

Can any body explain why the memoization doesn't work here, or share his personal approach to solve this problem ?

Costraints:

N <= 100 W <= 1000

PS I've seen this problem somewhere before but I don't have a link, can anybody provide a link of a similiar problems ?

Here's a problem I crossed lately:

You have a large String S, and q queries, each query consist of a small string b.

The answer of each query is to find the length of the longest common substring between S and b. ( |S| <= 10^5, |b| <= 100, q <= 100 )

My dp solution to find the length of the largest LCS is O(n*m) per query, but it doesn't seem to pass!

I think will need to do some pre-prcessing of S before starting quering, but I can't find a solution.

Any hint or idea will be appreciated.

I was trying to solve this problem, after submitting my solution I got TLE and I couldn't figure out the problem with my O(n.log(n)) solution, I also checked some accepted solution and most of them are using the same approach?

my submission

UPD

I got accepted by copying someone sort function but I still want to know what's wrong with java.util.Arrays.sort function?

I was checking some solution of this problem, and I didn't understand 2 things, let's look at this solution , first why we loop over k j(0..k), and second why k replaced by j and k-j in each call?

I was trying to solve this problem but i got TLE.

In short terms the problem is :

You are given m queries each contains three integers l,r,x, (l<=x<=r) and you have to fill segment [l,r] with integer x except for the element of indices x, ex. if l=1,r=3 and x=2 segment [l,r] = {2,0,2}.

My solution use an indicator array called nxt to avoid filling the already visited segments and go to the next unvisited item, so this should be done in O(n), however i'm getting a TLE and i can't figure out why.

this is my submission

any help or hint is very appreciated.

Hi everyone.

Lets suppose that we have an array with differents elements, and a function f(x,y) that takes 2 elements from the array and return true or false..

We want to extract all connected components.

Note that if f(x,y) = true and f(y,z) = true then x,y,z are in the same connected component even though f(x,z) = false

My simple solution is to iterate over each pair(x,y) and connect vertex with value x to a vertex with value y if f(x,y) = true , and then extract all connected components.

The complexity of this solution is O(n^2) , However i'm looking for a better solution. Thanks.

UDP I guess i didn't explain well, so here an example :

Lets a be an array : a = { 1 , 4 , 7 , 5 , 9 }

f(1,4)=true , f(1,7)=false , f(1,5)=false , f(1,9)=false f(4,7)=false , f(4,5)=false , f(4,9)=true f(7,5)=true , f(7,9)=false f(5,9)=false

So the answer will be 2 sets ( 1,4,9 ) and (7,5)

Note that f(x,y)=f(y,x)

N=1e5

Hi CF's .

Is there any algorithm that can find the biggest Complete graph inside a graph.

I searched a little but i didn't find any resources , is such algorithm even exist ?

hi CF community. I was trying to solve this problem but i got a TLE.

My backtrack approach use bitmask to mark treasures already taken .

the constraints of the problem are small so i didn't figure out why it gives TLE .

here my commented code .

I'm getting WA in this 449B this is my submission

i implemented the dijkstra's algorithm to find shortest path between the capital and each city , and the result is stored in dist[] .

could anyone point out the problem , or tell me if my idea is wrong ??