### masonsbro's blog

By masonsbro, history, 8 months ago, ,

Next Saturday, May 4, at 6pm UTC, the University of Texas at Austin is hosting an "invitational" (actually open to anyone) programming contest. The contest will last 5 hours and is intended to be similar to a North American ICPC regional contest in terms of difficulty. There will be 10-14 problems, and we encourage you to follow ICPC rules: teams of 3 on one computer, using no online resources.

The problem set was created by myself and arknave.

If you want to participate, you can sign up using the registration form: https://forms.gle/L2s5DaNQFzKKdtnu6

Details will be sent out to everyone who's registered closer to the contest date.

Update: The contest url is utipc19.kattis.com.

Update 2: The solutions are up.

• +77

 » 7 months ago, # |   0 Reminder: this is tomorrow! Good luck to all participants.
 » 7 months ago, # |   0 Auto comment: topic has been updated by masonsbro (previous revision, new revision, compare).
 » 7 months ago, # |   +67 Maybe you can shift the start so it doesn't collide with CF round?
•  » » 7 months ago, # ^ |   +8 Unfortunately we won't be able to move our room reservations. To everyone competing in person, see you tomorrow!
•  » » » 7 months ago, # ^ |   +26 Oh, I didn't know that there is onsite participation. Maybe you can do parallel contest for online participants and postpone only that one?
 » 7 months ago, # |   0 Only one hour left, but there is no mail with login and password. Should I worry?
•  » » 7 months ago, # ^ |   +13 You can register yourself at the Kattis site
•  » » » 7 months ago, # ^ | ← Rev. 2 →   +8 You mean, I don't need additional registration for this contest. Only for Kattis?P.S. Thank you I could log in. The problem was that after even I logged into Kattis using Facebook, on the contest page it asks me to log again and didn't have the button to log-in using Facebook. Now I found the way to do it.
 » 7 months ago, # |   +1 Great contest! Is there going to be an editorial published? We did not solve B,I,L and are curious about the intended solutions.
•  » » 7 months ago, # ^ |   +12 I will give a few hints. B: It's only necessary to know some parities to be able to say if a number is lucky or not. I: $C = V - E$ Where $C$ is number of components, $V$ is number of vertex and $E$ is number of edges, you can pre calculate the value o $V$ and $E$ for each number, this doesn't work if there is cycles, but in the problem the graph is a cactus so you can count the number of cycles that you should exclude. L: If you can solve the problem for $N = 2$ you can solve for bigger $N$, you should think about inclusion-exclusion here.
•  » » » 7 months ago, # ^ | ← Rev. 2 →   0 Could you elaborate a bit on which parities you mean for B. I am familiar with using the parity of the prefix to determine the number of "even sum substrings" for any string, but am not able to correctly turn this into a recurrence that accounts for all possible strings in the range. Thanks!
•  » » » 7 months ago, # ^ |   0 My solution to problem I uses an implicit disjoint set for each factor which solves the problem on a general graph as well. I was curious about what the intended solution was since I couldn't think of a solution that used the fact that the graph was a cactus.
 » 7 months ago, # | ← Rev. 2 →   +12 Really happy to get the first place! :) Our team didn't start well but caught up later.Here are our solutions for some of the problems:Problem B — Serious Business IdeaWe can turn this into a standard digit DP problem. The problem is how we should capture the transition of the No. of the scary substrings. Suppose we are in the $i$-th (from the beginning) digit of number, we can keep track of "The parity of No. of scary substrings", "The parity of No. of suffixes of $s[1,i]$ with odd sum", "The parity of No. of suffixes of $s[1,i]$ with even sum". Then it will not be hard to find the transition. My Code#include using namespace std; typedef long long ll; const int B = (int)1e5 + 50, mod = 998244353; ll dp[B][2][2][2][2]; int bit[B], b; int pw2[B]; //int A, B; ll get(int d, int scary, int odd_suf, int even_suf, bool flag, bool st){ if(d == -1) { return scary % 2 == 1; } if(!flag && ~dp[d][scary][odd_suf][even_suf][st]) return dp[d][scary][odd_suf][even_suf][st]; int lim = flag ? bit[d] : 9; int res = 0; for(int i = 0; i <= lim; i++){ bool nxt_st = st || i != 0; int nxt_scary = (scary + (i % 2 == 0 ? even_suf + 1 : odd_suf)) % 2; int nxt_odd = (i % 2 == 0 ? odd_suf : even_suf + 1) % 2; int nxt_even = (i % 2 == 0 ? even_suf + 1 : odd_suf) % 2; if(!nxt_st) {nxt_scary = nxt_odd = nxt_even = 0;} res += get(d - 1, nxt_scary, nxt_odd, nxt_even, flag && lim == i, nxt_st); res %= mod; } return flag ? res : dp[d][scary][odd_suf][even_suf][st] = res; } ll solve(string str){ b = 0; memset(dp, -1, sizeof(dp)); for(int i = str.length() - 1; i >= 0; i--) { bit[b++] = str[i] - '0'; } return get(b-1, 0, 0, 0, true, false); } int main() { string L, R; cin >> L >> R; L.back() -= 1; int carry = 0; for(int i = L.size() - 1; i >= 0; i--) { if(carry) { L[i]--; carry = 0; } if(L[i] < '0') { L[i] += 10; carry++; } } ll res = (solve(R) - solve(L) + mod) % mod; cout << res << endl; } Problem I — Cactus Shoppe IdeaTry to build the graph for each different query. We can see the sum of the number of nodes in the graph will not exceed $O(n \cdot \sqrt{\max f_i})$, since each node will appear in at most $2 \sqrt{\max f_i}$ (the number of its divisors). One can also see the number of edges are bounded. Then for each graph, we run dfs and count the answer. Code#include using namespace std; const int N = (int)1e5 + 50, Q = (int)1e6 + 50; int n,m,q; vector G[N]; bool vis[N]; bool gd[N]; int f[N]; vector dvs[Q]; int res[Q]; void dfs(int v) { vis[v] = true; for(int nxt : G[v]) { if(!vis[nxt] && gd[nxt]) dfs(nxt); } } int solve(int dv) { for(int i : dvs[dv]) { vis[i] = false; gd[i] = true; } int res = 0; for(int i : dvs[dv]) { if(!vis[i]) { dfs(i); res++; } } for(int i : dvs[dv]) { gd[i] = false; } return res; } int main() { memset(res, -1, sizeof(res)); cin >> n >> m >> q; for(int i = 0; i < n; i++) { cin >> f[i]; int j; for(j = 1; j * j < f[i]; j++) { if(f[i] % j == 0) { dvs[j].push_back(i); dvs[f[i]/j].push_back(i); } } if(j * j == f[i]) dvs[j].push_back(i); } for(int i = 0; i < m; i++) { int a, b; cin >> a >> b; a--, b--; G[a].push_back(b); G[b].push_back(a); } while(q--) { int x; cin >> x; if(res[x] != -1) { cout << res[x] << "\n"; continue; } res[x] = solve(x); cout << res[x] << "\n"; } } Problem L — Neural Networks IdeaFor each pair of neighboring layers, we try to compute the answer by inclusion-exclusion principle and sum them together. Let $f(a, b)$ be the number ways to connect two layers of size $a$ and $b$ respectively. Then we have $f(a, b) = \sum_{i = 0}^{b} {(-1)}^i {{b}\choose{i}} {(2^i - 1)}^a$ Code#include using namespace std; typedef long long ll; const int N = (int)5e5 + 50; const ll mod = 998244353; int n, num[N]; ll fac[N], facinv[N]; ll inv[N]; ll pw2[N]; ll fp(ll x, ll k){ if(k == 0) return 1; ll hf = fp(x, k/2); return k % 2 ? hf * hf % mod * x % mod: hf * hf % mod; } ll comb(int n, int k){ return fac[n] * facinv[k] % mod * facinv[n - k] % mod; } ll calc(int a, int b) { if(a < b) swap(a, b); ll res = 0; int sig = 1; for(int i = b; i >= 0; i--) { res += sig * fp(pw2[i]-1, a) * comb(b, i) % mod; sig = -sig; res %= mod; } return res; } int main(){ inv[1] = 1; for(int i = 2; i < N; i++) inv[i] = (mod - (mod / i) * inv[mod % i] % mod) % mod; fac[0] = 1; for(int i = 1; i <= N-1; i++) fac[i] = fac[i-1] * i % mod; facinv[N-1] = fp(fac[N-1], mod - 2); for(int i = N-1 - 1; i >= 0; i--) facinv[i] = facinv[i+1] * (i+1) % mod; pw2[0] = 1; for(int i = 1; i < N; i++) pw2[i] = pw2[i-1] * 2 % mod; cin >> n; for(int i = 0; i < n; i++) cin >> num[i]; ll res = 1; for(int i = 0; i < n - 1; i++) { res *= calc(num[i], num[i+1]); res %= mod; } cout << (res + mod) % mod << endl; } I am curious about what is the intended solution for Problem I, since my solution is not related to cactus.
