Need Hint On This Problem

Pages: 1234... 7
Jul 7, 2018 at 6:38pm
@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;



Last edited on Jul 7, 2018 at 6:39pm
Jul 7, 2018 at 6:53pm
@ipg what is str_k and str_l ?
Jul 7, 2018 at 6:56pm
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++
Last edited on Jul 7, 2018 at 6:58pm
Jul 7, 2018 at 7:00pm
@ipg this gives 109 as the result for abcd

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
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?
Last edited on Jul 7, 2018 at 7:05pm
Jul 7, 2018 at 7:03pm
@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
Last edited on Jul 7, 2018 at 7:04pm
Jul 7, 2018 at 7:06pm
.
Last edited on Jul 8, 2018 at 7:02am
Jul 7, 2018 at 7:12pm
.
Last edited on Jul 8, 2018 at 7:02am
Jul 7, 2018 at 7:15pm
.
Last edited on Jul 8, 2018 at 7:02am
Jul 7, 2018 at 7:46pm
@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.



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

/*  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;
}

Jul 8, 2018 at 5:08am
@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
Jul 8, 2018 at 6:52am
@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 ?
Jul 8, 2018 at 6:56am
@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 ?
Last edited on Jul 8, 2018 at 7:00am
Jul 8, 2018 at 7:10am
@ipg 2016069
how u got 30 points in no string attached im still getting only 10 from your code
Jul 8, 2018 at 8:10am
@kashish , reomve the extra variables and comments in code. try to resubmit 2 to 3 times.
Jul 8, 2018 at 8:55am
@cppcppcpp read again , i say you need to replace each elements of string from a ,b c to ...z
Jul 8, 2018 at 9:52am
closed account (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.
Jul 8, 2018 at 10:19am
@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.
Last edited on Jul 8, 2018 at 10:21am
Jul 8, 2018 at 10:25am
@kashish and @sj7
if you can't get 30 marks in NSA then

improve this code
1
2
3
4
5
6
7
8
9
10
11

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) ;
Jul 8, 2018 at 11:44am
@ipg check your PM i have sent you my solution to NSA.
Last edited on Jul 8, 2018 at 11:44am
Jul 8, 2018 at 12:06pm
closed account (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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/*  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;
}


Pages: 1234... 7