### chokudai's blog

By chokudai, history, 5 months ago,

We will hold AtCoder Beginner Contest 214.

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

We are looking forward to your participation!

• +115

 » 5 months ago, # | ← Rev. 2 →   +73 Uhm sure, that's one way to rid the world of 'beginners' :P
•  » » 5 months ago, # ^ |   +39 this the only way for a beginner to solve 8 tasks
•  » » 5 months ago, # ^ |   +4 :)
•  » » 5 months ago, # ^ |   -9 Me too :D
 » 5 months ago, # |   -53 This contest is clashing with ICPC Amritapuri regionals. If possible please postpone it, otherwise many people like me who are participating in this ICPC regionals will not be able to participate.
•  » » 5 months ago, # ^ |   +36 bro u r not beginner,all the best for icpc for your team
•  » » » 5 months ago, # ^ |   +5 No, I'm a beginner and it's very educational for me. I always look forward for ABC
•  » » » » 5 months ago, # ^ |   +31 Of course, a beginner who has participated in only 105 rated contests :)
•  » » 5 months ago, # ^ |   +19 Give a virtual contest later, if you really want to attend it.
•  » » » 5 months ago, # ^ |   -9 That's what I'll do but virtual contest is virtual for a reason, not as fun as real contest
•  » » » » 5 months ago, # ^ |   +9 just imagine that it's real:))
•  » » » » » 5 months ago, # ^ |   +14 thats what she said
 » 5 months ago, # |   +9 i think count of 400 problems should be increased rather than 500 or 600.(beginner point of view)
 » 5 months ago, # |   +5 RIP Problem :D
 » 5 months ago, # | ← Rev. 2 →   +26 beginner contests become harder and harder...
 » 5 months ago, # |   0 How to solve D?I've been trying some tree dp
•  » » 5 months ago, # ^ |   +6 I did it using DSU. For each edge it can be maximum on a path only if every other edge is smaller than it, so we can sort edges in increasing order and solve only for a tree that consists of some prefix of edges. As you traverse the edges add them to the tree and increase answer by $w \cdot sz[u] \cdot sz[v]$, where sz[x] is the number of vertices in x's component.
•  » » 5 months ago, # ^ | ← Rev. 3 →   +5 Assume all N nodes initially are disconnected now iterate over the edges sorted by weight and merging the nodes on the fly, and before doing the merging operation on an edge $(u,v)$ add $w_{u,v} \times C_u\times C_v$to the final answer, where $C_u$ is the component size of the component in which node $u$ is present
 » 5 months ago, # |   0 How to solve E ?
•  » » 5 months ago, # ^ |   0 For E, I did in some greedy fashion. Firstly, I sorted all the intervals as pairs. Next, take l = start with min start of present intervals, enqueue all these intervals in min-heap with their end point. Now, increase l by 1, check if the next min start of intervals is l or not, if it is enqueue them too in min-heap. The idea is to assign the left most point possible to the interval with least end point. Submission
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 SpoilerSort and iterate by L, push R to PQ to sort from low to high.
 » 5 months ago, # |   +1 Isn't problem D similar to 915F - Imbalance Value of a Tree? And 915F has a solution that can calculate the maximum value and minimum value...
•  » » 5 months ago, # ^ |   0 Similar to mootube from USACO Jan 2018 as well. But ABCs are for educational purposes so I think it's fine to have more generic problems.
•  » » 5 months ago, # ^ |   0 915F is more difficult because we should turn the vertice's value into the edges in that case. Then they're completely the same.
 » 5 months ago, # |   +18 Similar problem to F
•  » » 5 months ago, # ^ |   0 Actually this gfg method is very precise, but I overcomplicated it and was not able to solve it during the contest. Although after the contest ended, I got a solution using graphs. Basically like this. for all i, store where the next character 'c' occurs. Then from ith index create an edge between ith index and the minimum index from (i+2) where character 'c' occurs. Do the same from 0th index. Initiaize the dp array to zero except dp[0] = 1. Then for all i, dp[i] = dp[i] + dp[j] (j belongs to the other end of all the edges before i ).
 » 5 months ago, # |   +15 Can anyone provide some information about solving min cost flow with Dijkstra (is there a way to get rid of negative edges)? I have never seen anything about it...
