@jvplus can you post your code. Did you get both subtasks right?
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
only focus on solve(), ignore rest!
@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.
@jvplus Did you see mine. And I hope you know that you can’t use code templates in ZCO or INOI
in line 21 it should be: ans=min(ans,arr[n-1]);
@jvplus Where do you perform BITWISE AND in your code
1 Like
How to edit a community wiki?
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
@lokesh2002 yes your solution is also valid. In fact that was close o the intended solution. I had to reduce the time limits, to reduce the load on Codechef servers however I don’t think it affected anyone in any way. If you know of any instance where someone got TLE just cause of the lower time limit pls tell me.
this solution is wrong. I had put a specific test case just to fail this solution. Idk how it still passed.
The case was 25 6 6. 11001, 110, 110. The correct answer is 6
Thanks, I’ll try it.
@adhyyan1252 I’ve tried it for a long time and I don’t know why I’m getting wrong answers by using prefix sums. Maybe I haven’t correctly understood how to make a prefix sum array here. Can you please explain?