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