Need Hint On This Problem

[closed account 1TD80pDG]

@kashish

let's take string abcd;
so you need to first check si<sj for full string if si<sj is 0 then ans is 0.
else
you need to exchange every element of string a to z;

str1=str;

min=100000000;
for(i=0; i<str_len; i++)

{

for(int j=97; j<=122; j++)
{
str[i]= char(j);

for(int k=0; k<str_len ; k++)
{
int count=0;
for(int l=k+1; l<str_len; l++)
{
if(str_k<str_l)
count++;


}

count=count+ abs( int(str1[i]-int(str[i]));

if(count<min)
min=count;

[sc7]

@ipg what is str_k and str_l ?

[closed account 1TD80pDG]

str[k] and str[l]

for caculating how many pairs are si<sj likewise

for(i=0; size of str

for(j=i+1; size of str

if( s[i]<s[j])
count++

[sc7]

@ipg this gives 109 as the result for abcd

string str;cin>>str;
            string str1=str;
            int str_len=str.length();

        int min_val=100000000;
        for(int i=0; i<str_len; i++)

        {

            for(int j=97; j<=122; j++)
            {
                str[i]= char(j);
                

                    for(int k=0; k<str_len ; k++)
                    {
                        for(int l=k+1; l<str_len; l++)
                        {
                            if(str[k]<str[l])
                                count_val++;
                        }
                    }
            }


        

            count_val=count_val+ abs( str1[i]-str[i] );

            if(count_val<min_val)
                min_val=count_val;
        }

            cout<<min_val<<"\n";
            }

this is same as the code you provided, what am I missing?

[closed account 1TD80pDG]

@kashish i think in no minimum no maximum
i am missing boundary condition that's why i am getting wrong ans.
if you passed any single test in 2nd subtask then provide me answer for sample test case:

test case 1:

11 3
1 2 3 4 to 11

test case 2:

15 5
1 2 3 tp 15

test case 3:

100 5
1 2 3 to 100
test case 4:

1000 5
1 2 3 to 1000

[closed account 1TD80pDG]

.

[closed account 1TD80pDG]

.

[closed account 1TD80pDG]

.

[closed account 1TD80pDG]

@kashish and @sj7 use this code to generate all subsequences
this print the all subsequences of any array.
then if you get all AC then tell me.
this code faster way to print all subsequnces.

/*  C++ code to generate all possible subsequences.
    Time Complexity O(n * 2^n) */
#include<bits/stdc++.h>
using namespace std;
 
void printSubsequences(int arr[], int n)
{
    /* Number of subsequences is (2**n -1)*/
    unsigned int opsize = pow(2, n);
 
    /* Run from counter 000..1 to 111..1*/
    for (int counter = 1; counter < opsize; counter++)
    {
        for (int j = 0; j < n; j++)
        {
            /* Check if jth bit in the counter is set
                If set then print jth element from arr[] */
            if (counter & (1<<j))
                cout << arr[j] << " ";
        }
        cout << endl;
    }
}
 
// Driver program
int main()
{
    int arr[] = {1, 2, 3, 4};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << "All Non-empty Subsequences\n";
    printSubsequences(arr, n);
    return 0;
}

[ashishyadav]

@ipg 2016069
i got 20 marks in no maximum no minimum
and 10 in no string attached through my own code.I used 3 loops thats why it gives only 10 marks.

thanks for the help in reducing the nmbr of loops

[sc7]

@Kashish After getting all subsequences,
what did you do ? am getting WA in every subtask! Only sample is running correctly.

After I got the subsequence I ran a loop and found if the length of the subsequence == k then sort this subsequence and ran another loop from 1 to k-1 and multiplied all integers??? Are we not supposed to do that ??

for eg if k= 5 and I got two subsequences like [1,2,3,4,5] and [2,4,5,6,7] then my result will be

(2.3.4).(4.5.6) %MOD right ?

[closed account 1TD80pDG]

@sc7 if you don't get first subtask then use this
MOD=1000000007

ans=((ans%MOD)*(a[i]%MOD))%MOD;


. i don't know why i am getting wrong answer in 2nd subtask
i think in 2nd subtask there may be corner cases which i am getting or subtask 1 test cases are too light ?

[ashishyadav]

@ipg 2016069
how u got 30 points in no string attached im still getting only 10 from your code

[closed account 1TD80pDG]

@kashish , reomve the extra variables and comments in code. try to resubmit 2 to 3 times.

[closed account 1TD80pDG]

@cppcppcpp read again , i say you need to replace each elements of string from a ,b c to ...z

[iGEqDjzh]

@ipg Can you tell me the complexity of your NMINMAX code? Because if you are generating all the subsequences then it is impossible to pass the second subtask as for the second subtask value n <=5000 and 2^5000 is surely not going to run.

[closed account 1TD80pDG]

@iamrahul
/* C++ code to generate all possible subsequences.
Time Complexity O(n * 2^n) */
google it you will find efficient solution to generate all subseq.

[closed account 1TD80pDG]

@kashish and @sj7
if you can't get 30 marks in NSA then

improve this code

for(int k=0; k<str_len ; k++)
                    {
                        for(int l=k+1; l<str_len; l++)
                        {
                            if(str[k]<str[l])
                                count_val++;
                        }
                    }

you don't need to run every time for all values k=0 to str_len ;
if elements is change then run loop only for k=0 and elements changed index(l) ;

[closed account 3UohqMoL]

@ipg check your PM i have sent you my solution to NSA.

[iGEqDjzh]

@ipg I really don't understand what are you talking about as there is no "efficient" way to generate all subsequences since the number of subsequences for an array length n is itself 2^n-1 excluding the empty array. You must be getting TLE in your second subtask if you have used this code:

/*  C++ code to generate all possible subsequences.
    Time Complexity O(n * 2^n) */
#include<bits/stdc++.h>
using namespace std;
 
void printSubsequences(int arr[], int n)
{
    /* Number of subsequences is (2**n -1)*/
    unsigned int opsize = pow(2, n);
 
    /* Run from counter 000..1 to 111..1*/
    for (int counter = 1; counter < opsize; counter++)
    {
        for (int j = 0; j < n; j++)
        {
            /* Check if jth bit in the counter is set
                If set then print jth element from arr[] */
            if (counter & (1<<j))
                cout << arr[j] << " ";
        }
        cout << endl;
    }
}
 
// Driver program
int main()
{
    int arr[] = {1, 2, 3, 4};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << "All Non-empty Subsequences\n";
    printSubsequences(arr, n);
    return 0;
}