Firstly, just like the above solution, we observe that we only need to put one element in group A. Now, say we put an element X in group B. Then the final value obtained will be:
X AND Y
where Y is the OR of all numbers other than X. Now, let’s look at the value of Y:
The i th bit of Y will be 1 if and only if one or more of the numbers other than X has it’s i th bit equal to 1.
Here’s a tweak I can make to value of Y which I claim won’t change the value of (X AND Y). Let the i th bit of Y be 1 if and only if the i ith bit of two or more numbers (including X) is equal to 1. This doesn’t change the value of (X AND Y). Think why?
Moreover, this value of Y is independent of the choice of X. So you just calculate Y and find max of all x AND Y where x is a number from the given list. That’s the answer.
Complexity: Calculation of Y is O(N \log{N}) and finding max among (x AND Y) is O(N). So, overall complexity is O(N \log{N}).
My code for the problem A Game of Thrones passes the first subtask but gets a TLE on the second. Can someone please tell how I can optimize it? Here’s what I’m doing:
First, I sort the array. Since every king from n+1 to m has to attack exactly once, the total number of attacks is m-n. So, the numbers in array B will sum up to m-n. So we have to find out the number of ways to partition m-n attacks into the array formed by removing the elements from A which are less than or equal to n.
Let ind be the index of the smallest element greater than n in the sorted array A.
f(i, curtot) is the number of distinct arrays B[i...n-1] such that curtot (current total) is the current number of attacks that have happened, i.e., the number of attacks that have happened from ind to $i-1$th index. The number of attacks that can happen at the i th index can vary from 2 to a[i]-n-curtot, because as stated in the editorial, a[i]-n is the maximum number of attacks that can happen at i th index, and I’ve subtracted curtot from that because curtot attacks have already happened previously. So I iterate over every number x in this range and call f(i+1,curtot+x) and add it to dp[i][curtot]. The final answer is f(ind, 0).
How can I optimize this to pass the second subtask as well? Is there a better approach than this? I didn’t understand the editorial.
here it is: CodeChef: Practical coding for everyone in this i first tried to find the max, and then done or all elements except the max, then or the elements==max, as there may be manyMaxNos in the array.
the idea of sorting and doing the stuff didn’t came in my mind during contest, done in a little complicated way. BTW sorting was the correct approach to solve this.
@jvplus that is a hell of a complicated code. Here is my code which does the same thing why did I get some test cases wrong? CodeChef: Practical coding for everyone
@adhyyan
question 2
i feel we can write a simpler dp
dp[i]=f[ith prime]
dp1[i]= sum of primes till 'i’th prime(including i th prime);
dp[i]=dp[i-1]+dp1[i-1];
and then we can find where dp[i] exceeds 10^12
8613 prime=88903.
then we can do use upperbound/binarysearch
@adhyyan
meanwhile time limit could have been 1 sec.
we wanted to maximize the value of (A BTIWISE AND B). right I Google the properties of bitwise and and read somewhere that a&b can be at most min(a, b). then I bruteforcely checked whether it is correct or not and realized that the answer is min(both), btw I haven’t prove it, I did it totally on observations from some samples
I didn’t actually performed BITWISE AND, I had done some observation with couple of nested loops in order to improve complexity of code, and observed that the answers are always coming min(both), and that’s what I did and got AC, I haven’t done the proving I might got AC due to weak test cases.
If I understood your solution well, then the ineffcecient part is summing f(i+1,curtot+x) for every x. Rather than doing this we can store prefix sums of in another called pref. Pre[i, j] is sum of f(i, 0) + f(i, 1) + f(i, 2)… f(i, x). This will reduce the complexity by a factor of M