•  » » 5 months ago, # ^ |   +5 Yes, we can make all edges non-negative. Check this
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 Let dis'[i] be the shortest path from 1 to i in the previous graph .And you want to calculate dis[i] in the new graph .Let h[i] = dis[i]-dis'[i] , so dis[i] = dis'[i] + h[i].And you can turn the edge u,v,w to u,v,w+dis'[u]-dis'[v] , you can find that w + dis'[u] >= dis'[v]. So you can use dijkstra to calculate h[i].Because the graph is a DAG in the beginning , so you can calculate dis'[i] easily .
 » 5 months ago, # |   +19 I'm finally able to solve 6 problems in ABC, but now there are 8 total :(Also, now that ABCs are substantially harder than before, maybe the rated range should also increase?
 » 5 months ago, # |   0 could anyone help me understanding why just dp on DAG not working in H?Make dag, let dp[i] = path with biggest items ends at iin one iteration set all dp -1, then set dp[scc[1]] = 0. then just fill it dp table.backtrace path with largest dp[i], then make all items of vertex in path 0fill dp K times.
•  » » 5 months ago, # ^ |   +26 Maybe this case will hack your solution. 5 5 2 1 2 2 3 1 4 2 5 4 3 1 2 2 1 1 (The expected answer is 7.)
•  » » » 5 months ago, # ^ | ← Rev. 2 →   0 I'm sorry if I'm wrong. It seems answer is 6.1-2-3 and (1-4 or 1-2-5)How could it be 7?
•  » » » » 5 months ago, # ^ |   0 Sorry It's 7. right.
 » 5 months ago, # |   +6 how to solve bonus of B
 » 5 months ago, # | ← Rev. 3 →   +9 ...not sure
 » 5 months ago, # |   +2 I solved E using bitset code
 » 5 months ago, # |   0 How to solve E?please anyone help me.
 » 5 months ago, # |   0 E can be solved using splay tree / ordered set with binary search in O(nlog^2).
 » 5 months ago, # |   0 Can someone please tell me what's wrong in my solution to problem D(Problem link)? Here's my code(My code). Thanks in advance.
•  » » 5 months ago, # ^ |   0 the way you declared edges was the problem, you first declared it with some size and later cleared it then sorted it and iterated from 1 to n-1, which causes wrong indexing and cause other problems too, here I corrected it. ps: your merge function is not optimal, your dsu will be O(logn) for each operation instead of O(1), look at cp-algorithm(or any other site) for optimal implementation of dsu.
•  » » » 5 months ago, # ^ |   0 Thank you very much. Appreciate your help.
 » 5 months ago, # |   0 Have anyone solved C with the graph approach as given in the editorial
 » 5 months ago, # |   0 Can anyone please tell the concept used behind in E? Thank You
 » 5 months ago, # |   +14 Can anyone explain how to calculate the sum of products of sizes in problem G using binomial coefficients? I can't understand where the formulas in the editorial code come from.
