Editorials for all the 4 four problems of the ICOP1903 contest. Editorials for their respective problems written by Adhyyan, Jagreet and Shashwat. SPLIT ARRAYWe can observe that the BITWISE AND of two numbers will be lower or eqaul than both those number $A$ & $B \leq A$ $A$ & $B \leq B$ Similarly, we can observe that the BITWISE OR of two numbers will always be greater or equal to both the numbers $A$  $B \geq A$ $A$  $B \geq B$ Where & represent Bitwise AND operation while  represent Bitwise AND operator. If we want to maximize our value then we have to reduce the number of BITWISE AND operations we are performing and increase the number of BITWISE OR operations. The question had a constraint stating that there has to be at least one number in each box. That means we have to put exactly 1 number in the box with BITWISE AND and the rest of the numbers in the other box. This yields a very simple $O(N^2)$ solutions. We try putting in every element in box A one at a time. Then we can calculate the combined value of the 2 boxes using a single linear pass of the array. Every time we store the maximum and finally output it. Since there can be N elements which we choose to put in box A, and for each of those tries we have to do a linear pass the complexity is $O(N^2)$ which is not enough to give full points. To get full points a $O(n)$ method will suffice. We will again iterate over all elements and try putting them in Box A but this time we will calculate the combined value in $O(1)$ rather than $O(n)$. Suppose we fix element $i$ as the one which goes in box A. Then we can calculate the BITWISE OR of elements in range $[0, i1]$ and $[i+1, n1]$ and BITWISE OR them to get the value of Box B. If we naively, find the ORs it will take $O(N)$ time for each $i$ we choose. To make this faster we use prefix and suffix arrays. We have two arrays of length $N$, P and S. $P[j]$ will store the BITWISE OR of all elements from $[0, j]$. So by this definition $P[0] = A[0]$(where A is the input array). $P1 = A[0]$ OR $A1$. $P2 = A[0]  A1  A2$. However, with this method calculating P will take O(N^2). After careful observation we can see that $P[i] = P[i1]$  $A[i]$. Using this we can calculate $P$ in $O(n)$ time. Similar the $S$ array is the suffix array. $S[i]$ stores OR of elements from $[i, n1]$ and can be calculated in $O(N)$ time using a very similar method as above. Using these 2 arrays we can quickly compute the OR of all elements except $i$, which is equal to $P[i1]  S[i+1]$. Since computing the value can now be done in $O(1)$ time we can iterate over all $i$s and find the $i$ for which we get the maximum combined value. The complexity of this solution is $O(N)$. VOID AND USERNAMEThis problem has 2 different approaches Binary Search Approach: Precompute the prime numbers upto a suitable number like $2*10^5$. This number can be found out by observing the outputs of $f(x)$ for higher values of x and realizing that only primes upto $2*10^5$ can give a value near to the upper bound of the problem i.e. $10^12$. Next Binary Search the value of x, and calculate the value of the function for that x. Store the closest value of $f(x)$ to n and print that value. Dynamic Programming Approach: Precompute the summation of all primes upto $2*10^5$. Observation same as 1st approach. Let us assume we know the value of $f(x)$ and we want to know the value of $f(x+1)$. There are 2 cases : $x+1$ is not a prime in which case $f(x+1) = f(x)$. If $x+1$ is prime $f(x+1) = f(x) + (x+1)*(ci+1)$ + Sum of all primes below $(x+1)$. Observe that in the expansion of $f(x)$ and $f(x+1)$, only the coefficients of the terms of $f(x)$ is getting incremented by 1 in case of $f(x+1)$. Thus adding the sum of primes below $(x+1)$ alongwith the current value of the function will give us $f(x+1)$. We can use this approach to calculate initial values of $f(x)$ normally and then use DP to calculate $f(x)$ for higher values of x. JOKRBOMBThe number of shortest paths between 2 nodes can be calculated in O(N+M) using a DFS+BFS trick which is not useful here. They can also be calculated in O(N^3) using Floyd Warshall. To do this, you run 3 nested loops. Loop 1 picks i, the intermediate. Loop 2 picks u, the source and Loop 3 v, the destination. Now: if $Dist[u][v]=Dist[u][i]+Dist[i][v], Paths[u][v]+=Paths[u][i]*Paths[i][v]$ if $Dist[u][v]>Dist[u][i]+Dist[i][v], Paths[u][v]=Paths[u][i]*Paths[i][v]$ else do nothing. Proof you may find here. Tutorial for Floyd Warshal: geeksforgeeks article To find total number of shortest paths over all (u, v), just keep another count variable. If we pick the intermediate nodes i in reverse order from $N$ to $1$, in the first iteration $N$ is the only city, in second $N, N1$ are the only cities, in the ith iteration only $N \dots N(i1)$ are the only cities. Thus we are computing the sum of Num function in reverse order of time. Store this in a vector, reverse the vector and output it. GOTBOOK1First sort the array by final king number. Note that the position of a throne is irrelevant to the solution, just that the final array B has to be made accordingly. Ignore all the initial thrones up till the one in which a king with number > N is sitting as no attacks could have taken place on these. Let first throne with King $ > N$ be X. From throne X, we define $dp[i][j]$ as the answer when For the first i thrones, j attacks have been assigned. Remember that j must be < AiN at all times as the Aith king sits on the ith throne. Transition: the ith throne can be attacked anywhere between 2 to AiN times. Therefore $dp[i][j] = Sum(dp[i1][1...j2])$. This sum can be computed fast using prefix sums If you have any questions or feedback please feel free to comment on this post. I hope you learned a lot in this contest :) Feel free to share your approach/ doubts. Important Announcement: If you guys feel you can host ICO prep contest and want to join us, please join this group by clicking at this link.
This question is marked "community wiki".
asked 17 Nov '18, 22:29

