Since the 2018-2019 ACM-ICPC Brazil Subregional Contest doesn't have an Official Editorial, I propose that we make an "Community Editorial".
B — Nim
We can think of every position [i, 0], [0, i], [i, i] as "insta-winning" positions. To model so, we can give them a very high Grundy number, so they doesn't conflict with any other possible Grundy number. That way, the cells that can only move you to an "insta-winning" cell, recieve an Grundy number of 0, meaning that they are losing positions.
After that, we can preprocess all possible positions and get it's Grundy number.
The final answer is just the nim-sum of every starting ball.
Accepted code#include <bits/stdc++.h>
using namespace std;
int main()
{
int estados[101][101] = {};
bool apareceu[1000] = {};
auto mex = [&](int di, int dj)
{
memset(apareceu, 0, sizeof(apareceu));
for(int i = 0; i < di; i++)
apareceu[estados[i][dj]] = true;
for(int j = 0; j < dj; j++)
apareceu[estados[di][j]] = true;
int mini = min(di, dj);
for(int i = 1; i <= mini; i++)
apareceu[estados[di - i][dj - i]] = true;
for(int i = 0; i < 1000; i++)
if(!apareceu[i])
return i;
};
estados[0][0] = 999;
for(int i = 1; i <= 100; i++)
estados[i][0] = estados[0][i] = estados[i][i] = 999;
for(int i = 1; i <= 100; i++)
{
for(int j = 1; j <= 100; j++)
{
if(i != j)
estados[i][j] = mex(i, j);
}
}
int n, v = 0, a, b;
cin >> n;
while(n--)
{
cin >> a >> b;
if(estados[a][b] == 999)
{
cout << "Y" << endl;
return 0;
}
v ^= estados[a][b];
}
cout << (v == 0 ? "N" : "Y") << endl;
}
C — Sweep line
To make things easier, we can think of every cut as an straight line. First, we need to observe two things:
- Every line splits an area into two new areas.
- Every line intersection splits an area into two new areas.
Then, the answer must be h + v lines from the first observation + h * v lines from the second observation (every vertical line intersects with every horizontal line) + the number of intersections of lines in the same orientation.
It's easy to see that lines of the same orientation can only intersects if (starti < startj and endi > endj) or (starti > startj and endi < endj).
One fast way to count how many times the above is true is to use an sweep line (from left to right, bottom to top, etc).
Accepted code#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<
int,
null_type,
greater<int>,
rb_tree_tag,
tree_order_statistics_node_update>
statisticsTree;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
long long h, v;
cin >> h >> v >> h >> v;
vector<pair<int, int>> horizontais(h), verticais(v);
for(auto &it : horizontais)
cin >> it.first >> it.second;
sort(horizontais.begin(), horizontais.end());
for(auto &it : verticais)
cin >> it.first >> it.second;
sort(verticais.begin(), verticais.end());
long long r = (h + 1) * (v + 1);
statisticsTree th, tv;
for(auto &it : horizontais)
{
r += th.order_of_key(it.second);
th.insert(it.second);
}
for(auto &it : verticais)
{
r += tv.order_of_key(it.second);
tv.insert(it.second);
}
cout << r << endl;
}
D — Ad hoc
Just count the number of numbers ! = 1
Accepted code#include <bits/stdc++.h>
using namespace std;
int main()
{
int n, r = 0, e;
cin >> n;
while(n--)
cin >> e, r += (e != 1);
cout << r << endl;
}
E — String
Just follow the statement.
Accepted code#include <bits/stdc++.h>
using namespace std;
int main()
{
string entrada, crib;
int r = 0;
cin >> entrada >> crib;
int lim = entrada.size() - crib.size() + 1;
for(int shift = 0; shift < lim; shift++)
{
for(int i = 0; i < crib.size(); i++)
if(entrada[shift + i] == crib[i])
goto next;
r++;
next:;
}
cout << r << endl;
}
F — DP
We can model the problem with the following indexes: The stages that we've already seen and the current time.
Since there are at maximum 10 stages, we can store the first index in a bitmask.
Then, we can apply the following recurrence:
dp[0][0] = 0;
for(i : possibleBitmasks)
dp[i][0] = -infinity
for(j : [1, 86400])
for(i : possibleBitmasks)
dp[i][j] = max(dp[i][j], dp[i][j - 1]) // watch nothing
for(k : [0, number of stages - 1])
if(i & (1 << k)) // the bit k is on
for(s : stages[k].shows)
if(s.endTime == j)
dp[i][j] = max(dp[i][j],
max(dp[i][s.initTime] + s.songs, // been on this stage before
dp[i ^ (1 << k)][s.initTime] + s.songs)) // first time on this stage
But it's not fast enought :(
To fix it, "skip" to the relevant moments (aka, the end time or the start time of an show) and calculate only the values of the relevant moments.
Accepted code#include <bits/stdc++.h>
using namespace std;
struct show
{
int i, f, o;
bool operator<(const show &a) const
{
return f < a.f;
}
};
vector<pair<int, int>> pd[(1 << 10) + 1];
int main()
{
vector<vector<show>> shows;
int n, m;
cin >> n;
shows.resize(n);
vector<pair<int, int>> events;
for(int i = 0; i < n; i++)
{
cin >> m;
shows[i].resize(m);
for(auto &it : shows[i])
cin >> it.i >> it.f >> it.o, events.emplace_back(it.f, i);
sort(shows[i].rbegin(), shows[i].rend());
}
sort(events.rbegin(), events.rend());
int maxi = (1 << n);
pd[0].emplace_back(0, 0);
while(events.size())
{
int k = events.back().second;
events.pop_back();
for(int i = 1; i < maxi; i++)
{
if((i & (1 << k)) == 0)
continue;
auto &shw = shows[k].back();
int r = -(1 << 30);
if(pd[i].size())
for(auto &it : pd[i])
if(it.first <= shw.i)
r = max(r, it.second + shw.o);
if(pd[i ^ (1 << k)].size())
for(auto &it : pd[i ^ (1 << k)])
if(it.first <= shw.i)
r = max(r, it.second + shw.o);
if(r != -(1 << 30))
pd[i].emplace_back(shw.f, r);
}
shows[k].pop_back();
}
int r = -(1 << 30);
if(pd[maxi - 1].size())
for(auto &it : pd[maxi - 1])
r = max(r, it.second);
cout << (r < 0 ? -1 : r) << endl;
}
I — Ad hoc
We can think of the lights as "bits" in an bitset, and the light switches as xor operations. After that, it's kinda easy to notice that we'll cicle through all possible values after 2 * M operations.
Then, we just simulate what is described in the statement (with an limit of 2 * M operations) and print the result.
Accepted code#include <bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
bitset<1000> inicial;
int n, m, l, e, r;
cin >> m >> n >> l;
vector<bitset<1000>> interruptores(m);
while(l--)
cin >> e, inicial[e - 1] = 1;
for(auto &it : interruptores)
{
cin >> l;
while(l--)
cin >> e, it[e - 1] = 1;
}
int lim = 2 * m;
for(r = 0; r < lim; r++)
{
inicial ^= interruptores[r % m];
if(inicial.none())
break;
}
cout << (r != lim ? r + 1 : -1) << endl;
}