Day 29 | Education Round 135 C and D | C++

Continuing the up-solving contest we started yesterday, we will be solving problems C and D today.

Digital Logarithm

This is quite a fun problem. I loved this problem.

One thing is simple, we will be needing a function that counts the digit in numbers.

Let's call this function dig_count and define it like this

int dig_count(int x){
    int cnt = 0;
    while(x){
        cnt++;
        x /= 10;
    }
    return cnt;
}

Some cool observations

1. A[i] and B[i] < 10^9 This means even the biggest number taken will be 9 digits long

2. Everything diverges to 1 Any number will be at max nine digits long So it will be like x < 10^9 dig_count(x) <= 9 dig_count(dig_count(x)) = 1

3. So the answer will at max be 4*n (2 steps for all the numbers to become 1) This is some observation, not useful in finding an answer though.

Greedily the best option is to do the following -

1. Match as much as we can without changing anything

2. Now if a number > 9 is not matched, then it cannot be ever matched without changing because anything after being operated on will be less than or equal to 9. So we will be changing all numbers > 9

3. We try matching as much as we can again.

4. Now if a number > 1 is not matched, then it cannot be ever matched without changing because anything after being operated on will now be equal to 1. So we will be changing all numbers > 1

5. No need to do anything now, as everything 1 now

Implementation

Step 1 - Matching as much as we can Note - I am using multiset to store data, as deletion takes O(log(n)) time

void delete_matching(multiset<int> &a, multiset<int> &b){
    for(auto it = a.begin(); it != a.end();){
        auto it_b = b.find(*it);
        if(it_b == b.end())it++;
        else{
            b.erase(it_b);
            // a.erase(iterator) returns next iterator since C++11
            it = a.erase(it);
        }
    }
}

Step 2 - Apply operation on values greater than 9 I wrote the method to pass value ( 9 here) so it could be used for 1 as well

int apply_operations_on_value_greater_than_x(multiset<int> &s, int x){
    int conversions = 0;
    multiset<int> temp;
    for(int i: s){
        if(i > x){
            temp.insert(dig_count(i));
            conversions++;
        }
        else 
            temp.insert(i);
    }
    s = temp;
    return conversions;
}

Step 3 - Combine everything

void solve(){
    int n, ans = 0;
    cin >> n;
    multiset<int> a,b;
    for(int i = 0; i < n; i++){
        int x;
        cin >> x;
        a.insert(x);
    }
    for(int i = 0; i < n; i++){
        int x;
        cin >> x;
        b.insert(x);
    }
    //Erase without modification
    delete_matching(a,b);
    ans += apply_operations_on_value_greater_than_x(a,9);
    ans += apply_operations_on_value_greater_than_x(b,9);
    delete_matching(a,b);
    ans += apply_operations_on_value_greater_than_x(a,1);
    ans += apply_operations_on_value_greater_than_x(b,1);
    cout << ans << "\n";
}

You can find my submission here - Submission Link

Letter Picking

This is a good problem, implementing it can be a little annoying (at least the way I did) LOL

Btw, the Lexicographical order is similar to the alphabetical order of the strings.

Check character by character from left, if you find a character smaller than another, then the string with a first character is different, and smaller is lexicographically smaller. If the string ends but doesn't have a different character, then a smaller string is compared by length Otherwise, both strings must be equal.

Notice that we choose the last character of the string, thus later steps matter more than the current step. In fact current step where we are choosing character only matters if it will be drawn from further steps.

Let's have a function that tells whether the player who is making the next move on the string will win or lose.

int best_value(string &s, int start, int end, char prev);

start and end are variables that tell the part of the string we are performing on. Let me explain in detail.

Initially, Alice has a choice to choose starting or ending character in string s[0:n - 1] if Alice chooses the 0th character, then Bob has a choice to pick from s[1:n-1] and s[0:n-2] if Alice chooses the last character.

In the end, there will be one character left and Bob will lose, win or Draw depending on the character Alice chooses before this.

In other words,

If Alice chooses the start character, then we would call best_value( s, start + 1, end, s[start]);

Otherwise, we would call best_value( s, start , end - 1, s[end]);

Notice best_value( s, start + 1, end, s[start]); now describes Bob chooses a character. So Bob will be the move maker. Since Alice wants to win, Alice wants to go in a position where Bob loses. If that's not possible Alice will try to go where Bob loses, and if even that's not possible then Alice has no option.

This is a problem category called - Algorithmic Games or Game Theory.

Here is a very good article on Topcoder.

Let's start with the implementation

