1
\$\begingroup\$

Maximillian is the chief commander of the Great Greek Army and he is leading his forces into a crucial war with Spain.

If all the enemy soldiers stand in a straight line incrementally marked starting from position 1, and a particular soldier at position \$i\$ dies, the soldiers at position \$2i\$ and \$2i+1\$ die as well. This happens in a cascading manner and so, a major part of troops can be killed by just killing one person.

By retrospection, Maximillian realizes that this also means that if the soldier marked \$1\$ (standing at the head of the troops) is killed and then the entire army is defeated. This however is not an easy task as the commander of the Spanish leads the Spanish troops and stands at the head of the troops. When one cascading set of deaths is completed, the remaining troops re-align; filling in the missing gaps and the death rule applies to the new positions.

Let there be \$N\$ soldiers in the enemy's camp marked as \$1,2,3,..., N\$. Maximillian identifies a list of \$K\$ individuals by their marked numbers, who will be executed in a sequential manner. Output the list of soldiers left in the enemy camp in increasing order of their marked values.


Input Specification:

input1: N, number of soldiers in the enemy camp

input2: K, number of soldiers to be killed

input3: An array of soldiers numbered between 1 to N who will be killed sequentially in the mentioned order

Output Specification:

Output an array of numbers that belong to soldiers who are alive at the end​ (in increasing order). If all are dead, then output {0}.


Test Case 1

input1: 7
input2: 1
input3: {1}
Output: {0}

Explanations:

The soldiers can be represented in the following way:

enter image description here

When Soldier {1} is killed, then {2,3} die.

When {2,3} die, {4,5,6,7} die.

Test Case 2

Example 2:

input1: 7
input2: 2
input3: {2,7}
Output: {1,3,6}

Explanations:

The soldiers can be represented in the following way:

enter image description here

When Soldier - {2} is killed, then {4,5} die.

They do not have any troops at \$2i\$ and \$2i+1\$.

The new representation becomes:

enter image description here

This is code-golf so the shortest code in bytes wins.


References:

\$\endgroup\$
9
  • 6
    \$\begingroup\$ So, the 2nd input is essentially the length of the 3rd one? I think many answers are going to ignore it. Also, why the special output {0} rather than just an empty array? \$\endgroup\$
    – Arnauld
    Apr 17 at 7:54
  • 8
    \$\begingroup\$ I think this needs more general test cases where the binary tree isn't full and where the whole army doesn't die. \$\endgroup\$
    – xnor
    Apr 17 at 8:08
  • 3
    \$\begingroup\$ Where did you get this challenge from? \$\endgroup\$
    – xnor
    Apr 17 at 8:23
  • 1
    \$\begingroup\$ I don't understand how exactly troops relocate in this rule: "When one cascading set of deaths is completed, the remaining troops re-align; filling in the missing gaps and the death rule applies to the new positions." \$\endgroup\$
    – xnor
    Apr 17 at 9:10
  • 3
    \$\begingroup\$ I can see there's a pending edit with major changes which may not reflect the intent of the OP. These clarifications should be provided by the OP. It should also be clarified whether this challenge comes from another programming contest -- as the typical I/O format is suggesting -- and if it can legitimately be posted here to begin with. \$\endgroup\$
    – Arnauld
    Apr 17 at 12:05
1
\$\begingroup\$

Jelly, 16 bytes

Ḥ,‘$€F>ÐḟðƬF⁴R¤ḟ

Try it online!

Ḥ,‘$€F>ÐḟðƬF⁴R¤ḟ  Main Link
         ðƬ       While the results don't reach a fixed point
Ḥ                 Double each value (killed soldier)
 , $              Pair            with
    €                  each value
  ‘                                    itself incremented
     F            Flatten the result
       Ðḟ         Filter out (remove) elements that are
      >           Greater than the right argument (the number of soldiers)
           F      Flatten the accumulated list of killed soldiers
               ḟ  Filter; remove the killed soldiers from
            ⁴R¤   [1, 2, ..., N], the list of all soldiers
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.