# The Great Battle Conundrum- Who are Alive?

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:

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:

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

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

The new representation becomes:

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

## References:

• 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? Apr 17, 2021 at 7:54
• I think this needs more general test cases where the binary tree isn't full and where the whole army doesn't die.
– xnor
Apr 17, 2021 at 8:08
• Where did you get this challenge from?
– xnor
Apr 17, 2021 at 8:23
• 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."
– xnor
Apr 17, 2021 at 9:10
• 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. Apr 17, 2021 at 12:05

# 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


# Python, 125124 119 bytes

-1 byte thanks to @The Thonnu

def f(n,k,A):*B,=range(n+1);g=lambda d:d<len(B)and g(2*d+1)|g(2*d)|B.pop(d);[g(B.index(x))for x in A];print(B[1:]or[0])


Attempt This Online!

Uses the array representation of a binary tree, then recursively removes the given element and the associated children of that element for each item in A.

• 124 Apr 8, 2023 at 18:04

# Scala, 211 bytes

Golfed version, Try it online!

def f(n:Int,k:Int,A:List[Int])={var B:List[Int]=(0 to n).toList;def g(d:Int):Unit={if (d<B.length){g(2*d+1);g(2*d);B=B.patch(d,Nil,1);}};A.foreach(x=> g(B.indexOf(x)));println(if(B.length>1)B.tail else List(0))}


Ungolfed verison:

object Main {
def f(n: Int, k: Int, A: List[Int]): Unit = {
var B: List[Int] = (0 to n).toList

def g(d: Int): Unit = {
if (d < B.length) {
g(2 * d + 1)
g(2 * d)
B = B.patch(d, Nil, 1)
}
}

A.foreach(x => g(B.indexOf(x)))
println(if (B.length > 1) B.tail else List(0))
}

def main(args: Array[String]): Unit = {
f(7, 2, List(2, 7))
}
}