E - 7x7x7 Editorial by en_translator
It is only the relative positions between the regions that matter, so one can fix one of the regions. Hereinafter, we fix the position of \(C_1\) at \(a_1=b_1=c_1=0\).
Now we have the following fact:
- Fact: one can impose additional constraints that \(C_1\) and \(C_i\ (i=2,3)\) has an intersection, i.e., they share a region with positive volume, edges, or vertices, without affecting the existence of the solution. In other words, if the original problem has a solution, so does it after imposing this condition.
This is because, if \(C_1\) and \(C_i\) do not have an intersection, then one can translate \(C_i\) without changing the values of \(V_1,V_2\), and \(V_3\) so that it touches \(C_1\). One may think \(C_3\) cannot be moved when \(C_1\) and \(C_2\) have an intersection, and \(C_2\) and \(C_3\) also have an intersection, but \(C_1\) and \(C_3\) do not; but in this case, one can swap \(C_1\) and \(C_2\), and translate all the cubes so that \(a_1=b_1=c_1=0\).
By this fact, one can assume that the absolute value of \(a_2,b_2,c_2,a_3,b_3,c_3\) are not greater than \(7\), which reduces the number of candidates to \(15^6 \approx 10^7\). All that is left is to, given \(a_2,b_2,c_2,a_3,b_3,c_3\), find the volume of the regions contained in exactly one, two, or three cubes.
First of all, the volume \(V(C_i \cap C_j)\) of the intersection of the cubes \(C_i\) and \(C_j\) can be found as \(\max\{0, \min\{a_i,a_j\}+7-\max\{a_i,a_j\}\} \times \max\{0, \min\{b_i,b_j\}+7-\max\{b_i,b_j\}\} \times \max\{0,\min\{c_i,c_j\}+7-\max\{c_i,c_j\}\}\), because the intersection is expressed as:
- \(\max\{a_i,a_j\}\leq x\leq \min\{a_i+7,a_j+7\}\) and
- \(\max\{b_i,b_j\}\leq y\leq \min\{b_i+7,b_j+7\}\) and
- \(\max\{c_i,c_j\}\leq z\leq \min\{c_i+7,c_j+7\}\).
Same applies to the volume \(V(C_i \cap C_j \cap C_k)\) of the intersection of three cubes \(C_i\), \(C_j\), and \(C_k\).
Next, defining \(v_i\) as the region contained in exactly \(i\) cubes, one can find \(v_1,v_2\), and \(v_3\) using the idea of inclusion-exclusion principle as follows:
- \(v_3=V(C_1\cap C_2\cap C_3)\)
- \(v_2=V(C_1\cap C_2)+V(C_1\cap C_3)+V(C_2\cap C_3)-3v_3\)
- \(v_1=3\times 7^3-2v_2-3v_3\)
Thus, one can find \(v_1,v_2,v_3\) for all candidates of \(a_2,b_2,c_2,a_3,b_3,c_3\) and check if they coincide with \(V_1,V_2,V_3\) to solve the problem.
Bonus
In fact, one can limit the range of \(a_2,b_2,c_2,a_3,b_3,c_3\) to be \([-1,7]\), which is shown experimentally. The proof and the independence of the length of the side of the cubes are unclear.
Sample code (C++):
#include<bits/stdc++.h>
using namespace std;
int f(int a1, int b1, int c1, int a2, int b2, int c2) {
int res = 1;
res *= max(0, min(a1, a2) + 7 - max(a1, a2));
res *= max(0, min(b1, b2) + 7 - max(b1, b2));
res *= max(0, min(c1, c2) + 7 - max(c1, c2));
return res;
}
int f(int a1, int b1, int c1, int a2, int b2, int c2, int a3, int b3, int c3) {
int res = 1;
res *= max(0, min({a1, a2, a3}) + 7 - max({a1, a2, a3}));
res *= max(0, min({b1, b2, b3}) + 7 - max({b1, b2, b3}));
res *= max(0, min({c1, c2, c3}) + 7 - max({c1, c2, c3}));
return res;
}
int main() {
int v1, v2, v3;
cin >> v1 >> v2 >> v3;
for (int a2 = -7; a2 <= 7; a2++) {
for (int b2 = -7; b2 <= 7; b2++) {
for (int c2 = -7; c2 <= 7; c2++) {
for (int a3 = -7; a3 <= 7; a3++) {
for (int b3 = -7; b3 <= 7; b3++) {
for (int c3 = -7; c3 <= 7; c3++) {
int nv3 = f(0, 0, 0, a2, b2, c2, a3, b3, c3);
int nv2 = f(0, 0, 0, a2, b2, c2) + f(0, 0, 0, a3, b3, c3) + f(a2, b2, c2, a3, b3, c3) -
nv3 * 3;
int nv1 = 3 * 7 * 7 * 7 - nv2 * 2 - nv3 * 3;
if (v1 != nv1 or v2 != nv2 or v3 != nv3) continue;
printf("Yes\n0 0 0 %d %d %d %d %d %d\n", a2, b2, c2, a3, b3, c3);
return 0;
}
}
}
}
}
}
cout << "No" << endl;
}
posted:
last update: