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

×

Explanation of Editorial

https://codeforces.com/problemset/problem/243/A

It would be a great help if someone could explain the editorial of this question. I have been trying to understand it for a long time but simply couldn't.

Thanks in advance ;)

asked 12 Dec '18, 23:06

incognito_nag's gravatar image

5★incognito_nag
11
accept rate: 0%


Consider all values $f(l, r)$ with fixed $r$.

Claim: the number of such values is at most $20$.
Because $0 \le a_i \le 10^6$, which is slightly less than $2^{20}$, the largest value of $f(l,r)$ can have at most 20 bits. Now $f(l-1, r) = a_{l-1}\ | \ f(l,r)$, which means the number of 1 bits in $f(l-1,r)$ is $\ge$ the number of 1 bits in $f(l,r)$. However you can only increase the number of 1 bits until you hit $20$, hence the claim is proved.

Let's say you maintain a set of values $f(l, r)$ for some $r$. This is quite doable because of the $20$ value limit. Let's call this set $g(r)$. Then, $g(r) = \{a_r\} \cup \{a_r \ | \ x : x \in g(r-1) \}$, which basically means that you OR $a_r$ with each value of $g(r-1)$ to get the values of $g(r)$ and also consider the value $a_r$ itself. I suppose this can be considered dynamic programming.

If you calculate $g(i)$ for all indices, the set of all possible values $f(l,r)$ is $\bigcup_{i=1}^n g(i)$. You just need to output the size of this set.

link

answered 12 Dec '18, 23:48

meooow's gravatar image

6★meooow ♦
7.0k718
accept rate: 48%

thanks a lot @meooow for such a good explanation.

Although, I have used a different approach ( prefix sum and binary search) and it gave me ACCEPTED ;)

(13 Dec '18, 01:50) incognito_nag5★

Could you share your approach? I'm interested to know.

(14 Dec '18, 20:46) meooow ♦6★
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

Question tags:

×655
×1

question asked: 12 Dec '18, 23:06

question was seen: 122 times

last updated: 14 Dec '18, 20:46