10 weeks ago

Rohit • 610

Hyderabad

Question 1

Question 2

3 months ago

Mohammad Zaid • 30

Hyderabad

Q1

Overview of the problem :

• Given a string X, Choose a subset of indices such that in any substring of length K, at least one of the character occurs at at least one of the chosen set of indices. We can rearrange the characters at the chosen indices and form a string. Among all the possibilities which satisfy the above condition , print the lexicographically smallest string obtained.

Approach :

• We can observe that it's always better to take smaller alphabetical characters first before going for the big ones.
• For example, if the string is "abcab" , we should always take character 'a' before even considering character 'b', as the final string will be lexicographically smaller if we take smaller characters.
• Now it's possible that even if we take all occurences of 'a',the condition in the problem is not satisfied. In that case we should consider the next smaller character,and keep considering characters in alphabetical order until the condition is satisfied.
• So in our final solution, we find the minimum i , such that if we take first i lowercase alphabets, the condition in the problem is satisfied. After finding the i, we take all occurrences of the first i-1 lowercase alphabets and exactly one occurrence of the ith alphabet,this is to ensure that our string is lexicographically smallest.

Time Complexity :

• O(N*P) , where N is the length of the given string , and P is the number of lowercase english alphabets

Pseduocode :

int main()    
{                           

    int K;
    string X;
    cin>>K;
    cin>>X;
    int freq[26]={0};
    for(auto A:X)
        freq[A-'a']++;
    for(int A=0;A<26;A++)
    {
        bool ok=true;
        int pre=-1000000000;
        for(int C=0;C<X.size();C++)
        {
            if(X[C]-'a'<=A)
            {
                pre=C;
            }
            if(C-pre>=K)
            {
                ok=false;
                break;
            }
        }
        if(ok)
        {
            for(int C = 0 ; C < A ; C++)
                for(int B = 0 ; B < freq[C] ; B++)
                    cout << (char)(C+'a');
            if(freq[A])
                cout << (char)(A+'a') << endl;
            return 0;
        }
    }
    return 0;
}

21 days ago

Lokesh 310

Hyderabad

Q2

Disclaimer

• The question is incomplete, with no sample test cases, so my understanding of the problem can be different from the actual problem.

Overview:

• Given the start and end points of n cars, find the length of the longest unoccupied segment.
• The unoccupied distance between the start of the line segment and the first car, and the last car and finish of the line segment is also taken into account while finding the longest unoccupied distance.

Approach:

• For a given car X, the closest car in front of it is the car Y, whose front strictly starts before the car X and has the least rear position:
  • Distance between cars X and Y is 0 is rear of car Y ends on or after the front of car X. Example: car X(5,3), car Y(7,4), distance(X, Y) = 0.
  • In other cases distance(X,Y) = rear(Y)-front(X)-1.
• So take all (front, rear) pairs for all cars and sort them according to front positions.
• Traverse from the car with the highest front position to the lowest front position:
  • Have the lowest encountered rear of a car(lowest_rear), whose front is strictly before the front of this car.
  • find the unoccupied distance between lowest_rear and the start of this car.
  • consider the rear of the current car for the lowest _rear after all cars with the same front position as the current car are finished.

Time complexity:

• O(NLOGN), N is the number of cars.

things to note:

• start array contains the rear points of cars, finish array contains the front of each car.

Pseudocode:

int longest_unoccupied(int n, vector<int> &start, vector<int> &finish)
{
    vector<pair<int, int>> car;
    int ans = 0 , lowest_rear = n + 1 , min_rear = n + 1;

    for (int i = 0; i < start.size(); i++)
    {
        car.push_back(make_pair(finish[i], start[i]));
    }

    car.push_back(make_pair(0, 0));    // imaginary car to account for the unoccupied distance between the start and first car
    sort(car.begin(), car.end());

    for (int i = car.size() - 1; i >= 0; i--)
    {
        if (i + 1 != car.size())
            if (car[i].first != car[i + 1].first)
                lowest_rear = min(lowest_rear, min_rear);
        if (lowest_rear > car[i].first)
            ans = max(ans, lowest_rear - car[i].first - 1);
        min_rear = min(min_rear, car[i].second);
    }

    return ans;
}

