### Lewin's blog

By Lewin, history, 3 years ago,

Several hours later, it will be available as an open cup round as the Grand Prix of America (start time here). Please only participate in one of them, and don't discuss problems here until after the open cup round has ended.

The deadline to register for the contest on Kattis is March 21st. You will need an ICPC account to register (you can see instructions in the link above on how to create one if needed).

You can see some past years' problems here: 2017, 2016

UPD 2: Contests are over

• +49

 » 3 years ago, # | ← Rev. 2 →   +24 G seems to be a problem related to matroid intersection.How to solve it? Edit : I figure out how to solve it after reading the author's solution. SpoilerDual matroid, and remove edges one by one.
 » 3 years ago, # |   +19 How to solve B and J ?
•  » » 3 years ago, # ^ |   +33 B: "Degree sequences" is a big hint.
•  » » » 3 years ago, # ^ |   0 This problem is also (almost) an old POI problem: https://main.edu.pl/en/archive/oi/18/kon
•  » » 3 years ago, # ^ |   +10 J: The graph must be a cactus for possible solutions. Then it's a DP problem on a cactus.
 » 3 years ago, # |   0 I: I had to optimize my O(NM) solution (and still it takes 1.8s). Is there something faster?
•  » » 3 years ago, # ^ |   +20 You can speed up to N+M**2 if you can multiply polynomial by constant in O(1).
•  » » 3 years ago, # ^ |   0 I wasted 90min in problem I and still cannot solve :(
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 Here is O(NM) solition, which doesn't seems too optimized for me, and works for 0.5s solutionvector> g; vector red; vector dfs(int v) { vector ans; ans.resize(1); ans[0] = 1; for (int u : g[v]) { vector r = dfs(u); int nmx = ans.size() + r.size() - 1; vector nans(nmx); for (int i = 0; i < (int) ans.size(); i++) { for (int j = 0; j < (int) r.size(); j++) { add(nans[i + j], mul(ans[i], r[j])); } } ans = nans; } if (red[v]) { if (ans.size() < 2) ans.resize(2); add(ans[1], 1); } else { if (ans.size() < 1) ans.resize(1); add(ans[0], 1); } return ans; } int main() { int n, m; while (scanf("%d%d", &n, &m) == 2) { g = vector>(n); for (int i = 1; i < n; i++) { int p; scanf("%d", &p); --p; g[p].push_back(i); } red = vector(n); for (int i = 0; i < m; i++) { int r; scanf("%d", &r); --r; red[r] = true; } vector r = dfs(0); while (r.size() <= m) r.push_back(0); for (int i = 0; i <= m; i++) { printf("%d\n", r[i]); } } return 0; } 
 » 3 years ago, # |   +8 C ?