•  » » 5 months ago, # ^ |   0 There is a good AtCoder explanation stream on YouTube. Unfortunately it is in Japanese and Google auto translate is not good at all. Let's hope that pashka will do a stream on these problems soon.
•  » » » 5 months ago, # ^ |   0 Video editorial has some DP, not just binomial coefficients as in written one. I've also solved this problem with DP, but I'm curious to know the intuition behind formulas in sample code.
•  » » 5 months ago, # ^ |   +18 Editorial code ideiaLets think of a easier version of the problem: How to calculate the sum of products of sizes when we split a array ( not a cycle !!) in k sub-arrays.The answer of this problem is $C(n+k-1, 2*k - 1)$. Because you can see this problem as put $k-1$ tokens of split in the array, and after that we put one token in each k parts.When we already break the array in k sub-arrays, We can know the products of sizes as the number of ways to put exactly one token in each of the sub-arrays, because $size = C(size,1)$. To know the sum of products of sizes, we just add $k-1$ spaces for putting tokens of split. You can see the final $C(n+k-1, 2*k-1)$ as putting one token that choose a element, one token of split, one token of element, ... , one token of split, one token of element.Now let's go back to the initial problem ( in a cycle ).The editorial code have a $first$ in there. This means that the first index of edge we will break if the edge between $first$ and $(first-1+n)\%n$ ( To avoid double count ). And after that we will break the cycle and go to the array. So the array is $[first, n-1][0, first-1]$. Know its similar to the array, but we need to care of the last token of element, because he can be in one of the two intervals, the others token can just be in $[first,n-1]$, because the first index edge we remove is $( first, (first-1+n)\%n)$.The $other$ variable means how much sub-arrays we will split the array ( its 0-based, so when its 0, means we will have 1 sub-array, 1 means we will have 2 sub-arrays). The first binomial of the code is the case when the last token is in the interval $[first,n-1]$, since every token is in this interval, this is the case for the array of size $n-first$, and we will split the array in $other+1$ sub-arrays, so the value is $C(cnt-first + other, 2*other + 1)$.The second binomial of the code is the case when the last token is in the interval $[0, first-1]$, so its the same at putting a one less count at the interval $[first,n-1]$ times the numbers of ways to put a token in the interval $[0,fist-1]$, which is $first$ ( the length of the interval). After that, we get the value $C(cnt- first +other - 1, 2*other)*first$. We have a $-1$ there because we can't put a token of split in the end of the interval $[first,n-1]$, and this type of token become the last token in the interval. So its the same as ignore the last position of the array, ending with the interval $[first, n-2]$.The value of dp $cnt-other-1$ is about the main problem, if we break the cycle in $other+1$ paths, we will assings $cnt-other-1$ paths, because each path removes a edge of the cycle.This is the ideia of the editorial code.You can actually count the sum of products without the ideia of $first$. You can see the problem as putting $n$ tokens of element and $k$ tokens of split to break the cycle in $k$ paths. But you will need to think of the two orders to put the tokens.The first order is to put first a token of element, second a token of split, a token of element, ... . This case is $C(cnt+k, 2*k)$.The second order is to put first a token of split. In this order you can't put a token in the begining, because you will double counting the cases where you remove the edge $(n-1, 0)$, because in the first order this is counting already when we putting a token of split in the end. So its $(cnt+k-1, 2*k)$.You can see this in this submission
•  » » » 4 months ago, # ^ | ← Rev. 2 →   +5 Thanks a lot, that's what I desperately want ! I've spent nearly half a month to think of this problem but in vain. Your editorial really helps me out !
 » 5 months ago, # |   +29 Here's an $O(n)$ solution to F I thought was cool:Go from left to right and imagine that we're building a trie representing the possible words we can form. So adding a new word == appending a leaf. If we ignore the consecutive restriction, we can append $s_i$ to any existing node, except for a node which already has child $s_i$. So we add $total - cnt[s_i]$ each time. This consecutive restriction simply means we can't append $s_i$ to a node we made on the last index, so the number of leaves we form at index $i$ becomes $total - cnt[s_i] - [\text{# nodes formed at }i-1]$.
