chokudai's blog

AtCoder Beginner Contest 157 Announcement
By chokudai, history, 5 years ago, In English

We will hold AtCoder Beginner Contest 157.

We are looking forward to your participation!

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

Comments Comments (52)
| Write comment?
»
5 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Clashes with CF Round 625 :(

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

Why it is not showing in the upcoming contests list?

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

Are you chodukai ??

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

I love this influx of ABCs from AtCoder! Thank you!!

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

@chokudai Could you update the timing of the contest. So that contestants can participate in both the rounds that are "Codeforces Round #625" and "ABC 157". As there is a clash between the two.

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

Is there any update in the timings or not because of clash with CF round 625 ?

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

AtCoder CEO declares that AtCoder won't change the contest durations, unfortunately.

Seems that some participants are worried that the contest is not shown on English page, but all the rated contests in AtCoder provides English problem statements (otherwise it will not be fair in terms of fairness of ratings) so please don't worry about it.

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

Clash : (

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

I don't want to tell this but task E is the replica of 1234D - Distinct Characters Queries. And all of those who are thinking I am lucky to find this out, I didn't submit a solution. There is no point for me to submit a code that I didn't write :). And as usual How to solve D?

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

    kort0n That's a serious problem. Considering it's a somewhat recent round.

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

      I personally don't think it is a big deal if easy problems coincide. Also, it is not hard to accidentally write an easy problem that someone has come up with before.

      Realistically, not many grandmasters read those Div 3 problems, so it's likely no organizer had seen it, either.

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        I personally don't think it is a big deal if easy problems coincide

        This is problem E in the AtCoder round. F was a hard problem, so E would be a deciding problem for rankings/ratings. In any case, the problem is a potential Codeforces Div2C level problem. So it isn't exactly an easy problem, like CF Div2A. If this was problem A, B or C in an AtCoder Beginner round, or of CF Div2A level, I would definitely agree with you.

        Also, it is not hard to accidentally write an easy problem that someone has come up with before.

        I never said that kort0n copied the problem from the Div. 3 round. Obviously it's just coincidence that the exact same problem had occured before. Yet in the future, don't you think some measures should be taken to reduce the chances of this happening again?

        Realistically, not many grandmasters read those Div 3 problems, so it's likely no organizer had seen it, either.

        That's why having some Div. 2/3 testers is important.

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

Is D related to find all set of independent vertices?

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

    U can solve it using disjoint set union data structure.

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

    It's related to finding the number of nodes per component

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    • Build components using DSU (merge each friendship — find common parent, combine sizes).
    • Set size of return for each index to (size_of_its_component — 1). The 1 is subtracted to exclude itself from the component size.
    • For each friendship, subtract 1 for both A[i] and B[i]. This is because we want to find new friendships, and exclude existing ones.
    • For each blockship, subtract 1 for both C[i] and D[i] from their sizes, as these need to be excluded.

    Reference: https://atcoder.jp/contests/abc157/submissions/10472885

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

How to solve F ?? Any hint ??

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

What is wrong with this approach for problem F? First binary search on time $$$T$$$. Let's build a graph where there is an edge from $$$i$$$ to $$$j$$$ if and only if the circle with center $$$p_i$$$ and radius $$$T / c_i$$$ intersects with the circle with center $$$p_j$$$ and radius $$$T / c_j$$$. Then check if the maximum clique of the graph is greater than or equal to $$$k$$$ or not. I passed $$$26$$$ test cases with this approach but couldn't pass the others. What is wrong with my approach?

Submission: https://atcoder.jp/contests/abc157/submissions/10467423

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

    For three meat point A, B, C.

    The area that works for meat A&B, B&C, C&A may not intersects.

    For example, if the meats form a Equilateral triangle, the minimum distance to reach all points should be larger than half of the edge length.

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

    The easier way is to bsrch + find all pairs of intersections and check if they are present in atleast k circles.

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

    even though, max-clique is NP. how do you solve it?

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

Solution for E

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

For problem F, there's another solution without binary searching the answer.

(Assume $$$K \geq 2$$$)
If we define the "distance" from point $$$P$$$ to the meat as the time required to heat the meat from point $$$P$$$. Then we can prove that the best choice for the heat source must be a point such that its distance to some $$$x$$$ meats are equal ($$$x$$$ = 2 or 3). So simply enumerate 2 or 3 meats, find such points and choose the answer from all of them.

This is the solution I came up with and it's also the second solution in the editorial. However, I don't know how to find such points when $$$x = 3$$$. Could anyone help me?

(I believe the editorial doesn't describe this part. Also, all the AC submissions I picked used binary search.)

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

getting wrong answer in B only in last test case anyone can help

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

How two solve F?

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

Nice, contest. Btw, what is definition of beginner according to AtCoder? (D — dsu, E — segment trees, F = I don't know what)

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

    D and E don't require those data structures. D can be solved with DFS/BFS and for E you can use sets

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

      How can E be solved with just sets?

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

        It just occurred to me you can have set for each letter its positions and then for a query do a lower_bound on left and count it if it is <= right.

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

        You know the alphabet consists of 26 letters, so...

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

        Just create an array of sets of size 26 and store indices of every character corresponding to that set. Handle updates by simply erasing and inserting and for the query of type 2 iterate from 0 to 25 and check if there's an element present in the set lower than R this can be done using lower_bound function. The overall complexity will be O(26*Q*logN).

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

Problem B seems a bit tough for me...considering recent B problems

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

Can someone please explain, how are we calculating in Problem F, "there exits atleast K circles having some common points" ?

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

    From the editorial:

    Here, if a union of K disks X is non-empty, then it corresponds to a disk, or a union of some disjoint multiple disks.

    In the former case, the center coordinate of the disk is included in X, and in the latter case, there exist two disks such that the intersection of their boundary circles is included in X.

    In another word:

    • $$$S = $$${ }
    • Add the center of every circle to $$$S$$$
    • for any two circles $$$x, y$$$: add the intersection of $$$x$$$ and $$$y$$$ to $$$S$$$
    • for every point $$$P$$$ in $$$S$$$: check if $$$P$$$ is located in at least $$$K$$$ circles
    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Can you please tell why are we taking centers of circles as well?

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

        I have the same doubt. Also, how can the union of k disk be empty?

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

        Consider 3 circles, each with radius $$$1$$$, and centers at $$$(-1,0)$$$, $$$(0,0)$$$, and $$$(1,0)$$$. They coincide at $$$(0,0)$$$

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

          Intersection of circle with centers (-1,0) and (1,0) is (0,0). Why are we adding centers then ?

          → Reply