### chokudai's blog

By chokudai, 5 weeks ago, We will hold AtCoder Beginner Contest 247.

The point values will be 100-200-300-400-500-500-600-600.

We are looking forward to your participation! Comments (22)
 » fun contesti thought F is a dp problem, realizing it's related to graph in the last minutes made me took a wild guess and speedrun coding DSU. submitted 8 seconds before contest ended and as expected got WA
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   They had us in the first half ngl
•  » » I used dp to calculate the amount of valid subsets for a cycle. See https://atcoder.jp/contests/abc247/submissions/30895994 in the calc-method. Need to calculate twice (iterate first) to account for the adjency of $0$ and $c-1$.
 » I think I overcomplicated most of my solutions :/ But still it's wonderful, when there are various approaches to a problem. Great contest)
 » 5 weeks ago, # | ← Rev. 3 →   I think both are same in multiset of string auto it=s.find(x) s.erase(it) (WA) s.erase(s.find(x)) (AC) 
•  » » if a[i]==b[i] your code might fail because you remove elements twice.
•  » » » sorry,i didn't understand can you please elaborate
•  » » » » For the case a[i]==b[i] the one solution removes two elements from the mulitset, the other solution tries to remove one element twice.
 » how to solve E?
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   Iterate over all possible right endings. For each endings, we find the first X, Y, bad to the left. (Here we define a number bad as $(a[i] < Y || a[i] > X)$ If the order is one of the following (X, Y, bad, right), (Y, X, bad, right), (X, bad, Y, right), or (Y, bad, X, right), it is impossible to find a subsequence ending at right that contains both X and Y. If bad is leftmost relatively to X and Y, then the number of subsequences ending at right will be $min(index_X, index_Y) - index_{bad} + 1$ My submission
•  » » » thanks a lot (:
 » Why are heuristic contests shown in red on main atcoder page and in black color on contests page? I get it confused with Atcoder Grand contests because they are shown in red.
 » The solution to F?
•  » » The idea is same as editorial but my dp states are a bit different. Please let me know if something is not clear. Spoiler// kosaraju algo to find the length of all cycles, a bit of overkill from my side vector> v(200005), revV(200005), comp; stack st; vector vis(200005, 0); void dfs1(ll node) { vis[node] = 1; for (auto x : v[node]) if (!vis[x]) dfs1(x); st.push(node); } void dfs2(ll node, ll ind) { vis[node] = 1; comp[ind].push_back(node); for (auto x : revV[node]) if (!vis[x]) dfs2(x, ind); } ll dp1, dp2; /* Note : if node "k" is selected then edge {k-1,k} is selected and not {k, k+1} Case when {1-i} edge is not selected : dp1[i] denotes that for a sequence of {1, 2, .. i} where ith value is not selected dp1[i] denotes that for a sequence of {1, 2, .. i} where ith value is selected Case when {1-i} edge is selected : dp2[i] denotes that for a sequence of {1, 2, .. i} where ith value is not selected dp2[i] denotes that for a sequence of {1, 2, .. i} where ith value is selected General formula => f[i] where f[i] denotes ways to select edges such that one of each adjacent nodes occurs atleast once but the ending node is not selected => {i-1,i} edge is not selected, this means {i-1} needs to be selected f[i] denotes ways to select edges such that one of each adjacent nodes occurs atleast once ans the ending node is selected => {i-1,i} edge is selected, this means {i-1} can or cannot be selected hence f[i] = f[i-1], f[i] = f[i-1] + f[i-1]; */ void calculate(ll n) { // when (1,i) edge is not selected, we are sure that "1" is not selected dp1 = 1, dp1 = 0; for (int i = 2; i <= n; i++) dp1[i] = dp1[i - 1], dp1[i] = (dp1[i - 1] + dp1[i - 1]) % mod; // when (1,i) edge is selected, we are sure that "1" is selected dp2 = 0, dp2 = 1; for (int i = 2; i <= n; i++) dp2[i] = dp2[i - 1], dp2[i] = (dp2[i - 1] + dp2[i - 1]) % mod; } ll get(ll n) { ll a = dp1[n]; /* {1,n} is not selected, hence "n" node needs to be selected for sure*/ ll b = (dp2[n] + dp2[n]) % mod; /* {1,n} is selected, hence "n" node may or may nots be selected for sure*/ return (a + b) % mod; } void solve() { ll n; cin >> n; vector a(n), b(n); for (int i = 0; i < n; i++) cin >> a[i]; for (int i = 0; i < n; i++) cin >> b[i]; for (int i = 0; i < n; i++) { v[a[i]].push_back(b[i]); revV[b[i]].push_back(a[i]); } for (int i = 1; i <= n; i++) if (!vis[i]) dfs1(i); ll ind = 0; vis.assign(n + 1, 0); while (!st.empty()) { ll node = st.top(); st.pop(); if (vis[node]) continue; comp.push_back(vector()); dfs2(node, ind); ind++; } /* Once we have all the cycles, we just need to calculate for all the length of cycle and keep multipying them, hope it is clear, final ans = (answer of cycle 1) X (answer of cycle 2) etc */ ll ans = 1; calculate(n); for (auto x : comp) ans = (ans * 1ll * get(x.size())) % mod; cout << ans << "\n"; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); solve(); return 0; } 
 » I find that Problems E and F in ABC round are always great practice for me. It turns out that it is quite a challenge for me to solve both of them within the contest. Hope that after more practice, I could be more comfortable with these problems.
 » Could anyone explain F. I'm unable to understand g(M)=f(M−1)+f(M−3) relation. Unable to understand "This problem is quite similar to “you must choose one of adjacent elements. How many ways are there to do so?” that we discussed right before." What is meany by adjacent elements? adjacent nodes or edges?
•  » » Can't answer the first question . While solving problem I was looking for pattern and then brute forced for some values and found out that f[i]=f[i-1]+f[i-2] where i is the size of the cycle . For the second part , try naming each edge and vertex 0 to n-1 , u will notice that when you colour edge j , vertex j and (j+1)%n gets colored , I think this is exactly what is meant by the "you must choose one of adjacent elements. How many ways are there to do so?"
 » It was a very good contest.can anyone tell me what is best time complexity in which problem C(1 2 1 3..) can be solved? Link for Problem C
•  » » Suppose that $T(x)=$ the number of numbers we should print when $N=x$, then we have $T(x)=2T(x-1)+1(x>1),T(1)=1$. So $T(x)=O(2^x)$.
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   THANK YOU!I have got a very interesting solution to this problem. I don't know how it got ACCEPTED but my solution is inspired by a similar problem in Codeforces ProblemSetMY SOLUTIONint n;cin>>n;for(int i=1;i<(1<
•  » » Someone solved it in O(1), because there are only 16 possibilities: Submission
 » I solved E with Sparse table and Binary Search. Kind of overkilled the problem. Code