C4 Problem - Trouble Understanding the Question maybe?

Hello, I am currently getting a wrong result for [C4 problem][1] (Easy Practice).

I have tried to solve this problem by making a separate frequency array containing the frequency of ingredients, then using this frequency array to count from “a” to “zzzz…z” by using counter array.

I had no problem with test cases given in the problem. However, since I am getting a wrong answer,
I now have doubts about myself actually understanding the question in the beginning.

Specifically, in one part of the question states:

To cook a dish, The Chef can use any of the ingredients which appear on his shelf, but only in the order which they appear on the shelf.

the other part of the question states:

However, The Chef is only interested in choosing the set of ingredients that appear first in a lexicographically ordered list of ingredients which satisfy the protein constraints.

So, the question is this:

  1. what is a test case that I should be worried about in solving this problem?

Specifically, what does it really mean by “using any of the ingredients … only in the order which they appear on the shelf?”

Thank you in advance,

kpark.
[1]: http://www.codechef.com/problems/C4

Here is the code I have tried:

#include <stdio.h>
#include <stdlib.h>

// counter[0] refers to ingredient "a", counter[1] refers to ingredient "b" ...
void addCounter(int *counter, int *freq){
    int i, j;
    counter[0]++;

    for (i = 0; i < 25; i++){
        if (counter[i] > freq[i]){
            counter[i] = 0;
            counter[i + 1] += 1;
        }
    }
    if (counter[25] > freq[25])
        counter[0] = -1;    // checking counter[0] if the result is impossible.
}

int getSum(int *protein, int *counter){
    int sum = 0;
    int i;

    for (i = 0; i < 26; i++){
        sum += protein[i] * counter[i];
    }

    return sum;
}

void getString(char *str, int *counter){
    int i, j, k;
    int pos = 0;
    char c;

    for (i = 0; i < 26; i++){
        k = counter[i];
        c = i + 'a';

        for (j = 0; j < k; j++){
            str[pos++] = c;
        }
    }
}

int main()
{
    int t, k;
    int protein[26] = {0};
    int freq[26];              // For counting all ingredients given on shelf
    int counter[26];           // counting from {0...0} to {freq[0] ... freq[25]}
    char L[1000], str[1000];   // L = ingredients given, str = string to output
    int S, pos;
    char c;

    scanf("%d", &t);

    int i, j;
    for (i = 0; i < t; i++){
        memset(protein, 0, sizeof(int)*26);
        memset(freq, 0, sizeof(int)*26);
        memset(counter, 0, sizeof(int)*26);
        memset(str, '\0', sizeof(char)*1000);
        memset(L, '\0', sizeof(char)*1000);
        pos = 0;

        scanf("%d", &k);
        for (j = 0; j < k; j++){
            scanf("%d", &protein[j]);
        }
        scanf("%s", &L);
        scanf("%d", &S);

        c = L[pos];
        while (c != '\0'){
            freq[c - 'a']++;
            c = L[++pos];
        }

        while(1){
            addCounter(&counter, &freq);
            if (counter[0] == -1){
                printf("IMPOSSIBLE\n");
                break;
            }else if (S == getSum(&protein, &counter)){
                getString(&str, &counter);
                printf("%s\n", str);
                break;
            }
        }

    }

    return 0;
}

You don’t understand task at all :slight_smile: But it’s written pretty complicated.

What task want to say is: You got string L. Erase some letters from it and doesn’t change order of rest, that sum of values of remaining letters is S and resulting string is as smallest (lexicographically) as possible.

For instance input:


1
2 3 2
bab
7 //=S

the correct result is bab because you cannot erase any letter and you cannot change their position.

But for input:


1
2 3 2
bab
5 //=S

is correct answer ab, because you can erase first b. The answer ba (erase last b) has also sum 5, but it’s not lexicographically smallest.

Do you understand task yet?

2 Likes

Ohhhhhhhhhhhhh haha. Thank you, that helped alot. :stuck_out_tongue:

you’re welcome :slight_smile: