We will hold AtCoder Beginner Contest 157.
- Contest URL: https://atcoder.jp/contests/abc157
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20200301T2100&p1=248
- Duration: 100 minutes
- Number of Tasks: 6
- Writer: kort0n
- Rated range: ~ 1999
- The point values will be 100-200-300-400-500-600.
We are looking forward to your participation!
Clashes with CF Round 625 :(
Why it is not showing in the upcoming contests list?
This calendar is displaying it as Japanese only, could this be the reason?
Are you chodukai ??
Are u inspired by I_love_Tanya_Romanova ?....
I love this influx of ABCs from AtCoder! Thank you!!
@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.
Is there any update in the timings or not because of clash with CF round 625 ?
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.
It's been fixed.
Clash : (
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?
kort0n That's a serious problem. Considering it's a somewhat recent round.
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.
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.
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?
That's why having some Div. 2/3 testers is important.
Is D related to find all set of independent vertices?
U can solve it using disjoint set union data structure.
It's related to finding the number of nodes per component
Reference: https://atcoder.jp/contests/abc157/submissions/10472885
How to solve F ?? Any hint ??
for any vertex ,i it's ans= size of component to which it belongs — no of adjacent children — no of bad edges in it's component — 1
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
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.
The easier way is to bsrch + find all pairs of intersections and check if they are present in atleast k circles.
even though, max-clique is NP. how do you solve it?
Max Clique can be solved in $$$O(3 ^ { n/3})$$$ using Bron–Kerbosch algorithm and it works faster for random graphs.
Solution for E
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.)
https://atcoder.jp/contests/abc157/submissions/10417928
Thank you very much!
I finally understood how to get that circle.
getting wrong answer in B only in last test case anyone can help
your solution
https://atcoder.jp/contests/abc157/submissions/10473385 I checked for both diagonals
Your code is failing in this test case
The answer is Yes but you print No
Just check with a simple for loop for each row and column and then manually for 2 diagonals.
There are two diagonals in a matrix :)
Simply check for all possible rows and columns of size 3 and left and right body diagonal of the matrix.
How two solve F?
Nice, contest. Btw, what is definition of beginner according to AtCoder? (D — dsu, E — segment trees, F = I don't know what)
D and E don't require those data structures. D can be solved with DFS/BFS and for E you can use sets
How can E be solved with just sets?
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.
You know the alphabet consists of 26 letters, so...
For each letter you can use a set, containing every position where it appears on the string. You can keep track of these positions while performing type 1 queries.
For a query of type 2 $$$l$$$, $$$r$$$ the answer will be at most 26. For each letter you only need to know if at least one is present on that range. Check if there is a position $$$i$$$ in the set such that $$$l\leq i\leq r$$$ (this can be accomplished with lower bound)
The complexity will be $$$\mathcal{O}(26\cdot q\log{n})$$$, which is $$$\mathcal{O}(q\log{n})$$$
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).
Problem B seems a bit tough for me...considering recent B problems
It's an implementation problem :)
Can someone please explain, how are we calculating in Problem F, "there exits atleast K circles having some common points" ?
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:
Can you please tell why are we taking centers of circles as well?
I have the same doubt. Also, how can the union of k disk be empty?
Consider 3 circles, each with radius $$$1$$$, and centers at $$$(-1,0)$$$, $$$(0,0)$$$, and $$$(1,0)$$$. They coincide at $$$(0,0)$$$
Intersection of circle with centers (-1,0) and (1,0) is (0,0). Why are we adding centers then ?