Блог пользователя DanceTheTragonDrainer

Автор DanceTheTragonDrainer, 4 года назад, По-английски

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
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +196 Проголосовать: не нравится

Downvote for spamming with tags.

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится -107 Проголосовать: не нравится

    LoOoOoOOOooOoLOooOoOOoOOoOOoOoLoOoOoOOL. ROFL. LMAO.

    On a serious note, upvote for the username.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +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.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +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.

  • »
    »
    4 года назад, # ^ |
    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??"

»
4 года назад, # |
  Проголосовать: нравится -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).

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    Try your algo on this test case [20,12,19]

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +26 Проголосовать: не нравится

    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

»
4 года назад, # |
  Проголосовать: нравится -14 Проголосовать: не нравится

low_kii_savage Please Help!!!

»
4 года назад, # |
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 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.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +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.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    +1, just found another corner case: 23 30 39 40. Surprisingly these cases work perfectly with the popular picking max element solution somehow.

»
4 года назад, # |
  Проголосовать: нравится +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.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    Can you post your solution as your explanation isn't very clear

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +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.

    • »
      »
      »
      4 года назад, # ^ |
      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.

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 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.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +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

      • »
        »
        »
        »
        4 года назад, # ^ |
        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, 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

»
4 года назад, # |
  Проголосовать: нравится +30 Проголосовать: не нравится

Can you give the link? It would be interesting to know the setter's rating.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +7 Проголосовать: не нравится

    This is the contest link. Although it probably doesn't work.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +62 Проголосовать: не нравится

      Doesn't work.

      Anyway, if the setter is from ...

      div 2
      div 1
      • »
        »
        »
        »
        4 года назад, # ^ |
        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?

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится +20 Проголосовать: не нравится

          Yes, sorry, I understood the situation about this problem wrongly. Weak tests is of course smaller issue than wrong solution.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +30 Проголосовать: не нравится

    Unfortunately Codechef doesn't reveal the problem setters of Indian ICPC online round

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +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.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

And I was thinking that Arab Region Regionals are the worst in the world, thanks man for this blog :D

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +13 Проголосовать: не нравится

https://discuss.codechef.com/t/icpc-online-round-2019-updates/42035

Finally, they officially acknowledged that something did go wrong.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    Lol they Forwarded the Ranklist "Along with Issues" Here issues are kept secret I dont know why.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    They acknowledged and then Did nothing Can this site be anymore Indian.