Subsequence product !!! NMNMX - NO MINIMUM NO MAXIMUM

[closed account 3UohqMoL]

Can anyone tell formula for nmnmx as i cannot get i

[closed account 3UohqMoL]

@Kr002
my limit has exceeded i have got for k = 2
powers of 2 increase by 1
powers of 3 increase by 2
powers of 4 increase by 3
powers of 5 increase by 4
powers of 6 increase by 5
powers of 7 increase by 6
powers of 8 increase by 7

plz help after this

[needbro]

@Kr002 okay i can get for any n,
but if I take mod(m-1) in calculating all the 3 parts , won't the answer be wrong?

[honeybuzz]

@all Finally I got 100 pts AC in NMNX!

1 0 AC
(0.020000)
1 1 AC
(0.010000)
1 2 AC
(0.020000)
Subtask Score: 20.00% Result - AC
2 3 AC
(0.110000)
2 4 AC
(0.440000)
2 5 AC
(1.890000)
2 6 AC
(9.720000)
2 7 AC
(6.840000)
Subtask Score: 80.00% Result - AC
Total Score = 100.00%

If anyone wants hints then please PM me the logic of NSA 100pts...
I have exhausted myself to the core and hence can't gather courage to start with NSA :P
PS you need to optimise your code to the very last drop to get it to work.
NOTE - I will only tell the core logic and not the code/pseudocode...I will help you with the expression to be generated but I will not tell you the exact expression...That is for you to derive...
I only need hints for NSA.

[honeybuzz]

Well, I can tell you that you need to figure out 2 main things that will help you beat the time constraint.
1)You need to find the pattern between the number of times that each elements occurs in the valid subsequences.
2)You need to somehow reduce the number of nCr's being calculated to a maximum of the number of terms that exist(n).This means that you can only afford to calculate only 1 nCr for each element.
Not doing any of the above conditions would result in TLE.

I cannot give you any more hint here in public but if you have NSA/EQUILIBR 100 pts, then PM me the core logic and I will give you more hints about MNMX.

[FrostGiant]

,

[honeybuzz]

Yep i will hint you about NMNX...PM me NSA HINT

[FrostGiant]

,

[blackmamba]

@honeybuzz for NSA u need to calculate number of elements to left of index i smaller than x if index i is replaced by x

[honeybuzz]

But counting elements smaller than the given element to the left of this element simply would take O(n^2)..I know an algo that can make it O(nlogn) but it still is too high since we have to do it for each element and that algorithm itself is quite complex.

[honeybuzz]

@FrostGiant I have enabled PM.Please share NSA hint

[blackmamba]

@honeybuzz u can do it in O(n).
hint: start from back ,have an arr a[26] and keep adding 1 to index u encounter. for eg if u encounter a make a[0]++
think a little bit more u will get it

[honeybuzz]

Yep thats what I was thinking of doing but dropped the idea thinking it was too complex...anyway, I will try to implement it.PS the complexity would be a bit more than O(n)

[blackmamba]

yes it would be O(n*26) for worst case thats makes it O(n) only

[blackmamba]

@honeybuzz check your inbox

[honeybuzz]

@blackmamba so i would have to have an array of 26 alphabets at each index of the array...correct?

[blackmamba]

yes u can do it that way ..

[honeybuzz]

I tried to calculate its complexity and in the worst case, I would have t*n*26*26 operations which would result in TLE :/

[needbro]

I'm using the euler totient fn. ,and have made the pascal triangle also,but still it leaves me with 20 pts only for the NMNMX problem.
and rest WA :(
what am i missing or doing wrong ..
i have PMed you @honeybuzz,@blackmamba,.
please help ,

[needbro]

@Kr002 what u said is not a fault, u might have misinterpreted it,my code should have not run for 20 pts also if i would have done any thing wrong.

there's something else i am missing