DanceTheTragonDrainer's blog

Is the problem SUMOR even solvable? (INDIAN ICPC)
By DanceTheTragonDrainer, 5 years ago, In English

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?

  • Vote: I like it
  • -100
  • Vote: I do not like it

Comments Comments (47)
| Write comment?
»
5 years ago, # |
  Vote: I like it +196 Vote: I do not like it

Downvote for spamming with tags.

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it -107 Vote: I do not like it

    LoOoOoOOOooOoLOooOoOOoOOoOOoOoLoOoOoOOL. ROFL. LMAO.

    On a serious note, upvote for the username.

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +34 Vote: I do not like it

      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.

      → Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it +184 Vote: I do not like it

    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??"

    → Reply
»
5 years ago, # |
  Vote: I like it -39 Vote: I do not like it

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).

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

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

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +26 Vote: I do not like it

    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

    → Reply
»
5 years ago, # |
  Vote: I like it -14 Vote: I do not like it

low_kii_savage Please Help!!!

→ Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it +3 Vote: I do not like it

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.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

      Order of 3, 1, 2 gives 680

      255 + 229 + 196 = 680

      → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

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

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 2   Vote: I like it +8 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      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

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
        ← Rev. 3   Vote: I like it +1 Vote: I do not like it

        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

        → Reply
»
5 years ago, # |
  Vote: I like it +30 Vote: I do not like it

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

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +62 Vote: I do not like it

      Doesn't work.

      Anyway, if the setter is from ...

      div 2
      div 1
      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
        ← Rev. 2   Vote: I like it +17 Vote: I do not like it

        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?

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it +20 Vote: I do not like it

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

          → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +30 Vote: I do not like it

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

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +30 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      So, will the problem be removed (and correspondingly the score) for declaring the final ranklist?

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +4 Vote: I do not like it

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

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it +16 Vote: I do not like it

          Relax, last year was worse.

          → Reply
          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
              Vote: I like it +2 Vote: I do not like it

            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.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              5 years ago, # ^ |
                Vote: I like it +36 Vote: I do not like it

              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.

              → Reply
          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
              Vote: I like it +7 Vote: I do not like it

            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.

            → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        idk

        → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Where did you find about setter??

      → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      vntshh

      → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +13 Vote: I do not like it

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

Finally, they officially acknowledged that something did go wrong.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

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

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

    → Reply