×

# CHEFAOR - Editorial

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

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[i][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[i][j]$, we can iterate from $p = i-1 \dots 1$ and use the relation:

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

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[i][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[i] = BitwiseOR(A[1], A[2], \dots, A[i])$. 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[i][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[i])$ and $BitwiseOR(A[p+1], A[p+2], \dots, A[i])$ 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:

This question is marked "community wiki".

1.3k156581
accept rate: 4%

19.8k350498541

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 !!

(28 Jun '15, 15:41) 1★

 2 Can someone tell me why my O(NKlog(A)) solution gives TLE? Link answered 28 Jun '15, 14:17 1.9k●4●13●17 accept rate: 11% same here. (28 Jun '15, 22:40) Bad constant? (29 Jun '15, 17:58) Hm... that's sad actually if you get the correct, but can not implement it properly. Where could I improve? (29 Jun '15, 18:15) Try to submit NKlog(A) code from editorial, you'll be surprised :) (30 Jun '15, 06:01) lebron7★ What exactly is the problem with the NKlogA solution from the editorial? (30 Jun '15, 08:53)
 1 Nice joke about "easily finish under 10 seconds". Here's author's code from editorial, submitted in practice: link answered 30 Jun '15, 06:01 7★lebron 3.3k●3●17 accept rate: 24% 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. (30 Jun '15, 08:53) Tried tester1, it works 8.3 on maxtest. Far from TL*0.5 :) 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" :) 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. (30 Jun '15, 15:20) lebron7★
 0 Show us some solution please! answered 28 Jun '15, 16:42 2★xlee 13●1 accept rate: 0% added tester's and author's solutions (28 Jun '15, 17:37)
 0 Can someone tell me why my O(NKlog(A)) solution gives TLE? Link answered 29 Jun '15, 11:44 1 accept rate: 0%
 0 Can someone tell what is the complexity of my code , I feel it is the same as required and gives TLE. Solution answered 29 Jun '15, 16:13 2★xlee 13●1 accept rate: 0% Got it , precedence can make you cry! :D . Morover use memset over simple loop to fasten up your code!! (29 Jun '15, 17:34) xlee2★
 0 can someone tell me if the Tester2 is based on knuth optimization? answered 04 Jul '15, 04:24 4★cold5r 11●1 accept rate: 0%
 0 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 answered 26 Jan '17, 02:35 3★eteruel 1●1 accept rate: 0%
 -1 Why would you ever swap the order of [Author,Tester] => [Tester,Author]? answered 28 Jun '15, 23:30 1★yleewei 84●1●4 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,852
×2,212
×1,722
×67

question asked: 26 Jun '15, 12:32

question was seen: 6,872 times

last updated: 26 Jan '17, 02:35