chokudai's blog

By chokudai, history, 3 years ago, In English

We will hold AtCoder Beginner Contest 218.

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

We are looking forward to your participation!

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

| Write comment?
»
3 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Hi chokudai I am interested in setting up the user editorials , if I can (ooops!!). How can I ?

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

    People with atcoder rating of greater than or equal to 2000 see the "New Editorial" button on ABC's editorial page. Clicking on it opens a page to publish user editorials.

»
3 years ago, # |
  Vote: I like it +12 Vote: I do not like it

My parents would rather let me participate in AtCoder contests than let me participate in Codeforces rounds, but they allow me to participate in both kinds of contests.

Imagine you're in UTC+8 and then you can figure it out ;)

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

Nice problemset, any hints on problem H?

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

    How to solve G?

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

      Do dfs traversal over the tree, now you need to keep track of the median for the entire path you're in, which can be done in several ways, i used ordered sets. Supose you want to know the best posible score for a node X, if depth of node X is even, is your oponent turn, so he will get you to the lowest possible outcome, otherwise is your turn, so you maximize it, run a top-down dp and print the value for node 1.

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

        Doesn't that give you TLE? (Ordered set for every node)

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

          Keep a global set, in which you only keep elements contained in the path from node $$$1$$$ to node $$$X$$$, to mantain this, you can add elements when you enter a node, and delete them just before you exit it.

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

      I skipped the contest this week to prep (w/ sleep) for hacker cup round 1. I'm getting around to solving these now.

      As I have primarily been using python for these (although might switch to Go once I've finished building up a reasonable library), multiset wasn't available, and I didn't think to use a Fenwick tree. I'm solving it with 4 heaps. It is a bit slow (near 1.0s), but it does the job. (2 heaps for left and right insertions, and 2 heaps for left/removals) and just do the bookkeeping to cancel out the addition/removal heaps when the heads of each match).

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

    The problem statement is equivalent to placing $$$min(R,B)$$$ 2x1-Dominoes on $$$A$$$ and adding the covered $$$A_i$$$ s. But that's as far as I could get...

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

      Does this cover the case when you do something like $$$AAB$$$?

      • »
        »
        »
        »
        3 years ago, # ^ |
        Rev. 2   Vote: I like it +3 Vote: I do not like it

        There is no need to do $$$AAB$$$ because you could do $$$ABA$$$ and get more points. $$$AAB$$$ would be the equivalent of placing the Domino on $$$A_{N-1}$$$ and the non existent $$$A_{N}$$$.

»
3 years ago, # |
  Vote: I like it +32 Vote: I do not like it