•  » » 5 months ago, # ^ | ← Rev. 4 →   +16 As a bonus, this only requires $O(\sigma)$ memory (where $\sigma$ = alphabet size). Excepting input... but even that can be obviated, as it can be easily implemented such that the program only knows the single character being worked on. Makes for a cute little finite-state automaton.
 » 5 months ago, # |   +1 In Problem E, I sorted the ranges in the non-decreasing order of $R_j$ and tried to assign boxes greedily, i.e., choose box $i$ such that $i$ is the first available box in the range $[L_j, R_j]$. However, for each range $[L_j, R_j]$, finding this $i^{th}$ box proved to be a headache. my attemptI tried implementing it using a fenwick tree... details...(an unordered map) that counts number of used boxes for any range and binary searching for the least $i$ in $[L_j, R_j]$ such that $sum([L_j, i]) •  » » 5 months ago, # ^ | 0 You did read the editorial?We iterate the boxes. While doing so, we add all balls (with the intervals) to a list that can be put into the actual box (that ist, the l[i]<= current box)Foreach box, we assign the ball with the smallest r[i]. We find that ball by using a priority queue.Whenever the list of balls (the priority queue) is empty we "jump" to the next ball, i.e. the next bigger l[i] value. •  » » » 5 months ago, # ^ | +5 OK. At first I thought my logic was very different but I guess it's quite the same thing. Thanks. Also, sumimasenI was very excited to write my first comment using latex ◕ᴗ◕  » 5 months ago, # | ← Rev. 3 → +6 Could someone explain to me the approach in the editorial of problem F. Substrings? In the solution to the original problem, what does$dp[i]$represents? At first I thought it was the number of substrings of$1st$to$ith$characters of$S$such that the$ith$character is marked and the$(i - 1)th$character is not marked but I think I'm understanding it wrong as dp[1] = 0 instead of 1. I feel like it's something very basic but I just can't wrap my head around it. •  » » 5 months ago, # ^ | 0 I found it easier to think of it as the number of strings that can be continued at that index ($0$-indexed) at the earliest  » 5 months ago, # | ← Rev. 2 → +23 chokudai, can you update the testcases in dropbox for ABC214 please? They are not updated since ABC207.  » 5 months ago, # | ← Rev. 2 → 0 Did anybody implement problem F in O(N) using prefix sums? I'm trying to implement it but can't deal with the indexes.UPD: Implemented it, code for people who need/* * Author: bubu2006 **/ #include using namespace std; const long long MOD = 1e9 + 7; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); string s; cin >> s; long long n = (long long)s.size(); vector dp(n + 2), last(26, -1), pref(n + 2); dp[0] = 1; dp[1] = 0; pref[0] = 1; pref[1] = 1; for(long long i = 0; i < n; i++) { if(last[s[i] - 'a'] == -1) { dp[i + 2] = (dp[i + 2] + pref[i]) % MOD; } else { dp[i + 2] = (dp[i + 2] + pref[i] - pref[last[s[i] - 'a']]) % MOD; } last[s[i] - 'a'] = i; pref[i + 2] = pref[i + 1] + dp[i + 2]; } long long ans = 0; for(long long i = 0; i <= n + 1; i++) { ans = (ans + dp[i]) % MOD; } cout << (ans - 1 + MOD) % MOD << '\n'; }   » 5 months ago, # | 0 Can anyone share a test case for problem E for which below logic fails. Sort the intervals in increasing order of their endpoints. Greedily assign a box to each intervals starting from the right most interval. int ans = 1, cb = a[n - 1].second; for (int i = n - 1; i >= 0; --i) { cb = min(cb, a[i].second); if (cb < a[i].first) { ans = 0; break; } cb --; }   » 5 months ago, # | 0 how to solve bonus for problem B ? i.e. 0 <= S,T <= 1e18 •  » » 5 months ago, # ^ | ← Rev. 3 → 0 found a blog about it.  » 5 months ago, # | ← Rev. 2 → 0 I'm curious as to why problem G has$N = 3000$with mod$10^9 + 7$, since my solution is basically the editorial solution with FFT to speed it up to$\mathcal O(N \log^2 N)$. I've seen many ABC problems with FFT on them, so it seems weird not to have$N = 10^5$with mod$998244353\$, but maybe this was done to hide the solution? I attached my submission below. Submission
 » 5 months ago, # | ← Rev. 2 →   0 Deleted.