Skip to content
TheChatArchiveThe Chat Archive
o1-mini-2024-09-12· OpenAIAi2 WildChat-4.8M (AI2)

solve this codeforces problem use c++: C. Lazy Narek Time Limit 2 seconds Memory Limit…

  1. User

    solve this codeforces problem use c++:

    C. Lazy Narek

    Time Limit

    2 seconds

    Memory Limit

    256 megabytes

    Problem Description

    Narek is too lazy to create the third problem of this contest. His friend Artur suggests that he should use ChatGPT. ChatGPT creates n problems, each consisting of m letters, so Narek has n strings. To make the problem harder, he combines the problems by selecting some of the n strings (possibly none) and concatenating them without altering their order. His chance of solving the problem is defined as scoren - scorec, where scoren is Narek's score and scorec is ChatGPT's score.

    Narek calculates scoren by examining the selected string (he moves from left to right). He initially searches for the letter "n", followed by "a", "r", "e", and "k". Upon finding all occurrences of these letters, he increments scoren by 5 and resumes searching for "n" again (he doesn't go back, and he just continues from where he left off).

    After Narek finishes, ChatGPT scans through the array and increments scorec by 1 for each letter "n", "a", "r", "e", or "k" that Narek fails to utilize (note that if Narek fails to complete the last occurrence by finding all of the 5 letters, then all of the letters he used are counted in ChatGPT's score scorec, and Narek doesn't get any points if he doesn't finish finding all the 5 letters).

    Narek aims to maximize the value of scoren - scorec by selecting the most optimal subset of the initial strings.

    Input

    In the first line of the input, you're given a single integer t (1 ≤ t ≤ 105), the number of test cases. Then the description of each test case follows.

    In the first line of each test case, you're given two integers n, m (1 ≤ n, m ≤ 103), the number of strings and the length of each string.

    In the next n lines, you're given n strings, each having a length of m. The strings only contain lowercase letters of the English alphabet.

    The sum of values of n ⋅ m over all test cases does not exceed 106.

    Output

    For each test case, output a single integer: the maximal possible value of scoren - scorec.

    Example

    Input: 4 5 2 nn aa rr ee kk 1 5 narek 1 4 nare 5 7 nrrarek nrnekan uuuuuuu ppppppp nkarekz

    Output: 0 5 0 7

    Note

    In the first test case, one of the optimal answers is when Narek doesn't choose any of the strings, so the answer is 0. He can alternatively choose all the strings. In this case, the full string becomes "nnaarreekk". Narek can choose the first appearances of all letters and add 5 to the score. His opponent will add 1 for all second appearances, which will be 5 in total. So the answer will be 5 - 5 = 0.

    In the third test case, the only optimal answer is when Narek doesn't choose the string. Note that if he were to choose the string, he wouldn't be able to find the last letter "k", so his score would stay at 0 instead of becoming 5. Then ChatGPT would add 4 for all of the 4 letters, and the answer would become 0 - 4 = -4.

    In the last test case, Narek needs to choose the first and the last strings. After putting these two next to each other, he gets "nrrareknkarekz". Narek can choose the letters marked with red and add 10 to his score. Since the black colored letters Narek left behind are eligible for the opponent to claim (they are used in the word "narek"), the opponent adds all other letters to the score and gets a score of 3. Therefore, the answer is 10 - 3 = 7.

  2. Assistant

    To solve this problem, we need to determine the maximum possible value of score_n - score_c that Narek can achieve by selectively choosing a subset of given strings. Let's break down the problem and outline the solution approach step-by-step.

    Problem Breakdown

    1. Objective: Maximize the value score_n - score_c, where:

      • score_n: Incremented by 5 for each complete "narek" sequence found in the selected subset of strings.
      • score_c: Incremented by 1 for each 'n', 'a', 'r', 'e', 'k' letter not used in any "narek" sequences.
    2. Constraints:

      • We have up to 10^5 test cases, each with up to 10^3 strings of length 10^3.
      • The sum of n * m across all test cases does not exceed 10^6.

    Solution Approach

    To solve this efficiently:

    1. Dynamic Programming (DP):

      • Define states based on the current progress in finding the "narek" sequence (0 to 4 corresponding to each character in "narek").
      • Use DP to decide whether to include or exclude each string while tracking the maximum score_n - score_c.
    2. Preprocessing:

      • For each string, precompute how it affects the current state. Specifically, determine how many "narek" sequences it can complete (k_delta) and the resulting state (j_final) after processing the string starting from each possible state (0 to 4).
    3. DP Transitions:

      • For each string, compute two options for each state:
        • Option 1: Exclude the string, keeping the current state unchanged.
        • Option 2: Include the string, updating the state and scores accordingly based on k_delta and the number of relevant characters in the string.
    4. Final Calculation:

      • After processing all strings in a test case, the answer is the maximum value across all possible states.

    Implementation

    Here's the complete C++ implementation based on the above approach:

    #include <bits/stdc++.h>
    using namespace std;
    
    typedef long long ll;
    
    // Function to process a string starting from a given state
    pair<int, int> process_string(const string& S, int start_j, const string& target) {
        int j = start_j;
        int k = 0;
        for(char c: S){
            if(c == target[j]){
                j +=1;
                if(j ==5){
                    k +=1;
                    j =0;
                }
            }
        }
        return {k, j};
    }
    
    int main(){
        ios::sync_with_stdio(false);
        cin.tie(0);
        int t;
        cin >> t;
        string target = "narek";
        while(t--){
            int n, m;
            cin >> n >> m;
            vector<string> strings(n);
            for(int i=0;i<n;i++) cin >> strings[i];
            // Precompute for each string:
            // t_S: number of 'n','a','r','e','k' letters
            // for each j=0 to4: k_delta and j_final
            struct StringInfo {
                int t_S;
                pair<int, int> transitions[5];
            };
            vector<StringInfo> infos(n, StringInfo());
            for(int i=0;i<n;i++){
                const string& S = strings[i];
                int t_S =0;
                for(char c:S) if(c == 'n' || c == 'a' || c == 'r' || c == 'e' || c == 'k') t_S++;
                infos[i].t_S = t_S;
                for(int j=0; j<5; j++){
                    infos[i].transitions[j] = process_string(S, j, target);
                }
            }
            // Initialize DP
            // dp[j] = max value for state j
            // States j =0 to4
            const int INF = -1e9;
            vector<int> dp_current(5, INF);
            dp_current[0] = 0;
            // Iterate over strings
            for(int i=0;i<n;i++){
                vector<int> dp_next(5, INF);
                for(int j=0; j<5; j++){
                    if(dp_current[j] == INF) continue;
                    // Option 1: Exclude
                    dp_next[j] = max(dp_next[j], dp_current[j]);
                    // Option 2: Include
                    int k_delta = infos[i].transitions[j].first;
                    int j_final = infos[i].transitions[j].second;
                    int value = dp_current[j] + 10 * k_delta - infos[i].t_S;
                    dp_next[j_final] = max(dp_next[j_final], value);
                }
                dp_current = dp_next;
            }
            // Get the maximum value from dp_current
            int answer = 0;
            for(int j=0; j<5; j++) answer = max(answer, dp_current[j]);
            cout << answer << "\n";
        }
    }
    

    Explanation of the Code

    1. Input Processing:

      • The code begins by reading the number of test cases t.
      • For each test case, it reads n strings of length m.
    2. Preprocessing Each String:

      • For each string, count the number of characters that are part of the "narek" sequence.
      • For each possible state (0 to 4), determine how many "narek" sequences (k_delta) the string can complete and what the final state (j_final) will be after processing the string starting from that state.
    3. Dynamic Programming Setup:

      • Initialize a DP array dp_current where dp_current[j] represents the maximum value of score_n - score_c for state j.
      • Iterate through each string and update the DP states based on whether the string is included or excluded.
    4. DP Transitions:

      • Exclude the String: The state remains the same.
      • Include the String: Update the state based on the transitions computed earlier and adjust the score_n - score_c accordingly.
    5. Final Output:

      • After processing all strings, the answer for each test case is the maximum value across all possible states in the DP array.

    Conclusion

    The above approach efficiently computes the optimal subset of strings for each test case by leveraging dynamic programming and precomputing transitions for each string. This ensures that the solution operates within the provided constraints and handles the large number of test cases effectively.