•  » » 3 years ago, # ^ |   +13 Do operations in reverse. Then i-th operation xors segment of length i.
•  » » » 3 years ago, # ^ |   -14 How to solve after that ?
•  » » » » 3 years ago, # ^ |   +8 Do the bitmask dp. dpi, msk is 1 iff after i operations we can get the mask msk. The answer is not more than n, so it works in O(2nn2).
 » 3 years ago, # |   +46 As I see, author solution on F is O(n+m). Problem can be solved in O(log^3) (or probably, log^2). The idea is follwing. We can find a number of points below passing through point (x, y) in O(logn) time. This can be done by Euclid-like approach. We want to find a first direction (i.e irreducibly p, q), such that number of point below p/q is less then number we need. To do that, we can go down by Stern–Brocot treeFormally, that means that we have (p1/q1 which is lower bound for our direction, and p2/q2 to upper bound). Initially, 0/1 and 1/0 are them. If (p1+p2)/(q1+q2) is too far, p1/q1 is answer, because there is no numbers between them. If not, we can change one of bounds to it. Although we have linear number of steps, we have O(logn) number of "turns", that is positions, where we change different bound with previous one. Number of steps before next turn, can be found using binary search. If do so, O(log^2) times of solving "points under line" problem needed. solution// number of (x, y) : (0 <= x < n && 0 < y < k/d x + b/d) ll count_solve(ll n, ll k, ll b, ll d) { if (k == 0) { return (b / d) * n; } if (k >= d || b >= d) { return ((k / d) * (n - 1) + 2 * (b / d)) * n / 2 + count_solve(n, k % d, b % d, d); } return count_solve((k * n + b) / d, d, (k * n + b) % d, k); } ll count_under_smart(ll n, ll m, ll p, ll q) { if (q == 0) return 0; if (p == 0) return n * m - n; assert(__gcd(p, q) == 1); ll on_diag = min((m - 1) / p, (n - 1) / q); if (p * (n - 1) >= q * (m - 1)) { return count_solve(m, q, 0, p) + m - 1 - on_diag; } else { ll r = count_under_smart(m, n, q, p); return n * m - r - on_diag - 1; } } ll count_under(ll n, ll m, ll p, ll q) { ll ans2 = count_under_smart(n, m, p, q); #ifdef LOCAL2 ll ans = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if ((i || j) && i * p < q * j) { ans++; } } } if (ans != ans2) { eprintf("n = %lld, m = %lld, p = %lld, q = %lld, ans1 = %lld, ans2 = %lld\n", n, m, p, q, ans, ans2); assert(0); } #endif return ans2; } const ll INF = 1e9; void solve(ll n, ll m, ll x) { if (x >= n * m - n) { printf("%lld %d\n", x - n * m + n + 2, 1); return; } ll p1 = 1, q1 = 0; ll p2 = 0, q2 = 1; while (true) { eprintf("%lld %lld %lld %lld\n", p1, q1, p2, q2); assert(count_under(n, m, p1, q1) <= x); assert(count_under(n, m, p2, q2) > x); ll limk = min(p2 ? (m - p1 - 1) / p2 : INF, q2 ? (n - q1 - 1) / q2 : INF); if (limk == 0) break; { ll l = -1; ll r = limk + 1; while (r - l > 1) { ll mid = (l + r) / 2; if (count_under(n, m, p1 + mid * p2, q1 + mid * q2) <= x) { l = mid; } else { r = mid; } } assert(l >= 0); p1 += l * p2; q1 += l * q2; assert(count_under(n, m, p1, q1) <= x); assert(count_under(n, m, p2, q2) > x); } ll limk2 = min(p1 ? (m - p2 - 1) / p1 : INF, q1 ? (n - q2 - 1) / q1 : INF); if (limk2 == 0) break; { ll l = -1; ll r = limk2 + 1; // assert(count_under(n, m, p2 + r * q2, q2 + r * q1) > x); while (r - l > 1) { ll mid = (l + r) / 2; if (count_under(n, m, mid * p1 + p2, mid * q1 + q2) > x) { l = mid; } else { r = mid; } } assert(l >= 0); p2 += l * p1; q2 += l * q1; assert(count_under(n, m, p1, q1) <= x); assert(count_under(n, m, p2, q2) > x); } } assert(count_under(n, m, p1, q1) <= x); assert(count_under(n, m, p2, q2) > x); x -= count_under(n, m, p1, q1); printf("%lld %lld\n", (x + 1) * q1 + 1, (x + 1) * p1 + 1); } Code here is a bit messy, because i was rewring linear searches of turns to binary on last minutes, but solves problem in 9ms.
•  » » 3 years ago, # ^ |   +10 Instead of Stern-Brocot tree, we binary searched on doubles, and used chain fraction to find the closest p/q with q<=n. This is log**2 I think.
•  » » 3 years ago, # ^ |   +3 If you use normal binary searches, the runtime is Θ(log3). If you use exponential search instead, the runtime drops to Θ(log2). (Exponential search runs in where t is the number steps you end up taking.)During the contest I just improved the constant of the linear searches by trying steps of 1000 first.