In JOKRBOMB, how can be calculate number of shortest path using the mentioned BFS+DFS trick? answered 18 Nov '18, 21:56

Nice Editorial! What if I sorted my array according to the number of 1s in its binary representation and the took the BITWISE OR of all elements except the largest one. Then took BITWISE AND with the largest one? answered 17 Nov '18, 23:00
it's works, i tried something similar and got AC.
(17 Nov '18, 23:10)
@jvplus can you post your code. Did you get both subtasks right?
(17 Nov '18, 23:11)
here it is: https://www.codechef.com/viewsolution/21636726 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.
(17 Nov '18, 23:15)
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.
(17 Nov '18, 23:17)
@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? https://www.codechef.com/viewsolution/21635780
(17 Nov '18, 23:21)
only focus on solve(), ignore rest!
(17 Nov '18, 23:24)
@jvplus Did you see mine. And I hope you know that you can't use code templates in ZCO or INOI
(17 Nov '18, 23:34)
in line 21 it should be: ans=min(ans,arr[n1]);
(17 Nov '18, 23:38)
1
@jvplus Where do you perform BITWISE AND in your code
(17 Nov '18, 23:39)
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.
(18 Nov '18, 00:35)
@salil03 thanks for reminding me about the template.
(18 Nov '18, 00:41)
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
(18 Nov '18, 10:20)
showing 5 of 12
show all

answered 17 Nov '18, 23:33
@jvjplus Can you explain how the answer is min(orr, mx) in your code?
(18 Nov '18, 00:00)
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
(18 Nov '18, 00:15)
check this: https://ide.geeksforgeeks.org/fp6cPLMZro
(18 Nov '18, 07:38)

Here's an alternate solution for Split Array: 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})$. answered 17 Nov '18, 23:50

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 $mn$. So, the numbers in array $B$ will sum up to $mn$. So we have to find out the number of ways to partition $mn$ 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$. 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. answered 18 Nov '18, 02:29
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
(18 Nov '18, 09:28)
Thanks, I'll try it.
(18 Nov '18, 19:47)
@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?
(19 Nov '18, 19:42)

@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[i1]+dp1[i1]; 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.
How to edit a community wiki?
@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.