Editorials for all the 4 four problems of the ICOP1903 contest. Editorials for their respective problems written by Adhyyan, Jagreet and Shashwat.
SPLIT ARRAY
We 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, i-1] and [i+1, n-1] 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). P[1] = A[0] OR A[1]. P[2] = A[0] | A[1] | A[2]. However, with this method calculating P will take O(N^2). After careful observation we can see that P[i] = P[i-1] | 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, n-1] 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[i-1] | 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 USERNAME
This problem has 2 different approaches
Binary Search Approach: Pre-compute 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: Pre-compute 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)*(c-i+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.
JOKRBOMB
The 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, N-1 are the only cities, in the ith iteration only N \dots N-(i-1) 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.
GOTBOOK1
First 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 < Ai-N at all times as the Aith king sits on the ith throne.
Transition: the ith throne can be attacked anywhere between 2 to Ai-N times. Therefore dp[i][j] = Sum(dp[i-1][1...j-2]). 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.