PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: iceknight1093
Tester: raysh07
Editorialist: iceknight1093
DIFFICULTY:
Easy
PREREQUISITES:
None
PROBLEM:
Given a binary string of length N, construct any binary grid of N columns and K \le \left\lceil\frac{3N}{2}\right\rceil rows such that the following is true:
- For any i such that S_i = 1, placing a golf ball at (1, 1) and repeatedly hitting it right with a strength of i along with letting it fall (with both parts being stopped by either grid borders or blocked cells) results in the ball eventually reaching (K, N).
- For any i such that S_i = 0, repeating the above process results in the ball not reaching (K, N).
EXPLANATION:
Let’s figure out when some binary string S can possibly be valid (in terms of saying which hitting powers are valid.)
First, note that since the grid has N columns but we start at (1, 1), powers of N and N-1 are in fact equivalent (since we can’t move N columns right anyway.)
So, we must certainly have S_N = S_{N-1}.
Next, suppose S_{N-1} = 1, i.e. a power of N-1 can reach the goal.
Then, we must have S_{N-2} = 1 as well!
To see why:
- First, suppose the first row has at least one blocked cell.
Then, note that powers N-1 and N-2 become equivalent since they’ll both stop just to the left of this blocked cell, and then there are \le N-1 columns remaining so moves with power \ge N-2 are all equivalent.
(The one exception is if (1, 2) is blocked; but in that case the ball falls straight down anyway and we can just pretend some prefix of rows doesn’t exist and repeat the argument.) - Otherwise, the first row has no blocked cells. Then, power N-1 will go all the way to (1, N) and then fall down.
However, the only way it can reach (K, N) is if none of the cells in the N-th column are blocked.
But if this is the case, power N-2 will end up somewhere in column N-1 on its first move, and then can always move one step right and fall down afterwards; hence also reaching (K, N).
We thus have two necessary conditions: S_N = S_{N-1} and S_{N-1} = 1 \implies S_{N-2} = 1.
These conditions are also sufficient for N \ge 4.
The proof of this is via construction.
First, let’s consider a simple construction that uses about 2N rows.
We’ll work on separating out what happens for each i = 1, 2, 3, \ldots, N-1.
Let’s have 2N rows, and for each i \in [1, N-1], block the cell (2N+2-2\cdot i, i+1).
That is, we’re blocking cells (2N, 2), (2N-2, 3), (2N-4, 4), \ldots, (4, N).
This forms a sort of “staircase” structure, just with a gap of 2.
Observe now that for each i, hitting the ball with power i will make it land just above the blocked cell in the (i+1)-th column.
Now, if we don’t block any further cells, note that the ball will always end up at (2N, N) since there’s nothing to block it from any of these stopping points.
(The exception is cell (4, N) being blocked for power N-1, in which case we’ll have to unblock it and let the ball fall down instead; this is fine since it doesn’t affect the other powers anyway.)
Now, if we want to block power i from reaching the end, we can simply also block the cell (2N+1-2\cdot i, i+1) instead, i.e. block one extra cell in the (i+1)-th column that’s just above the initially blocked cell.
For example, if we want to prevent power 1, we block (2N, 2) and (2N-1, 2).
This will cause the ball to land on cell (2N-2\cdot i, i+1) when hit with power i. However, cell (2N-2\cdot i, i+2) is already blocked in the next column (it’s the initially blocked cell in that column, after all), so the ball can’t move any further!
To optimize the above construction to use fewer rows, we can try being a little less wasteful, and combine constructions of adjacent columns.
We’ll still keep the same idea of: if a power is to be blocked it will be immediately after the first move.
First, let K = \left\lceil \frac{3N}{2} \right\rceil denote the number of rows; this we will fix.
Let’s iterate through powers 1, 2, 3, \ldots, N-1 in order.
Let (x_i, y_i) denote where the ball will land after the first move of power i, under the current construction.
Initially, nothing is blocked, so (x_1, y_1) = (K, 2).
We can then do the following at power i:
- Suppose power i is to be blocked.
Simply block cell (x_i, y_i+1) immediately.
Then, set (x_{i+1}, y_{i+1}) = (x_i-1, y_i+1) since with power i+1, the ball will fall on top of the cell we just blocked.
Note that this “uses up” only one row. - Suppose power i is not to be blocked.
Then, our next move depends on power i+1 instead.- If power i+1 also doesn’t need to be blocked, we block cell (x_i+1, y_i+1) (the cell to our bottom-right).
This will cause power i+1 to fall to our right, i.e. (x_{i+1}, y_{i+1}) = (x_i, y_i+1).
Note that this doesn’t use up any extra rows. - If power i+1 does need to be blocked, we instead block cell (x_i-1, y_i+1), i.e. the cell to our upper-right.
This ensures we have free passage to our right; while the next power will instead land on top of the cell we just blocked. Thus, (x_{i+1}, y_{i+1}) = (x_{i}-2, y_i+1).
Note that this uses up two extra rows.
- If power i+1 also doesn’t need to be blocked, we block cell (x_i+1, y_i+1) (the cell to our bottom-right).
Now, let’s count the number of moves used in the worst case.
The last case, of using two extra rows, happens only when we move from some S_i = 1 to S_{i+1} = 0.
This can only happen \le \frac{N}{2} times in total; suppose it happens x times.
For the remaining N-1-x indices, the worst we can do is the first case which adds one row.
So, the number of rows needed is 1 + 2\cdot x + N-1-x= N-1+x at worst (the first 1 is because we start with one row and then each operation adds rows.)
However, x \le \frac{N}{2}, so this is bounded above by \frac{3N}{2} as we desired!
TIME COMPLEXITY:
\mathcal{O}(N^2) per testcase.
CODE:
Tester's code (C++)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
void Solve()
{
int n; cin >> n;
string s; cin >> s;
int k = (3 * n + 1) / 2;
vector<vector<int>> ans(k, vector<int>(n, 0));
if (s[n - 1] != s[n - 2]){
cout << -1 << "\n";
return;
}
if (s[n - 1] == '1' && s[n - 3] == '0'){
cout << -1 << "\n";
return;
}
int r = k - 1;
int c = 1;
for (int i = 0; i < n - 1; i++){
r--;
if (s[i] == '0' && i > 0 && s[i - 1] == '1'){
r--;
}
if (s[i] == '0' || (i > 0 && s[i - 1] == '0')){
ans[r][c] = 1;
}
c++;
}
cout << k << "\n";
for (int i = 0; i < k; i++){
for (int j = 0; j < n; j++){
if (ans[i][j]) cout << "1";
else cout << "0";
}
cout << "\n";
}
}
int32_t main()
{
auto begin = std::chrono::high_resolution_clock::now();
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
// freopen("in", "r", stdin);
// freopen("out", "w", stdout);
cin >> t;
for(int i = 1; i <= t; i++)
{
//cout << "Case #" << i << ": ";
Solve();
}
auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
return 0;
}