### lewin's blog

By lewin, history, 6 months ago, ,

NAIPC is coming up on March 24th (start time here). More information about the contest can be found on this page. More information on how to register can be found on this page. You can register in teams of up to 3. This contest will be on Kattis.

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 1: The deadline to register your team is soon.

UPD 2: Contests are over

•
• +49
•

 » 6 months 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.
 » 6 months ago, # |   +19 How to solve B and J ?
•  » » 6 months ago, # ^ |   +33 B: "Degree sequences" is a big hint.
•  » » » 6 months ago, # ^ |   0 This problem is also (almost) an old POI problem: https://main.edu.pl/en/archive/oi/18/kon
•  » » 6 months ago, # ^ |   +10 J: The graph must be a cactus for possible solutions. Then it's a DP problem on a cactus.
 » 6 months ago, # |   0 I: I had to optimize my O(NM) solution (and still it takes 1.8s). Is there something faster?
•  » » 6 months ago, # ^ |   +20 You can speed up to N+M**2 if you can multiply polynomial by constant in O(1).
•  » » 6 months ago, # ^ |   0 I wasted 90min in problem I and still cannot solve :(
•  » » 6 months 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; } 
 » 6 months ago, # |   +8 C ?
•  » » 6 months ago, # ^ |   +13 Do operations in reverse. Then i-th operation xors segment of length i.
•  » » » 6 months ago, # ^ |   -14 How to solve after that ?
•  » » » » 6 months 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).
 » 6 months 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.
•  » » 6 months 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.
•  » » 6 months 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.