### DanceTheTragonDrainer's blog

By DanceTheTragonDrainer, 14 months ago,

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?

• -100

 » 14 months ago, # |   +196 Downvote for spamming with tags.
•  » » 14 months ago, # ^ | ← Rev. 2 →   -107 LoOoOoOOOooOoLOooOoOOoOOoOOoOoLoOoOoOOL. ROFL. LMAO.On a serious note, upvote for the username.
•  » » 14 months ago, # ^ |   +21 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.
•  » » » 14 months ago, # ^ |   +34 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.
•  » » 14 months ago, # ^ | ← Rev. 2 →   +184 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??"
•  » » » 14 months ago, # ^ | ← Rev. 2 →   -49 are mota bhai Um_nik nik nik , nikal yahan se. bhasan naa de jyada. errichto apni bakchodi ke karan pelata hai.
•  » » » 14 months ago, # ^ |   -28 really totally insane which made you insane. huh! so bad. chill ! leave it.
 » 14 months ago, # |   -39 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).
•  » » 14 months ago, # ^ |   +8 Try your algo on this test case [20,12,19]
•  » » 14 months ago, # ^ |   +26 Case for which the test case fails for this approachGiven array elements {20, 12, 19}20|12|19 = 3112|19 = 3119 = 1931+31+19 = 81The correct answer is 81.Also you can check this blog
•  » » » 14 months ago, # ^ |   +22 Very interesting, thank you!
 » 14 months ago, # | ← Rev. 3 →   +3 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 ORRemoving 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.
•  » » 14 months ago, # ^ |   +18 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.
•  » » » 14 months ago, # ^ |   +11 Order of 3, 1, 2 gives 680255 + 229 + 196 = 680
•  » » 14 months ago, # ^ |   0 +1, just found another corner case: 23 30 39 40. Surprisingly these cases work perfectly with the popular picking max element solution somehow.
 » 14 months ago, # |   +1 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.
•  » » 14 months ago, # ^ |   +6 Can you post your solution as your explanation isn't very clear
•  » » 14 months ago, # ^ |   +16 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.
•  » » » 14 months ago, # ^ | ← Rev. 2 →   +8 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.
•  » » » » 14 months ago, # ^ |   0 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.
•  » » » 14 months ago, # ^ |   +1 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
•  » » » » 14 months ago, # ^ | ← Rev. 3 →   +1 if you are still removing from the removable set in according to element size, then this will also not work. 24, 12, 10, 9, 7from what I understand, your order of removal: 7, 9, 10, 12, 2431 + 31 + 30 + 28 + 24 order of removal: 9, 10, 7, 12, 2431 + 31 + 31 + 28 + 24
 » 14 months ago, # |   +30 Can you give the link? It would be interesting to know the setter's rating.
•  » » 14 months ago, # ^ |   +7 This is the contest link. Although it probably doesn't work.
•  » » » 14 months ago, # ^ |   +62 Doesn't work.Anyway, if the setter is from ... div 2why does he prepare problems for such an important event? div 1how did he reached div 1 if he can't stress with next_permutation?
•  » » » » 14 months ago, # ^ | ← Rev. 2 →   +17 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?
•  » » » » » 14 months ago, # ^ |   +20 Yes, sorry, I understood the situation about this problem wrongly. Weak tests is of course smaller issue than wrong solution.
•  » » 14 months ago, # ^ |   +30 Unfortunately Codechef doesn't reveal the problem setters of Indian ICPC online round
•  » » » 14 months ago, # ^ |   +96 Of course they don't, otherwise the setters would be eaten alive.
•  » » » » 14 months ago, # ^ |   -14 Rastogi Ji you are hilarious
•  » » » » » 14 months ago, # ^ | ← Rev. 2 →   +3 Comment Deleted.
•  » » 14 months ago, # ^ |   -9
•  » » 14 months ago, # ^ |   +30 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.
•  » » » 14 months ago, # ^ |   0 So, will the problem be removed (and correspondingly the score) for declaring the final ranklist?
•  » » » » 14 months ago, # ^ |   +4 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 :(
•  » » » » » 14 months ago, # ^ |   +16 Relax, last year was worse.
•  » » » » » » 14 months ago, # ^ |   +2 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.
•  » » » » » » » 14 months ago, # ^ |   +36 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.
•  » » » » » » 14 months ago, # ^ |   +7 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.
•  » » » » 14 months ago, # ^ |   +3 idk
•  » » » 14 months ago, # ^ |   +1 Where did you find about setter??
•  » » » » 14 months ago, # ^ |   +27 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.
•  » » » » » 13 months ago, # ^ |   +3 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
•  » » » » » » 13 months ago, # ^ |   +3 nope
•  » » » » » » 13 months ago, # ^ |   0 praveenDhinwa what is the scene now?
•  » » » 13 months ago, # ^ |   +3
•  » » » » 13 months ago, # ^ |   0 How did you access this page?
•  » » » » 13 months ago, # ^ |   0 And vntshh will it not get deleted ?
 » 14 months ago, # |   0 And I was thinking that Arab Region Regionals are the worst in the world, thanks man for this blog :D
•  » » 14 months ago, # ^ |   0 Well, this time the contest was pretty good except the SUMOR problem. Last year it was much worse than this.
 » 14 months ago, # | ← Rev. 2 →   +13 https://discuss.codechef.com/t/icpc-online-round-2019-updates/42035Finally, they officially acknowledged that something did go wrong.
•  » » 13 months ago, # ^ |   +8 Lol they Forwarded the Ranklist "Along with Issues" Here issues are kept secret I dont know why.
•  » » 13 months ago, # ^ |   +3 They acknowledged and then Did nothing Can this site be anymore Indian.