We will hold AtCoder Beginner Contest 214.
- Contest URL: https://atcoder.jp/contests/abc214
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20210814T2100&p1=248
- Duration: 100 minutes
- Number of Tasks: 8
- Writer: blackyuki, Kodaman, physics0523, YoshikaMiyafuji
- Tester: math957963, Nyaan, penguinman
- Rated range: ~ 1999
The point values will be 100-200-300-400-500-500-600-600.
We are looking forward to your participation!
Uhm sure, that's one way to rid the world of 'beginners' :P
this the only way for a beginner to solve 8 tasks
Me too :D
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.
bro u r not beginner,all the best for icpc for your team
No, I'm a beginner and it's very educational for me. I always look forward for ABC
Of course, a beginner who has participated in only 105 rated contests :)
Give a virtual contest later, if you really want to attend it.
That's what I'll do but virtual contest is virtual for a reason, not as fun as real contest
just imagine that it's real:))
thats what she said
i think count of 400 problems should be increased rather than 500 or 600.(beginner point of view)
RIP Problem :D
beginner contests become harder and harder...
How to solve D?
I've been trying some tree dp
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.
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
How to solve E ?
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
Sort and iterate by L, push R to PQ to sort from low to high.
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...
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.
915F is more difficult because we should turn the vertice's value into the edges in that case. Then they're completely the same.
Similar problem to F
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 ).
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...
Yes, we can make all edges non-negative. Check this
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 .
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?
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 i
in 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 0
fill dp K times.
My code : https://atcoder.jp/contests/abc214/submissions/25054504
Maybe this case will hack your solution.
(The expected answer is 7.)
how to solve bonus of B
...not sure
I solved E using
bitsetcodeHow to solve E?
please anyone help me.
E can be solved using splay tree / ordered set with binary search in O(nlog^2).
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.
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.
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.
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.
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.
Lets 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
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 !
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]$$$.
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.
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.
I tried implementing it using a fenwick tree...
...(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])<i-L_j+1$$$ and updating its value in the fenwick tree to $$$1$$$ ($$$sum([x,y]) == y-x+1$$$ implies that $$$[x,y]$$$ is fully occupied).
If I'm not wrong, the time complexity is $$$O(N(logN + Hlog^2M))$$$ (where hashing time is, say $$$O(H)$$$, and $$$1 \le L_j \le R_j \le M$$$, here $$$M = 10^9$$$). This ACed all but 2 cases (TLE) (my submission).
Is there a better way to maintain this? Particularly, with better time complexity than that mine. Thanks for reading and answering!
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.
OK. At first I thought my logic was very different but I guess it's quite the same thing. Thanks.
I was very excited to write my first comment using latex ◕ᴗ◕
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.
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
chokudai, can you update the testcases in dropbox for ABC214 please? They are not updated since ABC207.
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:
Can anyone share a test case for problem E for which below logic fails.
how to solve bonus for problem B ? i.e. 0 <= S,T <= 1e18
found a blog about it.
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