Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

### chokudai's blog

By chokudai, history, 4 months ago, ,

We will hold AtCoder Beginner Contest 157.

We are looking forward to your participation!

• +49

 » 4 months ago, # |   -24 At last i am first to write a comment at something.
 » 4 months ago, # |   -18 Good luck to all participants!
 » 4 months ago, # |   +9 Clashes with CF Round 625 :(
 » 4 months ago, # |   +30 Why it is not showing in the upcoming contests list?
•  » » 4 months ago, # ^ |   +3 This calendar is displaying it as Japanese only, could this be the reason?
 » 4 months ago, # |   +6 Are you chodukai ??
•  » » 4 months ago, # ^ |   0 Are u inspired by I_love_Tanya_romanova ?....
 » 4 months ago, # |   +12 I love this influx of ABCs from AtCoder! Thank you!!
 » 4 months ago, # |   0 @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.
 » 4 months ago, # |   0 time clash of codeforces round 625 and Atcoder ABC 157
 » 4 months ago, # |   0 Is there any update in the timings or not because of clash with CF round 625 ?
 » 4 months ago, # |   +8 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.
•  » » 4 months ago, # ^ |   0 It's been fixed.
 » 4 months ago, # |   0 ABC 157 is not shown in the "Upcoming Contests" column in the left.
 » 4 months ago, # |   0 Clash : (
 » 4 months ago, # |   +13 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?
•  » » 4 months ago, # ^ |   -18 kort0n That's a serious problem. Considering it's a somewhat recent round.
•  » » » 4 months ago, # ^ |   +21 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.
•  » » » » 4 months ago, # ^ |   0 I personally don't think it is a big deal if easy problems coincideThis 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.
 » 4 months ago, # |   0 Is D related to find all set of independent vertices?
•  » » 4 months ago, # ^ |   0 U can solve it using disjoint set union data structure.
•  » » 4 months ago, # ^ |   0 It's related to finding the number of nodes per component
•  » » 4 months ago, # ^ |   +1 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.
 » 4 months ago, # |   0 How to solve F ?? Any hint ??
•  » » 4 months ago, # ^ |   0 i think it is related to find (X,Y) such that it is center of circle with all (xi,yi) inside it
 » 4 months ago, # |   +3 Solution for Dfor 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
 » 4 months ago, # |   0 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?
•  » » 4 months ago, # ^ | ← Rev. 2 →   +26 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.
•  » » 4 months ago, # ^ |   +8 The easier way is to bsrch + find all pairs of intersections and check if they are present in atleast k circles.
•  » » 4 months ago, # ^ |   0 even though, max-clique is NP. how do you solve it?
•  » » » 4 months ago, # ^ | ← Rev. 2 →   0 Max Clique can be solved in $O(3 ^ { n/3})$ using Bron–Kerbosch algorithm and it works faster for random graphs.
 » 4 months ago, # |   0
 » 4 months ago, # | ← Rev. 4 →   0 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.)
•  » » 4 months ago, # ^ |   0
•  » » » 4 months ago, # ^ |   +10 Thank you very much!I finally understood how to get that circle.
 » 4 months ago, # |   0 getting wrong answer in B only in last test case anyone can help
•  » » 4 months ago, # ^ |   0 your solution
•  » » » 4 months ago, # ^ |   0 https://atcoder.jp/contests/abc157/submissions/10473385 I checked for both diagonals
•  » » » » 4 months ago, # ^ |   +3 Your code is failing in this test case 64 40 83 44 17 41 58 49 38 7 58 83 88 17 40 94 60 The answer is Yes but you print No
•  » » » » 4 months ago, # ^ |   0 Just check with a simple for loop for each row and column and then manually for 2 diagonals.
•  » » » » » 4 months ago, # ^ |   0 Yes done that it's accepted
•  » » 4 months ago, # ^ |   +6 There are two diagonals in a matrix :)
•  » » 4 months ago, # ^ |   0 Simply check for all possible rows and columns of size 3 and left and right body diagonal of the matrix.
 » 4 months ago, # |   +5 How two solve F?
 » 4 months ago, # |   +1 Nice, contest. Btw, what is definition of beginner according to AtCoder? (D — dsu, E — segment trees, F = I don't know what)
•  » » 4 months ago, # ^ |   +3 D and E don't require those data structures. D can be solved with DFS/BFS and for E you can use sets
•  » » » 4 months ago, # ^ |   0 How can E be solved with just sets?
•  » » » » 4 months ago, # ^ |   +5 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.
•  » » » » 4 months ago, # ^ | ← Rev. 2 →   +3 You know the alphabet consists of 26 letters, so... SpoilerFor 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})$
•  » » » » 4 months ago, # ^ |   0 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).
 » 4 months ago, # |   0 How to solve Problem C? Could you show me your code?
 » 4 months ago, # |   0 Solution for E using STL set : https://atcoder.jp/contests/abc157/submissions/10493060
 » 4 months ago, # |   0 Problem B seems a bit tough for me...considering recent B problems
•  » » 4 months ago, # ^ |   0 It's an implementation problem :)
 » 4 months ago, # |   0 Can someone please explain, how are we calculating in Problem F, "there exits atleast K circles having some common points" ?
•  » » 4 months ago, # ^ |   +11 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
•  » » » 4 months ago, # ^ |   +3 Can you please tell why are we taking centers of circles as well?
•  » » » » 4 months ago, # ^ |   0 I have the same doubt. Also, how can the union of k disk be empty?
•  » » » » 4 months ago, # ^ |   0 Consider 3 circles, each with radius $1$, and centers at $(-1,0)$, $(0,0)$, and $(1,0)$. They coincide at $(0,0)$
•  » » » » » 4 months ago, # ^ |   0 Intersection of circle with centers (-1,0) and (1,0) is (0,0). Why are we adding centers then ?
 » 4 months ago, # | ← Rev. 2 →   0 Supplementary editorial and sample codes for last 4 problems AtCoder_ABC_157
•  » » 3 months ago, # ^ |   0 Thanks a lot for explanation it helped me a lot.
»
2 months ago, # |
0

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).