chokudai's blog

By chokudai, history, 5 weeks 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

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Good luck to everybody!

»
5 weeks 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 ?

  • »
    »
    5 weeks 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.

»
5 weeks 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 ;)

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice problemset, any hints on problem H?

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How to solve G?

    • »
      »
      »
      5 weeks 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.

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

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

        • »
          »
          »
          »
          »
          5 weeks 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.

    • »
      »
      »
      5 weeks 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).

  • »
    »
    5 weeks 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...

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        5 weeks 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}$$$.

»
5 weeks 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 :(

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      5 weeks 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.

      • »
        »
        »
        »
        5 weeks 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
        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Thats a lot code for a C in abc.

          • »
            »
            »
            »
            »
            »
            5 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Expecting for a shorter solution then...

            • »
              »
              »
              »
              »
              »
              »
              5 weeks ago, # ^ |
                Vote: I like it 0 Vote: I do not like it
              smol?
    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it -19 Vote: I do not like it
    • »
      »
      »
      5 weeks 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.

  • »
    »
    5 weeks 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)

  • »
    »
    5 weeks 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

    • »
      »
      »
      5 weeks 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.

      • »
        »
        »
        »
        5 weeks 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.

        • »
          »
          »
          »
          »
          5 weeks 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).

    • »
      »
      »
      5 weeks 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

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

plz explain C,D

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    check out the editorials

  • »
    »
    5 weeks ago, # ^ |
    Rev. 3   Vote: I like it +3 Vote: I do not like it
    C
  • »
    »
    5 weeks 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++)
    • »
      »
      »
      5 weeks 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.

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yeah I know my implemention is not that simple :(

»
5 weeks 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.

»
5 weeks 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
  • »
    »
    5 weeks 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)$$$.

  • »
    »
    5 weeks 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

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Is F brute force?

  • »
    »
    5 weeks 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.

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

    Yeah, it's kinda brute force.

    Spoiler
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

C was the hardest for me :_:

»
5 weeks 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?

  • »
    »
    5 weeks 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

  • »
    »
    5 weeks 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

    • »
      »
      »
      5 weeks 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.

  • »
    »
    5 weeks 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?

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

      O(n log n).

      • »
        »
        »
        »
        5 weeks 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.

»
5 weeks 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 :)

  • »
    »
    5 weeks 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.

  • »
    »
    5 weeks 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$$$)?

    • »
      »
      »
      5 weeks 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!

  • »
    »
    5 weeks 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.

    • »
      »
      »
      5 weeks 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?

      • »
        »
        »
        »
        5 weeks 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.

        • »
          »
          »
          »
          »
          5 weeks 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!

          • »
            »
            »
            »
            »
            »
            5 weeks 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.

»
5 weeks 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!

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I am getting WA on C on only 2 cases. Can someone help me figure it out?. This is my code. I used coordinate compression on both the matrices and checked if both the compressed matrices were equal.Thanks ;)

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem D is exactly same as this problem on Codechef.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

problem E difficulty has gone down by a lot recently.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

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

Could anyone please point out where this solution for C fails.

Thanks.

»
5 weeks 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 ?

»
5 weeks 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.

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

    Sorry I tried to help !!

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You have a problem in this line :

    int diff=abs(s[0].first — t[0].first) + abs(s[0].second — t[0].second);

    test case :

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

    you are getting Yes.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I modified your code and here is the submission: https://atcoder.jp/contests/abc218/submissions/25796147

    Basically, need to change 2 things: 1. remove Abs() 2. Use diffx and diffy in parallel instead of diff.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks, it worked! Also, just removing abs() worked. We don't need to divide diff into diffx and diffy.

»
5 weeks 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.

  • »
    »
    5 weeks 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.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Why checking rotation only is not sufficient in problem C?

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Because, according to the problem statement, the shapes can be matched by rotations and translations.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    never mind :))

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Here is a way to solve problems C and D on ABC 218.


Problem C can be solved as a geometry problem, where you basically:

  • find the figures' outline boxes,
  • rotate the first figure's box,
  • compare the resulting boxes for all rotations.

Here is my submission for C with neat organization & comments.


Problem D can be solved by using DFS to find the four points.

  • for every point, store all points that have the same X in one vector, same Y in another vector,
  • use DFS on every point to find the next point with the same X or Y (alternating between finding X or Y),
  • make sure the four points we find aren't repeated by:
    • finding the same X for the first point,
    • making sure the X and Y coordinates are increasing for the first 3 points (left-top, left-bottom, right-bottom).

My submission for D using DFS.

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

I tried something out for C
Attached the approach here: https://atcoder.jp/contests/abc218/submissions/26074628