Need Hint On This Problem
There is a sequence of N integers a1,a2,…,an.
where
1 ≤ ai ≤ 26
You are allowed(but don't have to) to replace any one number in this sequence with number x.Cost of this replacement is the absolute difference of there values i.e. |ai-x|.Let this value M.
1 ≤ x ≤ 26
Next, count the number of pairs of indices (i,j) in the resulting sequence (the sequence after changing one number, or the original sequence if no number was changed) such that 1≤i<j≤N and ai<aj. Let's denote it by P.
We have to find the minimum value of M+P.
where
1 ≤ ai ≤ 26
You are allowed(but don't have to) to replace any one number in this sequence with number x.Cost of this replacement is the absolute difference of there values i.e. |ai-x|.Let this value M.
1 ≤ x ≤ 26
Next, count the number of pairs of indices (i,j) in the resulting sequence (the sequence after changing one number, or the original sequence if no number was changed) such that 1≤i<j≤N and ai<aj. Let's denote it by P.
We have to find the minimum value of M+P.
Last edited on
@kashish
you said that
focus only on the number which are divisible by m.
https://www.codechef.com/JULY18B/problems/MGCSET
in Magic Set question
if N=2 and array is {1,2}
then subsequences are {1}, {2}, {1,2} then in sample test case 1:
1
2 3
1 2
output is 0 but there is one subsequences {1,2} sum is divisible by m(m==3). so output should be 1 instead of 0.
can you explain why output is 0 ?
you said that
focus only on the number which are divisible by m.
https://www.codechef.com/JULY18B/problems/MGCSET
in Magic Set question
if N=2 and array is {1,2}
then subsequences are {1}, {2}, {1,2} then in sample test case 1:
1
2 3
1 2
output is 0 but there is one subsequences {1,2} sum is divisible by m(m==3). so output should be 1 instead of 0.
can you explain why output is 0 ?
@kashish for magic set what will be output if n = 5,m = 3
2,3,5,9,6
according to me it should be :
{3,6,9},{3},{6},{9},{9,6},{3,6},{3,9}
Tell me if i'am right?
2,3,5,9,6
according to me it should be :
{3,6,9},{3},{6},{9},{9,6},{3,6},{3,9}
Tell me if i'am right?
Last edited on
@kashish https://www.codechef.com/JULY18B/problems/NMNMX
Can you help me. In No minimum no maximum problem.
I am just find the subsequences with size k and then sort the subsequences array and product the i=1 to n-1 elements of the each subsequences with lenght of k. And use modulo of 10^9+7 but only subtask is correct and original constraints giving wrong answer. So how to get the correct answer?
Can you help me. In No minimum no maximum problem.
I am just find the subsequences with size k and then sort the subsequences array and product the i=1 to n-1 elements of the each subsequences with lenght of k. And use modulo of 10^9+7 but only subtask is correct and original constraints giving wrong answer. So how to get the correct answer?
@sc7 No, i don't use bfs. I am just find the all subsequences of array and then only select subsequences with the length of k. And sort it and multiply each element except first and last elements. I think my code is unable to handle large integer. When we multiply.
Can anyone help me if let's say x= 10^18 and y=100 and how to multiply x*y and how to store them in any variable then how to use modulo operater .
ipg 2016069
i have not solved this problem.i getting wrong answer in this problem aswell as 3rd one.
i have not solved this problem.i getting wrong answer in this problem aswell as 3rd one.
@kashish for No Strings Attached problem, if want to get 30 marks then you need to use brute froce.
you need to change every element of string from a to z. then find the minmum of sum of si<sj and diffrence between changed character.
let's say string abcd.
so first you need to run loop
for( i=0; to i=str.size()
for ( i=97 to i=122
and keep change str[0]=char(i)]
change= str1[0]-str[0];
find the minmum of sum;
you need to change every element of string from a to z. then find the minmum of sum of si<sj and diffrence between changed character.
let's say string abcd.
so first you need to run loop
for( i=0; to i=str.size()
for ( i=97 to i=122
and keep change str[0]=char(i)]
change= str1[0]-str[0];
find the minmum of sum;
Last edited on
@ipg 2016069
i got 20 marks in no minimum and no maximum.
and TLE in rest of the subtask.
what result u get in 2nd subtask?
i got 20 marks in no minimum and no maximum.
and TLE in rest of the subtask.
what result u get in 2nd subtask?
@ipg 2016069
i have used brute force in no string attached but it giving me wrong on submission.I think im leaving some boundry test cases.
Can you suggest any.
i have used brute force in no string attached but it giving me wrong on submission.I think im leaving some boundry test cases.
Can you suggest any.
@ipg 2016069
in this question required answer is modulo of 1000000007.So for multiplication process you can use
MOD=1000000007
ans=((ans%MOD)*(a[i]%MOD))%MOD;
where ans stores the value of privious multiplication and a[i] is the new element to multiply.
Value of ans will never exceed 1010.
in this question required answer is modulo of 1000000007.So for multiplication process you can use
MOD=1000000007
ans=((ans%MOD)*(a[i]%MOD))%MOD;
where ans stores the value of privious multiplication and a[i] is the new element to multiply.
Value of ans will never exceed 1010.
Last edited on
@kashish my result is for no minimum no maximum
Sub-Task Task # Result
(time)
1 0 AC
(0.000000)
1 1 AC
(0.000000)
1 2 AC
(0.000000)
Subtask Score: 20.00% Result - AC
2 3 WA
(0.000000)
2 4 WA
(0.000000)
2 5 WA
(0.000000)
2 6 WA
(0.010000)
2 7 WA
(0.010000)
Subtask Score: 0.00% Result - WA
Total Score = 20.00%
Sub-Task Task # Result
(time)
1 0 AC
(0.000000)
1 1 AC
(0.000000)
1 2 AC
(0.000000)
Subtask Score: 20.00% Result - AC
2 3 WA
(0.000000)
2 4 WA
(0.000000)
2 5 WA
(0.000000)
2 6 WA
(0.010000)
2 7 WA
(0.010000)
Subtask Score: 0.00% Result - WA
Total Score = 20.00%
my result for No string attach (NSA) is
how to reduced 0.01 time,
time limit is 1.50
Sub-Task Task # Result
(time)
1 0 AC
(0.000000)
1 1 AC
(0.010000)
Subtask Score: 10.00% Result - AC
2 2 AC
(0.000000)
2 3 AC
(1.480000)
Subtask Score: 20.00% Result - AC
3 4 TLE
(1.510000)
3 5 TLE
(1.510000)
3 6 TLE
(1.510000)
Subtask Score: 0.00% Result - TLE
Total Score = 30.00%
how to reduced 0.01 time,
time limit is 1.50
Sub-Task Task # Result
(time)
1 0 AC
(0.000000)
1 1 AC
(0.010000)
Subtask Score: 10.00% Result - AC
2 2 AC
(0.000000)
2 3 AC
(1.480000)
Subtask Score: 20.00% Result - AC
3 4 TLE
(1.510000)
3 5 TLE
(1.510000)
3 6 TLE
(1.510000)
Subtask Score: 0.00% Result - TLE
Total Score = 30.00%
@ipg its not to reduce 0.01s , when the program ran for 1.51s it gave TLE call, the program might run for more time..