Need Hint On This Problem

[ashishyadav]

There is a sequence of N integers a₁,a₂,…,a_n.
where
1 ≤ a_i ≤ 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. |a_i-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 a_i<a_j. Let's denote it by P.


We have to find the minimum value of M+P.

[closed account 1TD80pDG]

@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 ?

[ashishyadav]

ipg 2016069
i will explain it in that thread

[closed account 3UohqMoL]

@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?

[ashishyadav]

@wasp
yes you are right.

[closed account 1TD80pDG]

@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?

[sc7]

@ipg 2016069 have you tried using bfs ?

[closed account 1TD80pDG]

@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.

[closed account 1TD80pDG]

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 .

[sc7]

@ipg you used 3 loops for finding subsequences ??

[ashishyadav]

ipg 2016069
i have not solved this problem.i getting wrong answer in this problem aswell as 3rd one.

[closed account 1TD80pDG]

@sc7 i used only one loop. my time complexcity is O(n).

[closed account 1TD80pDG]

@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;

[ashishyadav]

@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?

[ashishyadav]

@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.

[ashishyadav]

@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 10¹⁰.

[closed account 1TD80pDG]

@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%

[sc7]

@ipg can you elaborate a little about NSA problem ?

[closed account 1TD80pDG]

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%

[sc7]

@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..