You are not logged in. Please login at www.codechef.com to post your questions!

×

CHEFAOR - Editorial

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

Tester1
Tester2

This question is marked "community wiki".

asked 26 Jun '15, 12:32

pushkarmishra's gravatar image

4★pushkarmishra
1.3k156281
accept rate: 4%

edited 27 Jul '15, 17:30

admin's gravatar image

0★admin ♦♦
14.9k347484503

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) franky1★

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

Link

link

answered 28 Jun '15, 14:17

gdisastery1's gravatar image

5★gdisastery1
1.9k41317
accept rate: 11%

edited 28 Jun '15, 14:18

same here.

(28 Jun '15, 22:40) rajat16037★

Bad constant?

(29 Jun '15, 17:58) alexvaleanu3★

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) gdisastery15★

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

(30 Jun '15, 06:01) lebron6★

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

(30 Jun '15, 08:53) pushkarmishra4★

Nice joke about "easily finish under 10 seconds".

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

link

answered 30 Jun '15, 06:01

lebron's gravatar image

6★lebron
1.8k8
accept rate: 28%

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) pushkarmishra4★

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) lebron6★

Show us some solution please!

link

answered 28 Jun '15, 16:42

xlee's gravatar image

2★xlee
131
accept rate: 0%

added tester's and author's solutions

(28 Jun '15, 17:37) pushkarmishra4★

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

Link

link

answered 29 Jun '15, 11:44

bertho_coder's gravatar image

5★bertho_coder
1
accept rate: 0%

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

link

answered 29 Jun '15, 16:13

xlee's gravatar image

2★xlee
131
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★

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

link

answered 04 Jul '15, 04:24

cold5r's gravatar image

4★cold5r
111
accept rate: 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

link

answered 26 Jan, 02:35

eteruel's gravatar image

3★eteruel
11
accept rate: 0%

-1

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

link

answered 28 Jun '15, 23:30

yleewei's gravatar image

1★yleewei
8414
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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

Tags:

×10,491
×979
×976
×67

Asked: 26 Jun '15, 12:32

Seen: 4,951 times

Last updated: 26 Jan, 02:35