21 months ago

Yash Sahijwani 940

Solution for Question 1

Analysis

In the question, we are given a string beta and an integer alpha. Let the length of the string beta be n. Assuming 1-based indexing, we need to select some indices from 1 to n, such that, if we select any continuous substring of length alpha, from the string beta at random, then at least one of those selected indices lie in that substring.

There can be multiple such selections possible, and so we need to select the indices in such a way, that when we make a string from the letters at those indices (the letters in the string formed can be rearranged), we get the smallest possible lexicographical word.

Basic Idea

• When we form the final word, since we require the word to be lexicographically small, it is better to take all possible occurrences of smaller alphabets, before moving on to the bigger one. (Example: if ab and aab both satisfy the condition of covering the entire string, then it is better to take aab since it is lexicographically smaller than ab)
• So, we iterate over all alphabets from a to z. Say, we are at alphabet g, then we see whether taking all occurrences of all alphabets from a to g is able to cover the entire string (such that the condition is satisfied). If no, we move on to the next alphabet and do the same.
  • If yes, then it means that taking all occurrences of alphabets a to f didn't satisfy our condition, but adding all occurrences of alphabet g satisfies the condition.
  • However, it may be possible that it is not necessary to take all occurrences of the alphabet g, so we need to find out the least number of occurrences required to satisfy the condition.
  • We do this by iterating over all the positions at which the alphabets in the range a to f occur. We see the difference in positions between consecutive indices, and if that exceeds alpha, then we need to take some occurrences of g.
  • So we select the rightmost occurrence of g between consecutive elements such that the difference between the left index and this index is less than equal to alpha.
  • Now we make this new occurrence of g our current index and see whether the next index is at distance more or less than alpha. Then we keep on continuing this process to get the optimal number of occurrences of g required.
  • Lastly, add all these occurrences to a new string and sort the string (or add in lexicographical order itself).

Implementation

string s;
cin >> s;
ll k;
cin >> k;
vector < vector < ll > > idx(26);
ll n = s.length();
for(ll i=0;i < n;i++)
    idx[s[i]-'a'].pb(i);
vector < ll > curr;
for(ll i=0;i < 26;i++)
{
    bool possible = true;
    for(ll j=0;j <  (ll)idx[i].size();j++)
        curr.pb(idx[i][j]);
    sort(curr.begin(), curr.end());
    if((ll)curr.size()==(ll)0)
    {
        possible = false;
        continue;
    }
    ll prev = -1;
    for(ll j=0;j < (ll)curr.size();j++)
    {
        ll diff = curr[j] - prev;
        prev = curr[j];
        if(diff < k)
        {
            possible = false;
            break;
        }
    }
    if(!possible)
        continue;
    if(n-prev < k)
    {
        possible = false;
        continue;
    }
    vector < ll > without_last;
    for(ll j=0;j < (ll)curr.size();j++)
    {
        if(s[curr[j]]-'a'==i)
            continue;
        without_last.pb(curr[j]);
    }
    without_last.pb(n);
    prev = -1;
    ll last_count = 0;
    for(ll j=0;j < (ll)without_last.size();j++)
    {
        ll diff = without_last[j] - prev;
        if(diff >  k)
        {
            ll req = prev + k + 1;
            auto it = lower_bound(idx[i].begin(), idx[i].end(), req);
            it--;
            last_count++;
            prev = *it;
            j--;
            continue;
        }
        else if(diff < = k)
            prev = without_last[j];
    }
    string ans = "";
    for(ll j=0;j < i;j++)
    {
        for(ll k=1;k &lt; = (ll)idx[j].size();k++)
        {
            ans += ('a'+j);
        }
    }
    for(ll j=0;j < last_count;j++)
    {
        ans += ('a'+i);
    }
    cout << ans << '\n';
    return;
}