BYTEISLE - Editorial

editorial
, , ,
1

PROBLEM LINKS

Practice
Contest

DIFFICULTY

EASY

EXPLANATION

Note that the type of each Bytelandian is completely determined by the number of Byteknights in the island. Because there are between 0 and N Bytelandians, the number of solutions is actually only between 0 and N (modulo 1000000007 :P).

Firstly, we have to determine the number of Byteknights. Let knight[n] be the number of Bytelandian that satisfies a _ i <= n <= b _ i; that is, the number of Bytelandians that said it is possible to have n Byteknights in the island. It is easy to see that the number of Byteknights can be n iff knight[n] = n.

So, we need a data structure that can perform these operations efficiently:

  1. Increase the values of knight[a _ i]…knight[b _ i], for each Bytelandian i by 1
  2. Query the value of knight[i], for each 0 <= i <= N

Because all queries are needed only after the updates, the so-called ‘partial difference’ data structure suffices. Let diff[i] be knight[i]-knight[i-1]. Operation 1 can be simulated by increasing diff[a _ i] and decreasing diff[b _ i + 1]. Operation 2 is simply the sum of diff[1]…diff[i], which can be precalculated after the updates take place.

Secondly, we have to determine the lexicographically smallest solution. If it is possible for a Bytelandian to be a Byteknaves, then we should assign it Byteknaves, otherwise the solution would not be lexicographically smallest because ‘1’ is greater than ‘0’. A Bytelandian i can be assigned Byteknave iff there is n is a possible number of Byteknights (valid solution) and n is not in range a _ i…b _ i, i.e., he is lying.

A segment tree will perform the step efficiently. Let tree[n] = 1 if knight[n] = n, or 0 otherwise. Then we can query the number of valid solutions in a range in logarithmic time. After we decide that Bytelandian i is a Byteknave, we set all elements of the tree in the range a _ i…b _ i to zero. If it is not possible for Bytelandian i to be a Byteknave, because the number of valid solutions in the range a _ i … b _ i is the same of the number of valid solutions in the range 0…N, we must assign it a Byteknight.

SETTER’S SOLUTION

Can be found here.

TESTER’S SOLUTION

Can be found here.

1 Like
2

Why is Knight[i] = Diff[1] + Diff[2] + … + Diff[i] ?
I mean the right hand sum would basically be equal to Knight[i]-Knight[0].
And Knight[0] is not necessarily equal to 0.

3

The below statement in editorial does not seem to be true and confuses me.

“the number of solutions is actually only between 0 and N”

However, In example given here the solutions comes to be 5 for N=4.

1 Like
4

can Anyone explain :
" After we decide that Bytelandian i is a Byteknave, we set all elements of the tree in the range a _ i…b _ i to zero."

Why ?