Solutions to ICOP 3

Contest Link

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 :slight_smile:

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.

6 Likes

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?

@ista2000 can u explain your solution.

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}).

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.

In JOKRBOMB, how can be calculate number of shortest path using the mentioned BFS+DFS trick?

1 Like

it’s works, i tried something similar and got AC.

@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

@jvjplus Can you explain how the answer is min(orr, mx) in your code?

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.