chokudai's blog

By chokudai, history, 8 months 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

»
8 months ago, # |
  Vote: I like it -24 Vote: I do not like it

At last i am first to write a comment at something.

»
8 months ago, # |
  Vote: I like it -18 Vote: I do not like it

Good luck to all participants!

»
8 months ago, # |
  Vote: I like it +9 Vote: I do not like it

Clashes with CF Round 625 :(

»
8 months ago, # |
  Vote: I like it +30 Vote: I do not like it

Why it is not showing in the upcoming contests list?

»
8 months ago, # |
  Vote: I like it +6 Vote: I do not like it

Are you chodukai ??

»
8 months ago, # |
  Vote: I like it +12 Vote: I do not like it

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

»
8 months 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.

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

time clash of codeforces round 625 and Atcoder ABC 157

»
8 months 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 ?

»
8 months 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.

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

ABC 157 is not shown in the "Upcoming Contests" column in the left.

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Clash : (

»
8 months 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?

  • »
    »
    8 months 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.

    • »
      »
      »
      8 months 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.

      • »
        »
        »
        »
        8 months 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.

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Is D related to find all set of independent vertices?

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    U can solve it using disjoint set union data structure.

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    8 months 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

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve F ?? Any hint ??

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i think it is related to find (X,Y) such that it is center of circle with all (xi,yi) inside it

»
8 months ago, # |
  Vote: I like it +3 Vote: I do not like it
Solution for D
»
8 months 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

  • »
    »
    8 months 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.

  • »
    »
    8 months 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.

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it
»
8 months 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.)

»
8 months 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

»
8 months ago, # |
  Vote: I like it +5 Vote: I do not like it

How two solve F?

»
8 months 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)

  • »
    »
    8 months 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

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How can E be solved with just sets?

      • »
        »
        »
        »
        8 months 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.

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

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

        Spoiler
      • »
        »
        »
        »
        8 months 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).

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve Problem C? Could you show me your code?

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
8 months 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" ?

  • »
    »
    8 months 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
    • »
      »
      »
      8 months 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?

      • »
        »
        »
        »
        8 months 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?

      • »
        »
        »
        »
        7 months 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)$$$

        • »
          »
          »
          »
          »
          7 months 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 ?

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

Supplementary editorial and sample codes for last 4 problems AtCoder_ABC_157

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks a lot for explanation it helped me a lot.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone tell where did i do wrong ?

include<bits/stdc++.h>

using namespace std; int main() {long long n,q,index,insert; cin>>n>>q; string s(n,'0'); map<long long,long long>f; while(q--) { cin>>index>>insert;index--; if(index==0 and insert==0)continue; else if(f[index]>0) s[index]=(min((long long)(s[index]-'0'),insert))+'0'; else s[index]=(insert+'0'),f[index]++; } if(s[0]=='0' and n!=1)return cout<<-1,0; return cout<<s,0; } THIS IS THE SOLUTION I THOUGHT FOR THE 3RD PROBLEM (Guess The Number).

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

How to solve C?