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!
Solution Sketch
Tutorial is loading...
Accepted Code
for cas in range(int(input())): print({'o': "FILIPINO", 'a': "KOREAN", 'u': "JAPANESE"}[input()[-1]])
Accepted Submission: 67015948
Solution Sketch
Tutorial is loading...
Accepted Code
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
Solution Sketch
Tutorial is loading...
Accepted Code
#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
Solution Sketch
Tutorial is loading...
Accepted Code
#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
Solution Sketch
Tutorial is loading...
Accepted Code
#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
Solution Sketch
Tutorial is loading...
Accepted Code
#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
Solution Sketch
Tutorial is loading...
Accepted Code
#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
Solution Sketch
Tutorial is loading...
Accepted Code
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
Can somebody help me why my submission to Div2 C that is Div1 A is getting TLE on test 6 when I am using similar thing as the editorial
https://codeforces.net/contest/1281/submission/66931104
I am getting TLE on test 24. Can anybody help me out? I am unable to remove TLE. https://codeforces.net/contest/1281/submission/66993181
Add an additional condition in this for loop
for (LL i = 0; i < s[p-1]-'0' - 1; ++i) {s+= sub;}to exit when the string length crosses x. This would most probably fix the TLE.Oh I completely neglected that, only should take substring when we are appending. Thanks a lot!
You are calling substr in every loop, and it works in O(n), so your solution TLEs. I changed this, and it got accepted.
Can we print the pairs? 1281E
For problem 1281F/1280D, why is 67027127 incorrect?
Explanation: this submission closes all partition at the subtree instead of open it. It tries to either union the partitions from the $$$u$$$ subtree and $$$v$$$ subtree, or merge the top partitions from subtree $$$u$$$ and $$$v$$$ together.
Here is my implementation of Div1 D, which I think is easier to understand than the one given in the editorial: 67036054
Can somebody tell me, why am I getting TLE in this? Problem C
c=s.substr(pos+1);is unnecessary whentimes==0. You are obtaining a substring, only to find out later that you have to work on it $$$0$$$ times. That's a waste. Handle this and get an $$$AC$$$.I tried my best but I am not able to understand why 67059551 for problem Div2 C gives MLE and also Why 67057569 solution for same problem is giving TLE. please help
For the TLE, I think it is because substr is linear time in the length of the string, and you are potentially calling it quite a lot. If a string is of length close to x and you keep finding the number '1', then you will delete the right half of the string, then append the right half of the string again and again and again, it could easily be quadratic time complexity. Try only appending to s (never set it equal to sleft)
Thanks for the reply man. I tried what you said but still it gives TLE. heres my 67138033 . Also Could you find reason for MLE.
When you do += on the string s it is going to make a whole new string s, maybe you can use the append method instead.
Besides that there is a bigger problem in both the TLE and MLE one. You think the if statement is checking if n<x, but in actuality, you are checking if (n mod mod) < x. Hence you are going to go into it a bunch more than you want.
You should try to make a test generator and run it on some larger test cases (random). Then you can use debug mode or print statements to notice the problem. In this case even a random large test case would have revealed it.
Thanks man. Got it
i used += and got ac at 46 ms.. https://codeforces.net/contest/1280/submission/81967475
Can someone please tell me why my submission for B is giving a WA verdict on test set 2? Here is my submission.
Never mind. I have got it. Thanks.
Can somebody help, I still haven't understood why the complexity of problem 1281F/1280D is O(n^2)
Hi! I wrote this training material for our IOI training camp earlier this year: https://drive.google.com/open?id=1nhL63QcjUiRm1pGGmzi1QHceKAGeBsRY. A proof is given in Section 4.2, "Tree convolution DP", and also in the appendix. (It is only shown for the case of binary trees, but it can be extended to general trees by looking at the binary tree of "recursive calls" instead of the actual tree.)
Hello kevinsogo, thank you for sharing this DP3 module could you please share DP1 and DP2 modules?
also in the link you shared, the proof for general trees is left as an exercise, c in f(i, m, c) simply the index of the child we are at right?
thank you!
Can Somebody help me with code of C Cut and Paste it is giving wrong answer on 108th testcase of test 6 but I can't see the testcase so unable to figure out the mistake. Thanks in Advance :) https://codeforces.net/contest/1281/submission/67296667
Hi, when you are doing
answer = (answer + (answer-i)*v)%MOD;, your answer is becoming negative and most programming languages don't know how to tackle negative modulo. Doanswer = (answer + (answer-i)*v )%MOD; answer = (answer%MOD + MOD)%MOD;and it should work fine.Why is amswer turning negative anyway? answer, (answer-i), and v should always be positive. So, (answer + (answer-i)*v ) should be positive too.
Then, when you take the MOD of a (answer + (answer-i)*v ), shouldn't that also be positive?
this is because..lets assume ur answer becomes 1000000010 and i=100, when you will take mod..answer will become 3,so in next iteration i=11,and answer<i,,,,,so answer-i will be negative
Thanks! I was having the same problem.
In Problem C : Can anyone tell me why my solution using string ( Code with string ) gives runtime error but the same code with vector of char got accepted ( Code with vector
OK this is probably a dumb question but I'm still gonna ask . In problem D , wouldn't the optimal solution be counting N the number of the nodes where the condition ( number of bees < number of wasps) holds and returning max(m-1,N) ? (In this case , we will consider ALL the nodes where the condition is false to be a single village and consider every node where the condition holds as a single village as well ) Am I missing any details ?
Not sure I understand what you meant, but the villages need to be connected subtrees, so you can't just turn any bunch of nodes into a single village.
Why can't I turn any bunch of nodes into a single village ? (By considering them to be a sub-tree)
In 1281E, Can somebody give me a bit more proof why this technique is correct for maximizing and minimizing? And hopefully links to more problems like this one.
If anyone need detail explanation of DIV2 C SEE HERE
Why this give Memory limit exceeded on test 6. on Div 2C/1A problem link. Can anyone help me out please.;)
UPD : Solved!
In Div 2 F/Div 1 D, Can anyone explain how we can get the transition that runs in O(r)? I don't see a better way than to consider all possible ways to split the r regions among this node's children, which is exponential.
why is this wrong on testcase 1 4th test?? https://codeforces.net/contest/1281/submission/87028602