November 16, 2018 TCO Semifinals 2 Editorial

The competitors of this round are _aid, jcvb, Kankuro, kcm1700, krijgertje, ksun48, Petr, and qwerty787788. The easy is a tricky greedy problem that is easy to get wrong because of cases that need to be carefully considered. The medium is a constructive problem that is hard to analyze at first but has some solutions that are both easy to implement and verify. The last is a very tricky constructive problem that has a lot of small incremental steps that contestants can make progress on, but getting a full solution that covers all cases is hard.
Congratulations to the advancers:

1. qwerty787788
2. ksun48
3. Petr
4. _aid

NextLuckyNumber (misof):

In this problem, we are given integers N,K,d, and we want to find the smallest integer M such that M > N and M has exactly K occurences of the digit d.
There are two main cases to be aware of, if d is zero, or d is nonzero.
Let’s first construct the smallest number that consists of exactly k occurrences of the digit d. This is just the number ddd…d (k times), except for when d is zero, in which case we can prepend the number with a 1. We can check if this smallest number is strictly bigger than N, and if so, we can return it.
Now, let’s try to see if we can get an answer that is the same length as N. We can try all possibilities of the length of the common prefix (i.e., number of most significant digits they share), then all possibilities for the next digit in the new number. Once those are fixed, we have the guarantee that the new number is bigger and we can greedily fill in the missing digits (i.e with 0s and the number of ds needed if d is nonzero, otherwise, with 1s and the number of 0s we need). If we iterate from longest common prefix to shortest, and increment the next number from smallest to largest, we guarantee we are iterating through candidates in increasing order so we can greedily return the first one that we can feasibly fill.
If none of these options work, then M must have more digits than N. Since we already handled the first case earlier, we know that M must be longer than N by exactly one digit. We can start M with 1 and greedily fill in the rest (using a similar strategy to the second case).
An implementation is shown below:

class NextLuckyNumber:
	def getTicket(self, lastTicket, age, digit):
		lo = str(digit) * age
		if digit == 0:
			lo = "1" + lo
		if int(lo) > lastTicket:
			return lo
		s = str(lastTicket)
		for prefix in range(len(s)-1, -1, -1):
			have = s[:prefix].count(str(digit))
			for bdig in range(int(s[prefix])+1, 10):
				nhave = have + int(bdig == digit)
				if nhave <= age and nhave + len(s)-1-prefix >= age:
					need = max(0, age - nhave)
					rem = len(s) - 1 - prefix
					if digit == 0:
						return s[:prefix] + str(bdig) + "0" * need + "1" * (rem - need)
					return s[:prefix] + str(bdig) + "0" * (rem - need) + str(digit) * need
		if digit == 0:
			return int("1" + "0" * age + "1" * (len(s) - age))
		return int("1" + "0" * (len(s) - age + int(digit == 1)) + str(digit) * (age - int(digit == 1)))

VennDiagrams (misof):

In this problem, we want to construct a Venn diagram with n different categories: a drawing in which each intersection of categories corresponds to some nice connected area.
Drawing the smallest Venn diagram is surprisingly hard, but in this problem we have a lot of freedom, so we can come up with a construction that will be easy to implement. If you could do any dimension rectangle, one easy 2-approximation algorithm is to construct a 2 x (2^n) bitmap where the first row is {0,1,2,…,2^n – 2,2^n – 1} and the second row is full of (2^n – 1). All exact intersections of sets correspond to pixels in the first row (and to the entire bottom row), while each superset of sets contains the entire second row and some subset of the first row so it looks like a comb.
When we have to fit our solution into a 50×50 matrix, all we need is to be a bit more creative
with the shape of the “backbone”.
In the solution below, we have the following pattern for the (2^n – 1) cells:

*..........
***********
*..........
*..........
*..........
***********
*..........
*..........
*..........
***********
*..........

(full left column + full rows that are 4 apart) Remember that this pattern will be put on an infinite 2d grid with all zeros, so the zero cells are still connected.
This leaves plenty of room to attach all the other 1-pixel sets and to make sure that they
can’t form holes.
There are better constructions in terms of guaranteed approximation ratio but the constraints
were loose enough so those were not needed.

class VennDiagrams:
	def construct(self,N):
		ret = [[0 for __ in xrange(50)] for ___ in xrange(50)]
		tot = (1 << N) - 1
		for i in xrange(50):
			ret[i][0] = tot
		for i in xrange(0,50,4):
			for j in xrange(0,50):
				ret[i][j] = tot
		cnt = 0
		for i in xrange(1,50,2):
			for j in xrange(1,50):
				ret[i][j] = 0 if cnt >= (1 << N) else cnt
				cnt += 1
		ans = [50,50]
		for i in xrange(50):
			ans += ret[i]
		return ans

RearrangingBoxes (monsoon):