To be honest, I don't think the difficulty C of this contest is suitable for the difficulty of ABC's usual problem C. Otherwise, a lot of people, including me, won't do D first or even other later problems before doing C. At least for me, the implementation difficulty of D is simpler than that of C :(

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

    I am so depressed with a C ... It made me feel incompetent :(

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

      It's a thing that's popular on AtCoder (geometrical transformations), I usually get very mad when I see them, but they occur every once in a while. It's just about simulating rotations 4 times and writing a check function with the restricted canvas, but that in itself gets very implementation heavy and ugly. There's probably a better way to solve it, but this is how I usually get AC withing ~100 lines of code.

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

        Actually, I got AC with an about 40 lines and only 1.44kb code.

        Click to see the code
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Thats a lot code for a C in abc.

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

            Expecting for a shorter solution then...

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

      Seems like it makes sense to have some code templates for 2D array rotation and maybe other simple transformations to avoid wasting extra time on problems like this. It's not the first problem of this kind.

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

    For me G was easier than C , as it required a good amount of code and had much less points than C ( Unluckily I missed G as I had value of infinity as 998245353 rather than 10^9+7)

  • »
    »
    3 years ago, # ^ |
    Rev. 5   Vote: I like it 0 Vote: I do not like it

    I think my answer is wrong for problem C, but It has been accepted.

    Those test cases are giving me : Yes.

    3
    . # .
    # . .
    . . .
    . . #
    # . .
    . . .
    
    5
    . . . . .
    . . . . .
    . . # . .
    . . # # #
    . . # . .
    . . . . .
    . . . . .
    . . . # #
    . . . # #
    . . . # .
    

    Am I wrong ?

    Most of the people in the first page of the standings are getting "Yes" you can check if you want : https://atcoder.jp/contests/abc218/submissions/25773980

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

      Yeah, you are right, these cases must give a "No" Output. My Submission

      chokudai Please look into this.

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

        I want to add something the test case has spaces in between.

        but even after fixing that like this :

        3
        .#.
        #..
        ...
        ..#
        #..
        ...
        

        I still get Yes.

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

          The spaces wont matter as most people take the input character by character (including me).

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

      My code output "No" for both the test cases. It seems that my approach is right :D

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

plz explain C,D

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

    check out the editorials

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

    For C, First, if only 90 degree rotation is considered, there may be only 4 patterns s at most. Then consider the translation. It can be found that you only need to see which of the four patterns mentioned above can be translated to completely match t. Specifically, we list the positions of all characters # in S and T in sequence, and then compare them one by one. Let set pattern $$$S$$$ have a amount of $$$c_1$$$ #, the position of the $$$i$$$-th # is $$$(x_{0,i},y_{0,i})$$$; pattern $$$T$$$ have a amount of $$$c_2$$$ #, the position of the $$$i$$$-th # is $$$(x_{1,i},y_{1,i})$$$, and then we just need to find out whether the following conditions are met:

    • $$$\forall i\in[2,n],x_{0,i}-x_{1,i}=x_{0,1}-x_{1,1}$$$
    • $$$\forall i\in[2,n],y_{0,i}-y_{1,i}=y_{0,1}-y_{1,1}$$$
    • $$$c_1=c_2$$$

    Just follow this implemention. It may be a bit hard.

    Code(C++)

    For D, we only need to enumerate two points, not four. Let the two points we enumerated be $$$i$$$ and $$$j$$$, and then you just need to see whether the two points $$$(x_i, y_j)$$$ and $$$(x_j,y_i)$$$ exist. Be careful not to repeat the enumeration.

    Code(C++)
    • »
      »
      »
      3 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      You could use a hashmap for D,(checking whether it is possible to form a rectangle with every pair of points). That would be a slightly clean implementation.

»
3 years ago, # |
  Vote: I like it +10 Vote: I do not like it

I assumed that alien trick is applicable in H and it worked lol.

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

In problem E — Destruction, I got 13 tc passed and 10 wrong, can you please help me with what's wrong with my code. (When I submit, I assumed it will give me TLE)

Code
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Just find the minimum spanning tree for E(be careful while dealing with loops and multiple edges), your answer will be $$$max(0,total\ cost-cost\ of\ MST)$$$.

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

    I got 4 penalty's because I removed all edges even those which had negative weight. I guess that's your error too. Sort edges in non-decreasing order of weights and form a graph. If the edge forms a cycle and doesn't have weight <= 0, remove it, else add to the graph. Final answer is (Total sum of edge weights — sum of weights of included edges of graph).

    Submission

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

Is F brute force?

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

    Kinda, you can bruteforce all edges inside the shortest path (at most $$$N-1$$$), for all other edges the answer remains the same.

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

    Yeah, it's kinda brute force.

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

C was the hardest for me :_:

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

I use "divide and conquer" + "max,add convolution " to solve H. Bug why the answer is convex QwQ?

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

    ngl most of the in-contest solvers who use convexity often rely on proof by AC :P

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

    I saw submissions using priority queue also where they are greedily converting to red which gives maximum profit. Btw can you please elaborate your solution. Thanks

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

      dp[l][r][x][cl][cr] means considering the range from l to r , you use x red ,cl,cr is the color of two endpoints .

      You can speed it up use divide and conquer .

      Now you only need to solve the following problem in O(n):

      Given A,B,(A,B is convex ),find C. Where

      $$$ C[i]=\max_{x+y=i} (A[x]+B[y]) $$$

      you can find the implement in my code :

      https://atcoder.jp/contests/abc218/submissions/25770296.

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

    I always thought that it is impossible to make $$$(max, +)$$$ convolution faster than $$$ O(n \sqrt{n} ) $$$. What is the complexity of your solution?

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

      O(n log n).

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

        Oh, so you are using convexity of the arrays to make $$$(max, +)$$$ convolution faster. That's interesting, thanks!

        If someone is interested: here you can find more about this problem.

»
3 years ago, # |
Rev. 3   Vote: I like it +11 Vote: I do not like it

I'm pretty sure that once upon a time I've seen the problem like today's F with a weighted graph and $$$ N, M \leq 2 \cdot 10^5 $$$. Does anyone remember a similar problem and has a link to it? I think that it was at Hackerrank, but not sure.

UPD: It's basically this problem. Thanks to this solution from AtCoder :)

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

    True , I too think I have seen something very similar to this somewhere.

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

    Do you know how to solve the question for your constraints ($$$N, M \le 2 \cdot 10^5$$$)?

    • »
      »
      »
      3 years ago, # ^ |
      Rev. 2   Vote: I like it +13 Vote: I do not like it

      I do! Let's take any shortest path $$$ P = ( e_1, \dots, e_k ) $$$ between $$$ s $$$ and $$$ t $$$. Obviously, we already know the solution for the edges not in $$$ P $$$. Now, for every $$$ i $$$ we want to omit the edge $$$ e_i $$$ in the shortest possible way. Let's take a moment to think what does it actually mean "to omit" $$$ e_i = (v_1, u_1) $$$. It means that there should exist another edge $$$ e = (v_2, u_2) $$$ such that $$$ d(s, v_2) \leq d(s, v_1) $$$ and $$$ d(s, v_2) + len(e) > d(s, v_1) $$$. Between all such edges we want to find one that minimizes $$$ d(s, v_2) + len(e) + d(u_2, t) $$$. We can calculate the distances from $$$ s $$$ and to $$$ t $$$ at the beginning of the algorithm and create a sweep-line-like algorithm which will be solving the problem for all edges $$$ e_i $$$ one by one by maintaining all the "good" edges $$$ e $$$ at a given moment in time. We can do that with a segment tree (probably, an ordinary set is enough but I didn't bother much). The final complexity would be $$$ O ((N + M) \log N) $$$.

      My explanation is probably horrible, so I implemented the solution. Enjoy!

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

    Link

    I solved this problem few days back. I copied my code to find the edges that will always be in the shortest path.

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

      Thanks! Although your problem is similar and uses a lot of related ideas, I don't really see how it implies the today's F. How do you proceed after you found the edges that always are in a shortest path?

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

        There can be atmost n-1 such edges.

        For each such edge, I ran a bfs from 1 and didn't use that edge. The shortest distance of n (if n is reachable) will be the answer for that edge.

        • »
          »
          »
          »
          »
          3 years ago, # ^ |
          Rev. 2   Vote: I like it +8 Vote: I do not like it

          Yes, but this gives us $$$ O(N + M) $$$ per edge, so the total complexity is $$$ O(N \cdot (N + M) ) $$$, right?

          UPD: I probably misread your comment and thought that you used the linked problem to solve today's F. But I was wrong and you just used a part of the solution to identify the "critical" edges. If I understand you correctly, you could have used the edges in any shortest path and get the same complexity theoretically. Anyway, thanks for sharing your solution!

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

            Yes, actually I found ABC's F pretty much similar to this problem except one idea. So I shared it. But it seems you are looking for same problem with different constraints. So this problem isn't that relevant.

»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

en_translator is still working on translating today's editorial for H. Great thanks!

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

problem E difficulty has gone down by a lot recently.

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

    Thats because the quantity of tasks has also increased i Guess..

»
3 years ago, # |
  Vote: I like it +10 Vote: I do not like it

I think my answer is wrong for problem C, but It has been accepted.

Those test cases are giving me : Yes.

3
. # .
# . .
. . .
. . #
# . .
. . .
5
. . . . .
. . . . .
. . # . .
. . # # #
. . # . .
. . . . .
. . . . .
. . . # #
. . . # #
. . . # .

Am I wrong ?

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

    i got No on both TC you mentioned

»
3 years ago, # |
Rev. 4   Vote: I like it -13 Vote: I do not like it

I am getting AC on 19-TC and WA only on one TC (Case name — hand_04.txt) in problem C. either give me this TC from somewhere TT or please debug my code.

»
3 years ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

Please, can somebody help with my solution for G. I did everthing as in the editorial but used ordered_set instead of multiset or BIT. I spent almost an hour trying to find problem, but I couldn't.

UPD: I found problem. It was because erase in ordered_multiset doesn't work. So if you want to erase you need to erase using iterator of lower_bound, but I forgot that in ordered_multiset the lower_bound and upper_bound functions are swapped.

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

    Thanks for the info , I was also having the same error but as I was unable to figure out the reason I switched code from Multiset to set of pair.