•  » » 7 months ago, # ^ |   +8 Several teams used that solution for I. We didn't think of that! If you want to think about the intended solution, here are some bounds that I think would require it: 2 <= n <= 10^6, 1 <= m <= 10^6, 1 <= value <= 10^6, time limit 2.5s. Intended solutionLet's suppose we have some subset of the nodes and edges in the original graph. How many connected components are there? First, let's add the nodes to an empty graph. Every time we add a node, we add a connected component. Now, let's add the edges. Every time we add an edge, we subtract a connected component, unless it's the last edge of a cycle; in that case, we don't change the number of connected components.Another way of phrasing this: every node causes +1 connected components, every edge causes -1 connected components, and every cycle causes +1 connected components. In other words, the answer for a query is nodes — edges + cycles in the remaining graph.It's easy to tell when a node should be in the graph for a query (q_i should divide f_j). For an edge (u, v) to be in the graph, we need both the nodes to be in the graph. That is, q_i | f_u and q_i | f_v. This is the same as q_i | gcd(f_u, f_v). Similarly, a cycle (u_1, ..., u_k) is in the graph for query i if q_i | gcd(f_u_1, ..., f_u_k).So for each node u, do ++cnt[f_u]. For each edge (u, v), do --cnt[gcd(f_u, f_v)]. For each cycle (u_1, ..., u_k), do ++cnt[gcd(f_u_1, ..., f_u_k)]. Now to answer a query q_i we just need the sum of cnt[i*p] (for integers p). We can just compute the answers to all the possible queries naively, saving them in an array. (This takes O(F log F) time, where f_i <= F for all i.) Then we can look up the answer for each query.Total time complexity: O(M + F log F + Q).
•  » » » 7 months ago, # ^ | ← Rev. 2 →   +10 The difference between F log F and F div(F), where div is the maximum number of divisors of any number under F is hard to differentiate here, especially when supporting multiple languages. $\log_2(1\,000\,000) \approx 20$, and $div(1\,000\,000) = 240$. I think the time limit would have to be even lower. I think both solutions are nice. :)
•  » » » 7 months ago, # ^ | ← Rev. 2 →   0 I see. Good observation of the cactus! That's interesting.P.S. Thanks for the solution!
 » 7 months ago, # |   0 Auto comment: topic has been updated by masonsbro (previous revision, new revision, compare).