/*
Explained input parameters above - also intuitive
Returns 
0 - If the current player have no move to win but can draw
1 - If current player have a move to win
2 - If current player have no other move that to lose.
*/
int best_value(string &s, int start, int end, char prev){
    // If length is one, then bob is selecting
    // and thus if bob select not equal character, it will be issue
    if(start == end){
        if(s[start] == prev)return 0; //it is draw
        if(s[start] < prev)return 1; // Current Player Wins
        if(s[start] > prev)return 2; // Current Player Loses
    }
    if((end - start + 1) % 2 == 0){
        int left_val = best_value(s, start + 1, end, s[start]);
        int right_val = best_value(s, start, end - 1, s[end]);
        // If any value is 1, that is current player can win using it,
        // Current player will definitely choose this
        if(left_val == 2 || right_val == 2){
            return 1;
        }
        // If any value is 0, that is current player can draw using it,
        // Current player will definitely choose this since they cannot     
        // win
        // as checked above
        if(left_val == 0 || right_val == 0){
            return 0;
        }
        // No other options, current player will lose.
        return 2;
    }
    int left_val = best_value(s, start + 1, end, s[start]);
    int right_val = best_value(s, start, end - 1, s[end]);
    // If any value is 1, that is current player can win using it,
    // Current player will definitely choose this
    if(left_val == 2 || right_val == 2){
        return 1;
    }
    // If any value is 0, that is current player can draw using it,
    // Current player will definitely choose this since they cannot win
    // as checked above
    if(left_val == 0){
        if(s[start] == prev)return 0; //it is draw
        if(s[start] < prev)return 1; // Current Player Wins
        if(s[start] > prev)return 2; // Current Player Loses
    }
    if(right_val == 0){
        if(s[end] == prev)return 0; //it is draw
        if(s[end] < prev)return 1; // Current Player Wins
        if(s[end] > prev)return 2; // Current Player Loses
    }
    // No other options, current player will lose.
    return 2;
}

But you will notice that is not optimal because

1. You can see it is resolving many sub-problems on repeat

2. You analyzed time complexity

3. You tried submitting it and it gave you TLE like this

If you remember Memoization from this blog, you will realize that we can simply solve by storing the results in variables, really just that.

Just do this -

#include<bits/stdc++.h>
using namespace std;

int dp[2010][2010][26];

/*
Explained input parameters here - also intuitive
Returns 
0 - If the current player have no move to win but can draw
1 - If current player have a move to win
2 - If current player have no other move that to lose.
*/
int best_value(string &s, int start, int end, char prev){
    int &ans = dp[start][end][prev - 'a'];

    if(ans != -1){
        return ans;
    }

    // If length is one, then bob is selecting
    // and thus if bob select not equal character, it will be issue
    if(start == end){
        if(s[start] == prev)return ans =  0; //it is draw
        if(s[start] < prev)return ans =  1; // Current Player Wins
        if(s[start] > prev)return ans =  2; // Current Player Loses
    }
    if((end - start + 1) % 2 == 0){
        int left_val = best_value(s, start + 1, end, s[start]);
        int right_val = best_value(s, start, end - 1, s[end]);
        // If any value is 1, that is current player can win using it,
        // Current player will definitely choose this
        if(left_val == 2 || right_val == 2){
            return ans =  1;
        }
        // If any value is 0, that is current player can draw using it,
        // Current player will definitely choose this since they cannot win
        // as checked above
        if(left_val == 0 || right_val == 0){
            return ans =  0;
        }
        // No other options, current player will lose.
        return ans =  2;
    }
    int left_val = best_value(s, start + 1, end, s[start]);
    int right_val = best_value(s, start, end - 1, s[end]);
    // If any value is 1, that is current player can win using it,
    // Current player will definitely choose this
    if(left_val == 2 || right_val == 2){
        return ans =  1;
    }
    // If any value is 0, that is current player can draw using it,
    // Current player will definitely choose this since they cannot win
    // as checked above
    if(left_val == 0){
        if(s[start] == prev)return ans =  0; //it is draw
        if(s[start] < prev)return ans =  1; // Current Player Wins
        if(s[start] > prev)return ans =  2; // Current Player Loses
    }
    if(right_val == 0){
        if(s[end] == prev)return ans =  0; //it is draw
        if(s[end] < prev)return ans =  1; // Current Player Wins
        if(s[end] > prev)return ans =  2; // Current Player Loses
    }
    // No other options, current player will lose.
    return ans =  2;
}

void solve(){
    string s;
    cin >> s;
    int n = s.size();
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            for(char k = 'a'; k <= 'z'; k++)
            dp[i][j][k - 'a'] = -1;
    int result = best_value(s, 0, n-1, 'a');
    if(result == 0){
        cout << "Draw\n";
    }
    else if(result == 1){
        cout << "Alice\n";
    }
    else if(result == 2){
        cout << "Bob\n";
    }
}

int main(){
    int t;
    cin >> t;
    while(t--)solve();
}

You can see my submission here.

Please like and share my posts if they are helpful.