You originally have A x B x H cubes arranged in a cuboid with A rows, B columns, and H height. You would like to remove K of them so that the resulting arrangement is still connected and has the same surface area as the original cuboid (i.e. S = 2(AB + AH + BH)). Each cube’s bottom face must also touch the ground or another cube directly.
The idea is that we start from the A x B x H cuboid and we iteratively remove cubes from it, at all times maintaining the constant surface area S = 2(AB + AH + BH). Assume wlog that A ≤ B.
First of all observe that in theory the minimal volume we can achieve is (in particular if S – 2 is divisible by 4 it is achieved by a cuboid of size ).
It will turn out that we can obtain this minimum satisfying the task constraints (that is the solid must be formed from towers in a limited space), except for special case when A = 1 and B is even (it can be shown that then ).
The rough idea is simple: if we treat the solid as a graph (cubes are vertices, and two vertices are connected by an edge if corresponding cubes share a face), then we achieve minimal volume not only for a line graph of size , but also for any tree of size .
Thus if then there is no solution. Otherwise, we will proceed removing cubes.
Observe that removing one cube containing exactly one vertex of the cuboid reduces volume by 1 and does not change surface area. In fact, in the same way we can remove from the cuboid a cuboid of size (A – 1) x (B – 1) x (H – 1), removing cubes one by one in layers. This leaves us “floor” of size A x B and two “walls” of total size (A + B – 1) x (H – 1).
Next observe that we can remove a wall cube that has three neighbors (again this does not change surface area). Thus we can totally remove towers of size H – 1
from the walls (we just remove every second tower). So if A + B – 1 is odd, every tower is connected only to the floor. (We deal with A + B – 1 even later).
Next we can do the same idea with (A – 1) x (B – 1) part of the floor, by removing segments of length B – 1. If A – 1 is even we are done: the remaining cubes form a tree graph, so the volume is in fact minimal (equal to ).
If A – 1 is even but B – 1 is odd we can do symmetric thing
(see left picture below with A = 5, B = 7, where we observe the warehouse from the top, light gray cells denote towers of height 1, dark gray cells denote towers of height H).
If A – 1 and B – 1 are odd, we can create an almost tree like in the right
picture below (almost tree is the best we can get here, since A and B are even,
thus S is divisible by 4):

In this picture, the dark squares are towers of height H, the gray squares are towers of height 1, and the white squares are towers of height 0.
So the only case left is what to do with two towers of size H next to each other when A + B – 1 is even.
If A = B (and thus B is even) we cannot do anything (thus this is the special case of greater we have mentioned before).
Otherwise wlog let’s assume that B is even and we have a following picture (with A = B, B = 4) where two towers of height H are next to each other:

Call these two towers T_L (left) and T_R (right). If A ≥ 5 or B & ge; 4 we have at least one tower (call it T) of height 1 which does not have a neighboring tower of height H.
If we remove two cubes from T_R and add one cube to T, the volume reduces by 1, and the surface area doesn’t change.
If this leaves T_R of size 2, then it means that was even, thus S divisible by 4 and we are done. This needs special treatment for A = 3 and B = 2, but it also can be done.
Time complexity of the algorithm is O(AB).
Sample code:

public class RearrangingBoxes {
public int[] rearrange(int A, int B, int H, long K) {
  long V = (long)A*B*H;
  boolean swapped = false;
  if (A > B) {
    int temp = A;
    A = B;
    B = temp;
    swapped = true;
  }
  long Area = 2*((long)A*B + (long)A*H + (long)B*H);
  long minV = ((Area-2) + 2)/4;
  if (A == 1 && B%2 == 0) {
    minV += (H-1)/2;
  }
  if (V-K < minV) { return new int[0]; }
  int[][] sol = new int[A][B];
  for (int a=0; a<A; ++a) {
    for (int b=0; b<B; ++b) {
      sol[a][b] = H;
    }
  }
  if (A > 1) {
    long w = Math.min(H-1, K / ((A-1)*(B-1)));
    for (int a=0; a<A-1; ++a) {
      for (int b=0; b<B-1; ++b) {
        sol[a+1][b+1] -= w;
      }
    }
    K -= (A-1)*(B-1)*w;
    if (w < H-1) {
      for (int a=A-2; a>=0 && K > 0; --a) {
        for (int b=B-2; b>=0 && K > 0; --b) {
          sol[a+1][b+1]--; K--;
        }
      }
    }
  }
  int cols = (A+B-2)/2;
  for (int i=0; i<cols && K > 0; ++i) {
    long ile = Math.min(H-1, K); K -= ile;
    int a = i<A/2 ? A-2-2*i : 0;
    int b = i<A/2 ? 0 : 2*(i-A/2)+1+(A+1)%2;
    sol[a][b] -= ile;
  }
  cols = (B-1)/2;
  for (int i=0; i<cols && K > 0; ++i) {
    long ile = Math.min(A-1, K); K -= ile;
    for (int j=0; j<ile; ++j) { sol[A-1-j][1+2*i]--; }
  }
  if (B%2 == 0) {
    int rows = (A-1)/2;
    for (int i=0; i<rows && K > 0; ++i) {
      sol[1+2*i][B-1]--; K--;
    }
  }
  if (A == 2 && (A+B-1)%2 == 0) {
    if (K > 0) {
      assert(sol[0][B-1] == H);
      if ((H-1)%2 == 1) {
        if (B >= 5) {
          sol[1][B-3]--;
          sol[1][B-4]++;
          sol[0][B-1]--;
          sol[1][B-1]++;
        } else {
          assert(B == 3);
          sol[0][0]--;
          sol[0][B-1]--;
          sol[1][1]++;
          sol[1][B-1]++;
        }
      }
      int ile = (sol[0][B-1]-1) / 2;
      sol[0][B-1] -= ile;
      sol[1][B-1] += ile;
      for (int i=0; i < ile && K > 0; ++i) {
        sol[0][B-1]--; K--;
      }
    }
  } else if (A >= 3 && (A+B-1)%2 == 0) {
    int ile = (sol[0][B-1]-1) / 2;
    for (int i=0; i < ile && K > 0; ++i) {
      sol[0][B-1] -= 2; sol[A-1][B-1]++; K--;
    }
  } else {
    assert(K==0);
  }
  int[] answer = new int[A*B];
  for (int i=0; i<A*B; ++i) {
    answer[i] = swapped ? sol[i%A][i/A] : sol[i/B][i%B];
  }
  return answer;
}
};