CHEFAOR - Editorial

dynamic-programming
easy-medium
editorial
ltime25

#1

PROBLEM LINK:

Practice
Contest

Author: Roman Furko
Testers: Pushkar Mishra and Sergey Kulik
Editorialist: Pawel Kacprzak and Pushkar Mishra
Russian Translator: Sergey Kulik
Mandarian Translator: Gedi Zheng

DIFFICULTY:

Easy-Medium

PREREQUISITES:

DP, Bitwise Operations

PROBLEM:

Given an array A of N integers ranging from 0 to 2^{30}, partition this array into K consecutive sub-arrays such that the sum of Bitwise ORs of these sub-arrays is maximized.

Naive Approach

The simplest approach is to try out all possible partitions using recursion and take the maximum. This approach will try out at least {N \choose K-1} possibilities. It is clearly inefficient and will time-out for all sub-tasks.

An \mathcal{O}(N^2K) solution:

We can use Dynamic Programming. Let us maintain a 2-D array DP[][] in which DP*[j] stores the maximum sum that you can get by partitioning the segment 1 \dots i into j sub-segments. Evidently, this is an optimal overlapping sub-structure of the main problem.

To calculate DP*[j], we can iterate from p = i-1 \dots 1 and use the relation:

DP*[j] = max(DP*[j], DP[p][j-1] + BitwiseOR(A[p+1], A[p+2], \dots, A*)).

Since N, K \geq 1000, this algorithm will time out for the last two sub-tasks.

Optimising the DP to \mathcal{O}(NK\log(A_{max})) :

We make two observations:

  • DP[p][j] \leq DP*[j] for p \leq i. This isn’t difficult to infer since Bitwise OR operation on two numbers never results in a number smaller than either of the two.
  • Let us consider an array C where C* = BitwiseOR(A[1], A[2], \dots, A*). For i > 30, we claim that there are only 30 distinct values in the array C. The reason is that cumulative Bitwise OR operation accumulates ‘1’ bits. Since the maximum number of ‘1’ bits in the values stored in array C can be 30, thus there can only be 30 distinct values in array C.

Now, using the two aforementioned observations, we can optimize our DP. While calculating DP*[1 \dots K], we were iterating from p = 1 \dots i-1 and checking DP[p][1 \dots K]. But we can now say that we only need to iterate from 1 \dots K for those p where BitwiseOR(A[p], A[p+1], \dots, A*) and BitwiseOR(A[p+1], A[p+2], \dots, A*) are different. Since, there can at max be 30 such p, therefore, the net complexity comes down to \mathcal{O}(NK\log(A_{max})). This will easily finish in under 10 seconds.

An \mathcal{O}(NK) solution :

The \mathcal{O}(N^2K) DP solution can directly be optimised to \mathcal{O}(NK) DP using a widely known optimisation method called “Knuth Optimisation”. Though this was not required to solve the problem for 100 points, we suggest that you go through the concept:
Quora
Codeforces

AUTHOR’S AND TESTER’S SOLUTIONS:

Tester1
Tester2


#2

Can someone tell me why my O(NKlog(A)) solution gives TLE?

Link


#3

Show us some solution please!


#4

Why would you ever swap the order of [Author,Tester] => [Tester,Author]?


#5

Can someone tell me why my O(NKlog(A)) solution gives TLE?

Link


#6

Can someone tell what is the complexity of my code , I feel it is the same as required and gives TLE.
Solution


#7

Nice joke about “easily finish under 10 seconds”.

Here’s author’s code from editorial, submitted in practice: link


#8

can someone tell me if the Tester2 is based on knuth optimization?


#9

Try to solve it using a Divide and Conquer approach, this is another kind of dynamic programming optimization that runs in O(KNlogN), and here’s my solution that runs in 6.90 s

PD: You can read about it here


#10

http://www.codechef.com/viewplaintext/7298688

I coded the solution after going through editorial(but it is top-down approach).I could pass first sub-task only.Can someone figure out what optimization i have to do to my code to pass other sub-tasks.I think I have taken care of trick mention in editorial.Plz help !!


#11

added tester’s and author’s solutions


#12

same here.


#13

Got it , precedence can make you cry! :smiley: . Morover use memset over simple loop to fasten up your code!!


#14

Bad constant?


#15

Hm… that’s sad actually if you get the correct, but can not implement it properly. Where could I improve?


#16

Try to submit NKlog(A) code from editorial, you’ll be surprised :slight_smile:


#17

What exactly is the problem with the NKlogA solution from the editorial?


#18

On the testing server, all test files were passing under 8 seconds. Author’s solution was only for first 2 subtasks. it was wrongly uploaded here. the correct solutions are up now. Try submitting tester2’s solution.


#19

Tried tester1, it works 8.3 on maxtest. Far from TL*0.5 :slight_smile: I agree that getting TL because of bad implementation why AC is possible is a contestant’s fault, but that’s definitely not “easily finish” :slight_smile: Looking at other comments in this topic - I am not the only one who thinks this way.

And what was the point about “try tester2’s”? It is complitely different solution, based on Knuth optimization; it has nothing to do with NKlogA.