my solution was failing in only 1 test case the last one it was gving TLE i dont know why?
here is the link to my submission https://www.codechef.com/viewsolution/36846986
please could someone tell where am I going wrong! Thanks!
Can you please explain your code
Can Someone explain it more Clearly, I still don’t get it;
3 Likes
Compute the answer for each number.
Let arr[] = { 1 , 1 , 1 , 2 , 2 , 2 , 2 , 3 , 3 }
Now to calculate the number of subsequences in which 1 occurs the maximum number of times take the element 1 from the 3 1’s such that other element’s frequency does not exceed the frequency of 1.
For example:
No of subsequences in which 1 occurs exactly 1 time: 3c1 * ( 4c0 + 4c1 ) * ( 2c0 + 2c1)
No of subsequences in which 1 occurs exactly 2 time : 3c2 * ( 4c0 + 4c1 + 4c2 ) * ( 2c0 + 2c1 + 2c2 )
" " " " " " in which 1 occurs exactly 3 times : 3c3 *( 4c0 + 4c1 + 4c2 + 4c3 ) * ( 2c0 + 2c1 + 2c2 )
Do this for all the other elements. ( 2 and 3 )
Hope you get the idea.
9 Likes
I just saw your code
I am newbie I want to know how did you write such a well code in c++ 
plzz help me plzz tell me what should I do so that I can also write such code
I too kept track of prefix and suffix products under modulo, but always got a TLE on the last case! Why? https://www.codechef.com/viewsolution/36841269
I understood the logic part but in implementation i didn’t understand what are stored in prefix and suffix arrays??
5 Likes
Just keep learning new concepts and try to learn more data structures and algorithms and you will do good!
1 Like
In reply to kush_901:
Suppose the initial sequence is \{1,1,\cdots\,1,2,3,4,\cdots,n/2\}, with roughly n/2 ones, and n/2 other values. Then your values sz1 and sz2 will both be about n/2, and the 2-dimensional array ncr will have n^2/4 elements.
In the worst case, n could be 500,000, in which case your array will have 64 \times 10^9 elements. This is too many.
Similarly, you have several double loops sizes sz2 inside sz1, which give an O(n^2). solution.
How to optimize this calculation, because i did the same thing and got TLE (got 30 marks only)
my approach -
lets say there is an element x which is present f times, so what we do is we take all the frequencies of x one by one that is 1,2,3,4…f, and then go to all the other elements from 1 to n which are present and then suppose the current frequency of x is f1, so for the number lesser than x we find their total combinations such that the frequency is lesser than f1, and for the numbers greater than x we find the total combinations such that frequency is greater than or equal to f1, we multiply these numbers and hence will get the total number of subsequence where x is present f1 times and answer will be x, doing same with other elements too
I think this is an O(n^2) solution, how to optimize it.
lets say that a no. is having a count c then what i did was to precalculate cCk(i.e combinations) for all k from 0 to c and store the products (for all numbers) for particular k in a temporary array and used this later.
In this way u could easily get information about the possible products and additionally i used fenwick tree with it to manage small and big numbers
You can refer to my code here :
https://www.codechef.com/viewsolution/36738609
Instead of taking all the numbers one by one as you said I took all the numbers with same frequency.
For example : 1 1 1 1 2 2 2 3 3 3 4 4 4
No of subsequence in which 1 occurs exactly 1 time = 4c1 * ( 3c0 + 3c1 ) ^3
You can see that we can reduce the no of operations drastically by this way ( computing combinations of similar frequency and exponentiating them )
4 Likes
I’m getting tle in two testcase , pls someone make me understand how could I optimise this to AC.
Approach:
Store the freq of each element in a map.Calculate the coefficient sum (lets say prefix sum) for each element.Like , consider this testcase: 1 1 2 2 3 .For element 1: 2C0,2C0+2C1,2C0+2C1+2C2, similarly for element 2 (2C0, 2C0+2C1, 2C0+2C1+2C2 ) and 3 ( 1C0, 1C0+1C1).Next , Calculate product of prefix sum for each frequency in the whole array ( lets say Pre_Com). Pre_Com[i] denotes the product of prefix sum of freq i for all elements i.e
Pre_Com[1] = [ ( 2C0+2C1), (2C0+2C1)(2C0 + 2C1) , (2C0+2C1)(2C0 + 2C1)(1C0+1C1) ]
Pre_Com[2] = [( 2C0+2C1+2C2) , ( 2C0+2C1+2C2)(2C0 + 2C1+2C2) , ( 2C0+2C1+2C2)*(2C0 + 2C1+2C2) *(1C0+1C1)]
Now , iterate over all elements in map and for each freq of that element from 1 to freq[element],
calculate the ans as, fix considered freq (lets say fj )of the considered element (say ai, in the map),
ans = ( Pre[fj][last_element] * modular_inverse(Pre[fj][ai] ) ) * Pre_Com[ fj -1 ][ ai - 1]
My Submission
pls help all genius out there!
1 Like
You can refer to my code here :
https://www.codechef.com/viewsolution/36738609
Instead of taking all the numbers one by one as you said I took all the numbers with same frequency.
For example : 1 1 1 1 2 2 2 3 3 3 4 4 4
No of subsequence in which 1 occurs exactly 1 time = 4c1 * ( 3c0 + 3c1 ) ^3
You can see that we can reduce the no of operations drastically by this way ( computing combinations of similar frequency and exponentiating them ) .
1 Like
Consider the case like -
1 2 3 4 … 250000 250001 250001 250001 … (250000 times)
In this case your pre computation takes O(N²) time and space.
How to optimise -
Instead of storing pre computed values for all N, store for only those whose frequency is greater than or equal to i.
Suppose the frequencies for first 5 numbers are (1,2,1,3,1).
For i=1, we store prefix products of [(1C0+1C1), (2C0+2C1), (1C0+1C1), (3C0+3C1), (1C0+1C1)]
For i=2, we store [(21).(2C0+2C1+2C2) and (21).(2C0+2C1+2C2).(21).(3C0+3C1+3C2)]
And finally for i=3, we store [(2(1+2+1)).(3C0+3C1+3C2+3C3)]
Then after pre computation, if we want pre[i][j], we binary search for j on pre[i] and multiply appropriate powers of 2 for the remaining elements. Such powers of 2 can be easily evaluated in O(1) using prefix sums on frequencies.
Like if we want pre[2][3] for the above example, binary search will give us the precomputed value for pre[2][2] and then we multiply 21 to get pre[2][3].
Since the sum of the frequencies is equal to N, pre computation will only take O(N) and answering queries for each N will take O(log N) time because of binary search. Thus, the overall complexity is O(NlogN).
For details on implementation you can refer to my code. In this code, lbsearch and rbsearch are binary search functions, superfreq is just the prefix sums of frequencies, dp1 stores the precomputed values from left to right and dp2 stores them from right to left.
Maybe my approach is not the easiest to understand but it was the best I could think of.
1 Like
hey your code is well organised can you tell me the individual uses of the variable you have used like sum_till_now and how it is working i have idea behind logic but unable to implement it