Question:
Given an array of N positive integers. The beautifulness of the array is defined as the bitwise OR of all elements of the array.
Now you have to remove the elements of the given array one by one and calculate the beautifulness of the remaining array and add this value to the answer after each step.
You have to maximize the final answer. Also print an order of the indexes in which you will remove the elements.
Constraints: 1 <= N <= 100,000 1 <= a[i] <= 1000,000,000
Example Case :
Input: N = 5
Array = {1,2,3,4,5}
Output : 33
1 2 4 3 5
Explanation:
Step 0: Array {1,2,3,4,5} OR = 7, SUM = 7
Step 1 : {2,3,4,5} OR = 7, SUM = 14
Step 2 : {3,4,5} OR = 7, SUM = 21
Step 3 : {3,5} OR = 7, SUM = 28
Step 4: {5} OR = 5, SUM = 33
Step 5: {}, SUM = 33
Ans = 33
Is this question even solvable in polynomial time?
Can some one who solved also tell their approach?
Downvote for spamming with tags.
LoOoOoOOOooOoLOooOoOOoOOoOOoOoLoOoOoOOL. ROFL. LMAO.
On a serious note, upvote for the username.
Can you please tell if the question is correct or not?
Because many teams wasted their time on this question and it costed them their ranks and a position in the regionals.
Errichto is neither involved in organization nor is he doing any social work(I think he does the streams only because he loves teaching) so tagging them is not a good thing, if any of them are interested they will probably answer it, stop forcing question on them.
This is insane. I understand that many people are angry because of this problem appearing in their regional but it is not a reason to mention random people in your blog. You can't downvote comments addressing bad blogging practices just because you want to know the answer. In any other situation this blog would be heavily downvoted.
UPD: People reading this when Errichto's comment having +200 "WTF is he talking about??"
As fas as I understand the problem it can be solved greedily. Fistly we choose the largest element of the array. It will be the last removed element. Secondly we can find the element among the remaining elements which gives the maximum value ORing it with the first element. This element will be the penultimate element. And so on till we can't find such element. The removing sequense of the other elements is insignificant. The complexity is O(30*N).
Try your algo on this test case [20,12,19]
Case for which the test case fails for this approach
Given array elements {20, 12, 19}
20|12|19 = 31
12|19 = 31
19 = 19
31+31+19 = 81
The correct answer is 81.
Also you can check this blog
Very interesting, thank you!
low_kii_savage Please Help!!!
Can someone check this solution for correctness: (couldn't debug during contest but works on the corner cases that have been discussed)
Any solution will be of the following form: First remove redundant elements (elements on removing which OR doesn't change) Then remove elements that reduce the OR
Removing the redundant elements must be done in sorted (increasing order). To do this we sort the initial array. Then for each element we check if for all its set bits j there exists atleast one more element with bit j set at 1. If for any set bit this isn't true, the element is not redundant and cannot be removed. (Not sure if the increasing order part is necessary but to be on the safer side)
After this process, we are left with N<=32 elements as each element has atleast 1 bit that no other element has and there are <= 32 bits.
Now, each element has a value which is equal to the sum of the values of it's unique (not present in any other element) set bits. For eg if we have 12, 18, 17 = {01100, 10010, 10001} thus 12 has value 6, 18 has value 2 and 17 has value 1. So we remove the element with the least value, update the values of the other elements (for eg here now 18 is the only element with the first bit as set) and then take out the least value again and keep doing this.
So our solution for 12, 18, 17 is 79.
Solution for corner case: 20 — {10100} 19 — {10011} 12 — {01100} So no element here is redundant and we can skip to the 2nd part of the solution.
The values are 0, 3, 8 respectively initially. So we first remove 20. Now the values are 19 and 12 respectively. So we remove 12 and then 19. This gives us the answer 81 as expected.
Consider [97, 196, 154]
Your algorithm would remove them in order 196, 97, 154, which would give you 255 + 251 + 154 = 660.
But a better solution is 97, 154, 196 giving 255 + 222 + 196 = 673.
Order of 3, 1, 2 gives 680
255 + 229 + 196 = 680
+1, just found another corner case: 23 30 39 40. Surprisingly these cases work perfectly with the popular picking max element solution somehow.
Our solution gave WA during the contest but I’m pretty sure the logic was correct. First of all remove zeros from the array and add the or of the array c+1 times in the answer (c=count of zeros). Keep 30 sets, such that si stores the numbers that have ith bit set. Also create a set (r) that has all the elements left. We do this operation (n-c) times - Create a set (nr) of non-removable elements, which stores the numbers that will decrease the value of or, if removed from the array. All the elements present in the sets (si) that have size 1 will come in this set. Now, iterate in the set r and select the smallest element which is not present in nr and remove it, if you find one (this won’t decrease the or value). If not then remove the smallest element from the nr set (this will decrease the or value and the difference would be this number). Update the sets r and si by removing this deleted element, wherever present.
Can you post your solution as your explanation isn't very clear
Consider [2, 5, 12]
All of them would come into your (nr) set, and you'll remove them in order 2, 5, and lastly 12, which would give 15 + 13 + 12 = 40.
However, a better order of removal is 5, 2, 12, which yields 15 + 14 + 12 = 41.
My solution check all the elements in nr set and select that number whose removal makes minimum change in current OR. It gives better answer 41. But it didn't get accepted in online round.
This approach is the same as in the comment above.
It fails on [97, 196, 154], where your algorithm removes them in order 196, 97, 154 giving 660.
But 97, 154, 196 gives 673.
So removing the smallest from nr set doesn't work and for it we need to check how much each element of nr set reduces the or value, which can be done in O(30*sizeof(nr)) i.e O(30*30). But this solution resulted in TLE during the contest.
Our submission — Code
if you are still removing from the removable set in according to element size, then this will also not work.
24, 12, 10, 9, 7
from what I understand, your order of removal: 7, 9, 10, 12, 24
31 + 31 + 30 + 28 + 24
order of removal: 9, 10, 7, 12, 24
31 + 31 + 31 + 28 + 24
Can you give the link? It would be interesting to know the setter's rating.
This is the contest link. Although it probably doesn't work.
Doesn't work.
Anyway, if the setter is from ...
why does he prepare problems for such an important event?
how did he reached div 1 if he can't stress with next_permutation?
We don't know whether the author's solution was incorrect or whether the test cases were weak.
The stress part would be useful only if the former is true, isn't it so?
Yes, sorry, I understood the situation about this problem wrongly. Weak tests is of course smaller issue than wrong solution.
Unfortunately Codechef doesn't reveal the problem setters of Indian ICPC online round
Of course they don't, otherwise the setters would be eaten alive.
Rastogi Ji you are hilarious
Comment Deleted.
The setter has CC rating ~2200 on long, ~1900 on short contests, across a decent number of contests. His intended solution turned out to be wrong.
So, will the problem be removed (and correspondingly the score) for declaring the final ranklist?
Codechef sucks conducting ICPC. Every time there will be some shit thing. I don't know, why only me keeps my foot on that shit :(
Relax, last year was worse.
drastogi21 If the setter's solution turns out to be wrong. And in the worst, if the problem turns out to be approximate, this would be worst bro.
The situation is bad, yes. But still, no one is safe from mistakes. The worst thing about all of this is organizers/admins behavior. They should make some official statements admitting the mistake, and hopefully do something to decrease the probability of this happening again. One ok-ish solution would be to ask top-10 teams in region to create problems and to test problems other teams created, and give them auto advancement to the next round.
Last year, the contest was unbalanced, but all problems had correct solutions and test cases. At least, the effort was put into something that was right.
idk
Where did you find about setter??
I'm the statement verifier for Codechef. I did something with these statements, I have some info. I'm also not willing to share all the info I have because lol why.
Do you have any idea what did they do finally https://discuss.codechef.com/t/icpc-india-regionals-online-round-2019-updates/42035 as they say they have forwarded Rank List
nope
vntshh
And I was thinking that Arab Region Regionals are the worst in the world, thanks man for this blog :D
https://discuss.codechef.com/t/icpc-online-round-2019-updates/42035
Finally, they officially acknowledged that something did go wrong.
Lol they Forwarded the Ranklist "Along with Issues" Here issues are kept secret I dont know why.
They acknowledged and then Did nothing Can this site be anymore Indian.