I hope you enjoyed the problems! Thanks to the onsite teams and coaches who gave feedback; I'm glad the reception was positive.
Interestingly, in the onsite ICPC round, while "Kirchhoff" got several accepted solutions, "Miss Punyverse" got no accepted submissions at all! It is the reverse here. (Kirchhoff even has a trickier output format in the onsite round compared to the version presented in Codeforces.) It seems the ICPC scoreboard really affects the results greatly; what the top few teams are working on influences what everyone else will be working on.
I am planning on releasing the full, untouched ICPC Manila 2019 problem set in the gym sometime in the future, so you can see which problems you missed. The Intergalactic Sliding Puzzle is not the hardest problem in the round!
for cas in range(int(input())): print({'o': "FILIPINO", 'a': "KOREAN", 'u': "JAPANESE"}[input()[-1]])
Accepted Submission: 67015948
def solve(s, t):
mns = list(s)
for i in range(len(s)-2,-1,-1): mns[i] = min(mns[i], mns[i + 1])
for i in range(len(s)):
if s[i] != mns[i]:
j = max(j for j, v in enumerate(s[i:], i) if v == mns[i])
s = s[:i] + s[j] + s[i+1:j] + s[i] + s[j+1:]
break
return s if s < t else '---'
for cas in range(int(input())):
print(solve(*input().split()))
Accepted Submission: 67049609
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr ll mod = 1'000'000'007; //'
constexpr int N = 1111;
char _s[N];
ll solve() {
int x;
scanf("%d%s", &x, _s);
ll ls = strlen(_s);
vector<char> s(_s, _s + ls);
for (int i = 1; i <= x; i++) {
int v = s[i - 1] - '1';
if (s.size() < x) {
vector<char> sub(s.begin() + i, s.end());
for (int it = 0; it < v; it++) s.insert(s.end(), sub.begin(), sub.end());
}
ls = (ls + (ls - i) * v) % mod;
}
return ls;
}
int main() {
int z;
for (scanf("%d", &z); z--; printf("%lld\n", (solve() % mod + mod) % mod));
}
Accepted Submission: 67016113
#include <bits/stdc++.h>
using namespace std;
int solve(int r, int c, vector<string> grid) {
vector<int> rows(r), cols(c);
int total = 0;
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
if (grid[i][j] == 'A') rows[i]++, cols[j]++, total++;
}
}
if (total == r * c) return 0;
if (total == 0) return -1;
if (rows[0] == c || rows.back() == c || cols[0] == r || cols.back() == r) return 1;
if (grid[0][0] == 'A' || grid[0].back() == 'A' || grid.back()[0] == 'A' || grid.back().back() == 'A') return 2;
if (*max_element(rows.begin(), rows.end()) == c || *max_element(cols.begin(), cols.end()) == r) return 2;
if (rows[0] || rows.back() || cols[0] || cols.back()) return 3;
return 4;
}
int main() {
int z;
for (cin >> z; z--;) {
int r, c;
cin >> r >> c;
vector<string> grid(r);
for (int i = 0; i < r; i++) cin >> grid[i];
int res = solve(r, c, grid);
(~res ? cout << res : cout << "MORTAL") << '\n';
}
}
Accepted Submission: 67016167
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void solve() {
int n;
cin >> n;
n <<= 1;
vector<vector<pair<int,ll>>> adj(n);
for (int i = 0; i < n - 1; i++) {
int a, b; ll c;
cin >> a >> b >> c;
a--, b--;
adj[a].emplace_back(b, c);
adj[b].emplace_back(a, c);
}
vector<int> parent(n, -1), que(1, 0);
vector<ll> parent_cost(n);
parent[0] = 0;
for (int f = 0; f < que.size(); f++) {
int i = que[f];
for (auto [j, c]: adj[i]) {
if (parent[j] == -1) {
parent[j] = i;
parent_cost[j] = c;
que.push_back(j);
}
}
}
vector<int> size(n, 1);
ll mn = 0, mx = 0;
reverse(que.begin(), que.end());
for (int i : que) {
size[parent[i]] += size[i];
mx += parent_cost[i] * min(size[i], n - size[i]);
mn += parent_cost[i] * (size[i] & 1);
}
cout << mn << " " << mx << '\n';
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int z;
for (cin >> z; z--; solve());
}
Accepted Submission: 67020743
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Group {
int win; ll adv;
Group(int win = -1, ll adv = 0): win(win), adv(adv) {}
Group operator+(const Group& o) const {
return Group(win + o.win, adv + o.adv);
}
Group operator+() const {
return Group(win + (adv > 0));
}
bool operator<(const Group& o) const {
return win < o.win || win == o.win && adv < o.adv;
}
};
vector<Group> convolve(const vector<Group>& fa, const vector<Group>& fb) {
vector<Group> fi(fa.size() + fb.size());
for (int a = 0; a < fa.size(); a++) {
for (int b = 0; b < fb.size(); b++) {
fi[a + b ] = max(fi[a + b ], fa[a] + fb[b]);
fi[a + b + 1] = max(fi[a + b + 1], fa[a] + +fb[b]);
}
}
return fi;
}
vector<vector<Group>> f;
vector<vector<int>> adj;
void convolve_tree(int i, int p = -1) {
for (int j : adj[i]) {
if (j == p) continue;
convolve_tree(j, i);
f[i] = convolve(f[i], f[j]);
}
}
int solve() {
int n, m;
scanf("%d%d", &n, &m);
f = vector<vector<Group>>(n, vector<Group>(1, Group(0)));
for (int i = 0, b; i < n; i++) {
scanf("%d", &b);
f[i][0].adv -= b;
}
for (int i = 0, w; i < n; i++) {
scanf("%d", &w);
f[i][0].adv += w;
}
adj = vector<vector<int>>(n);
for (int i = 1; i < n; i++) {
int x, y;
scanf("%d%d", &x, &y);
x--, y--;
adj[x].push_back(y);
adj[y].push_back(x);
}
convolve_tree(0);
return (+f[0][m - 1]).win;
}
int main() {
int z;
for (scanf("%d", &z); z--; printf("%d\n", solve()));
}
Accepted Submission: 67016189
1280E - Kirchhoff's Current Loss
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1LL << 60;
class Circuit {
public:
ll w = -1;
ll width() {
if (w == -1) compute_width();
return w;
}
virtual void compute_width() {}
virtual void assign(ll value) {}
virtual ostream& write_to(ostream& os) const { return os; }
void assign_minimal(ll value) { assign(value * width()); }
friend ostream& operator<<(ostream& os, const Circuit& circuit);
};
ostream& operator<<(ostream& os, const Circuit& circuit) {
return circuit.write_to(os);
}
class Resistor: public Circuit {
public:
ll value = -1;
Resistor() {}
void compute_width() override {
w = 1;
}
void assign(ll value) override {
this->value = value;
}
ostream& write_to(ostream& os) const override {
return os << ' ' << value;
}
};
class Join: public Circuit {
public:
char typ;
vector<Circuit*> children;
Join() {}
void compute_width() override {
w = typ == 'S' ? INF : 0;
for (auto child: children) {
ll ww = child->width();
w = typ == 'S' ? min(w, ww) : w + ww;
}
}
void assign(ll value) override {
for (auto child: children) {
if (typ == 'S') {
if (child->width() == width()) {
child->assign(value);
value = 0;
} else {
child->assign(0);
}
} else {
child->assign(value);
}
}
}
ostream& write_to(ostream& os) const override {
for (auto child: children) os << *child;
return os;
}
};
class CircuitParser {
const string& s;
int i = 0;
CircuitParser(const string& s): s(s) {}
Circuit *parse() {
if (s[i++] == '(') {
Join *j = new Join();
while (true) {
j->children.push_back(parse());
if (s[i++] == ')') break;
j->typ = s[i++];
i++;
}
return j;
} else {
return new Resistor();
}
}
public:
static Circuit *parse(const string& s) {
return CircuitParser(s).parse();
}
};
void solve(ll a, const string& s) {
Circuit *c = CircuitParser::parse(s);
c->assign_minimal(a);
cout << "REVOLTING" << *c << '\n';
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int z;
for (cin >> z; z--;) {
ll a;
string s;
cin >> a;
getline(cin, s);
assert(s[0] == ' ');
solve(a, s.substr(1));
}
}
Accepted Submission: 67016199
1280F - Intergalactic Sliding Puzzle
def solve(k, grid):
seek = *range(2*k + 2), *range(4*k + 1, 2*k + 1, -1)
flat = [seek[v] for v in grid[0] + grid[1][::-1] if v]
m = {
'L': 'l'*2*k + 'u' + 'r'*2*k + 'd',
'R': 'u' + 'l'*2*k + 'd' + 'r'*2*k,
'C': 'l'*k + 'u' + 'r'*k + 'd',
'D': 'CC' + 'R'*(2*k + 1) + 'CC' + 'R'*(2*k + 2),
'F': 'R'*(k - 1) + 'DD' + 'R'*(2*k + 1) + 'D' + 'L'*2*k + 'DD' + 'L'*k,
'G': 'FF',
}
[(i, j)] = [(i, j) for i in range(2) for j in range(2*k + 1) if grid[i][j] == 0]
st = 'r'*(2*k - j) + 'd'*(1 - i)
for v in range(2, 4*k + 2):
ct = flat.index(v)
if ct >= 2:
st += 'L'*(ct - 2) + 'GR'*(ct - 2) + 'G'
flat = flat[ct - 1: ct + 1] + flat[:ct - 1] + flat[ct + 1:]
if ct >= 1:
st += 'G'
flat = flat[1:3] + flat[:1] + flat[3:]
st += 'L'
flat = flat[1:] + flat[:1]
if flat[0] == 1: return st, m
def main():
def get_line():
return [0 if x == 'E' else int(x) for x in input().split()]
for cas in range(int(input())):
res = solve(int(input()), [get_line() for i in range(2)])
if res is None:
print('SURGERY FAILED')
else:
print('SURGERY COMPLETE')
st, m = res
print(st)
for shortcut in m.items(): print(*shortcut)
print('DONE')
main()
Accepted Submission: 67026155