< Back to forum

can any one please tell the approach for this question https://www.codechef.com/JULY18B/problems/NSA


Enter your answer details below:


Preview

Enter your comment details below:

Preview




1 Answer(s)

avatar

QUICK EXPLANATION:

Precalculate Y0

for unchanged string and arrays B[i][c] and F[i][c] holding number of letters less than c before position i and number of letters larger than c after position i correspondingly. After that you can try each single switch on position i from letter c1 to letter c2 having following formulas:

X=|c1−c2|,

Y=Y0−(B[i][c1]+F[i][c1])+(B[i][c2]+F[i][c2])

 

Whole solution works in O(N⋅Σ)

.

EXPLANATION:

Your solution has to be subquadratic to get 100 points. Thus it would be okay if you try to change every single letter and calculate new value of Y

. What is the impact single letter c in position i makes for the whole Y? It's number of letters less than c before i plus number of letters larger than c after i. If we calculate those values in advance for all possible i and c alongside with some initial Y0 for unchanged string, it will be possible for us to recalculate Y after we change letter at position i from c1 to c2

(see formulas from quick explanation). We can calculate values as follows:

string S;
cin >> S;
for(auto &it: S) {
    it -= 'a';
}
int N = S.size();
int Sigma = 26;

int B[N][Sigma], F[N][Sigma];
memset(B, 0, sizeof(B));
memset(F, 0, sizeof(F));

int64_t Y0 = 0;
for(int i = 1; i < N; i++) {
    int B_idx = i, F_idx = N - i - 1; // we run B_idx from 1 to N-1 and F_idx from N-2 to 0.
    for(int c = 0; c < Sigma; c++) {
        B[B_idx][c] = B[B_idx - 1][c] + (S[B_idx - 1] < c);
        F[F_idx][c] = F[F_idx + 1][c] + (S[F_idx + 1] > c);
    }
    Y0 += B[B_idx][S[B_idx]];
}

Now we can try every possible switch and choose the best option:

int64_t ans = Y0;
for(int i = 0; i < N; i++) {
    for(int c = 0; c < Sigma; c++) {
        int X = abs(S[i] - c);
        int64_t Y = Y0 - (B[i][S[i]] + F[i][S[i]]) + (B[i][c] + F[i][c]);
        ans = min(ans, X + Y);
    }
}
cout << ans << endl;

source : https://discuss.codechef.com/questions/131400/nsa-editorial
comment if you don't understand this solution

 

Shubham_Kumar_Gupta last updated on April 7, 2019, 6:34 p.m. 0    Reply    Upvote   

Instruction to write good question
  1. 1. Write a title that summarizes the specific problem
  2. 2. Pretend you're talking to a busy colleague
  3. 3. Spelling, grammar and punctuation are important!

Bad: C# Math Confusion
Good: Why does using float instead of int give me different results when all of my inputs are integers?
Bad: [php] session doubt
Good: How can I redirect users to different pages based on session data in PHP?
Bad: android if else problems
Good: Why does str == "value" evaluate to false when str is set to "value"?

Refer to Stack Overflow guide on asking a good question.