chokudai's blog

AtCoder Beginner Contest 214 Announcement
By chokudai, history, 3 years ago, In English

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!

  • Vote: I like it
  • +115
  • Vote: I do not like it

Comments Comments (57)
| Write comment?
»
3 years ago, # |
← Rev. 2   Vote: I like it +73 Vote: I do not like it

Email Announcement

Uhm sure, that's one way to rid the world of 'beginners' :P

→ Reply
»
3 years ago, # |
  Vote: I like it -53 Vote: I do not like it

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.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +36 Vote: I do not like it

    bro u r not beginner,all the best for icpc for your team

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      No, I'm a beginner and it's very educational for me. I always look forward for ABC

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +31 Vote: I do not like it

        Of course, a beginner who has participated in only 105 rated contests :)

        → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    Give a virtual contest later, if you really want to attend it.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it -9 Vote: I do not like it

      That's what I'll do but virtual contest is virtual for a reason, not as fun as real contest

      → Reply
»
3 years ago, # |
  Vote: I like it +9 Vote: I do not like it

i think count of 400 problems should be increased rather than 500 or 600.(beginner point of view)

→ Reply
»
3 years ago, # |
  Vote: I like it +5 Vote: I do not like it

RIP Problem :D

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +26 Vote: I do not like it

beginner contests become harder and harder...

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve D?

I've been trying some tree dp

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    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.

    → Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 3   Vote: I like it +5 Vote: I do not like it

    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

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve E ?

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it
    Spoiler
    → Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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...

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    915F is more difficult because we should turn the vertice's value into the edges in that case. Then they're completely the same.

    → Reply
»
3 years ago, # |
  Vote: I like it +18 Vote: I do not like it

Similar problem to F

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 ).

    → Reply
»
3 years ago, # |
  Vote: I like it +15 Vote: I do not like it

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...

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Yes, we can make all edges non-negative. Check this

    → Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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 .

    → Reply
»
3 years ago, # |
  Vote: I like it +19 Vote: I do not like it

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?

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +26 Vote: I do not like it

    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.)

    → Reply
»
3 years ago, # |
  Vote: I like it +6 Vote: I do not like it

how to solve bonus of B

→ Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it +9 Vote: I do not like it

...not sure

→ Reply
»
3 years ago, # |
  Vote: I like it +2 Vote: I do not like it

I solved E using bitset code

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve E?

please anyone help me.

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

E can be solved using splay tree / ordered set with binary search in O(nlog^2).

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
3 years ago, # |
  Vote: I like it +14 Vote: I do not like it

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.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +18 Vote: I do not like it
    Editorial code ideia
    → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 2   Vote: I like it +5 Vote: I do not like it

      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 !

      → Reply
»
3 years ago, # |
  Vote: I like it +29 Vote: I do not like it

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]$$$.

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 4   Vote: I like it +16 Vote: I do not like it

    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.

    → Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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 attempt

Is there a better way to maintain this? Particularly, with better time complexity than that mine. Thanks for reading and answering!

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      OK. At first I thought my logic was very different but I guess it's quite the same thing. Thanks.

      Also, sumimasen
      → Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it +6 Vote: I do not like it

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.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like 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

    → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +23 Vote: I do not like it

chokudai, can you update the testcases in dropbox for ABC214 please? They are not updated since ABC207.

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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
→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone share a test case for problem E for which below logic fails.

  1. Sort the intervals in increasing order of their endpoints.
  2. 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 --;
}
→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve bonus for problem B ? i.e. 0 <= S,T <= 1e18

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like 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

→ Reply