snuke's blog

By snuke, history, 5 years ago,

AtCoder Beginner Contest 131 is on this Saturday.

The point values will be 100-200-300-400-500-600.

• +34

| Write comment?
 » 5 years ago, # |   +2 How to solve last problem ? I have some ideas ,but i had a little time to think on them.
•  » » 5 years ago, # ^ |   0 Quite similar to the problem called chemical table, from CF 1012, EJOI 2018. Trying that first can help to understand why to use DSU.
 » 5 years ago, # |   -8 DSU
 » 5 years ago, # |   +5 How to solve F?
•  » » 5 years ago, # ^ |   0 DSU
•  » » » 5 years ago, # ^ |   +5 Please explain more.
•  » » » » 5 years ago, # ^ |   +6
•  » » » » » 5 years ago, # ^ |   0 how to solve e? pls also explain that.
•  » » » » » » 5 years ago, # ^ |   0 The answer is -1 only if K > (N-1) choose 2. We will give a construction for the remaining K below. To prove that higher K values are impossible, note that any two vertices connected by an edge will have distance 1, so we can't use pairs connected by edges. Since the graph is connected, we must have at least N-1 edges, so we can have at most N choose 2 — (N-1) = (N-1) choose 2 pairs.If K = 0, output a complete graph. Otherwise, suppose that C choose 2 <= K < (C+1) choose 2. Call C vertices "outside vertices" and the remaining vertices "inside vertices". Connect all of the inside vertices to all other vertices (in other words, add edges between all pairs of vertices except those that are both outside). We can see that this gives C choose 2 pairs with distance 2, since the set of pairs with distance 2 is exactly the set of pairs of outside vertices. If K > C choose 2, remove one of the inside vertices. (If there is only one inside vertex, C = N-1, which would imply K > (N-1) choose 2, and we already established that we can ignore those cases, so there will still be at least one inside vertex afterwards.) Then, connect it to N — K + C choose 2 — 1 other vertices, including at least one of the remaining inside vertices. Obviously, this final vertex will have distance 0 to itself and distance 1 to all vertices it is connected to, but it has distance 2 to all other vertices, so this adds N — 1 — (N — K + C choose 2 — 1) = K — C choose 2 valid pairs, completing the construction.
•  » » » » » » » 5 years ago, # ^ |   0 thank you for you explaination :) it helped me a lot
 » 5 years ago, # |   0 can anyone tell me the approach for problem e.
•  » » 5 years ago, # ^ |   +1 upper bound of k is (n-2)*(n-1)/2 This is a single vertex (n) is connected to all n-1 vertices. Now if we want to decrease this value to reach k we need to choose a vertex and connect it to unconnected vertices (each edge decreases number of pairs by one) so perform this operation till we reach value k. https://atcoder.jp/contests/abc131/submissions/6072403 my submission.
•  » » 5 years ago, # ^ |   0 So let's find the maximal value of k: it is (1+2+..+n-2).Why? Because with this graph then k will be maximized: 1-2 1-3 1-4 1-... 1-nAs there will be 2-1-3, 2-1-4, 2-1-5, .. 2-1-n, 3-1-4, 3-1-5 ... (n-1)-1-n road of distance 2.So if k>mx (mx=1+2+..+n-2). Print -1else if k==mx we will print the above edges else if k using namespace std; typedef pair ii; vector ans; int n,k,mx=0; int main() { cin >> n >> k; for (int i=1;i<=n-2;i++) mx+=i; if (k>mx) { cout << "-1"; return 0; } if (1) { for (int i=2;i<=n;i++) ans.push_back(ii(1,i)); int d=mx-k; for (int i=2;i
•  » » » 5 years ago, # ^ |   0 to decrease k are you picking a single vertex each time and fixing it and then connecting it to others till it is == k. ?
•  » » » » 5 years ago, # ^ |   0 I will make edges: 2-3 2-4 2-5 2-... 2-n, 3-4 3-5 3-6 3-... 3-n, 4-5 4-6 and so on until it is ==k (the above code is d==0)
•  » » » » » 5 years ago, # ^ | ← Rev. 2 →   +1 thanks i understood it. i set the upper bound to n-2 for the graph like 1 -- 2 -- 3 — .. -- nand then start adding edges. it gave wa for almost half of test cases.
•  » » » » » » 5 years ago, # ^ |   0 At first I make the same mistake as you too. And I tried to draw some more special type of graphs and finally figured the solution
•  » » 5 years ago, # ^ | ← Rev. 2 →   +18 Maximum number of pairs can be (n-1)*(n-2)/2, this will happen when the graph is a tree and a single node is connected to all other nodes and hence the answer (n-1)C2, if k is greater than this value then our output will be "-1", now let there be n*(n-1)/2 edges in the graph so this will be the answer for case k=0, now consider a node say "2" if we start removing its edges one by one then the value of k will increase by one with every removal,so we have the answer for k=0 to k= n-2 because we can remove atmost (n-2) edges because the graph should be connected, now lets say that we don't remove the edge (1,2) in the above step and now consider node 3, if we start removing its edges one by one(except the edge that is connected to 1) the value of k starts increasing by 1 with every removal, we can remove atmost (n-3) edges from this node, so we have the answer for k=n-1 to k=2*n-5, similarly you can remove edges for node 4, 5 and so on, you can maintain an adjacency matrix to implement the above algo, here is the link to my code.I hope this helps :)
•  » » » 5 years ago, # ^ |   +3 Thanks. i understood it.
•  » » » 5 years ago, # ^ |   +3 +100 for the logic and explanation. Kudos!!
•  » » » » 5 years ago, # ^ |   +3 Thank You, this encourages me to write better :D
•  » » 5 years ago, # ^ |   0 first of all , lets see what is the maximum number of pairs that can be formed with distance equal to 2 ,if k exceeds that value simply return -1. Max_dist_2 = ((n-1)*(n-2))/2; Now , edges_to_draw = n-1 + (Max_dist_2 -k); Now start drawing edges from node 1 to all (now decrease edges_to_draw by n-1), then for every edge you draw between two consecutive node decrease edge_to_draw by 1 .Repeat this till edges_to_draw becomes 0. BAM....Your Graph is Ready!!!!
•  » » 5 years ago, # ^ |   0 There are a lot of method . I will tell about my solution. If there are n verticles so we have n*(n-1)/2 pairs that theoretically can have a short distance 2 ,but graph must be connected . So i constructed a graph where all edges are 1 j (2<=j<=n) . This graph will have (n*(n-1)/2)-(n-1) pairs and their distance are 2 . It is maximal number of pairs can be. So if k>(n*(n-1)/2)-(n-1) answer is -1 . if k<(n*(n-1)/2)-(n-1) we must create ((n*(n-1)/2)-(n-1))-k triangles (cycles) .
 » 5 years ago, # |   +13 The last problem reminded me this problem: 1012B
 » 5 years ago, # |   0 lots of RE in 3rd problem in python 3.4 my code seems right.
•  » » 5 years ago, # ^ |   +8 from math import gcd -:: python 3.5 or above from fractions import gcd -:: python 3.4 I think this is the problem.
 » 5 years ago, # | ← Rev. 4 →   +8 Weak tests on F.I got AC with an $O(N^2)$ solution.https://atcoder.jp/contests/abc131/submissions/6073267My code is quadratic in a case where all points have the same y-coordinate.
 » 5 years ago, # |   +11 when we get editorial?
•  » » 5 years ago, # ^ |   +2 They have a solution in brainf**k for problem A lmao
 » 5 years ago, # |   0 C was remarkably similar to this problem. (Unfortunately, this would have been hard to fix because the other problem appeared on a contest just a few days back.) As others have mentioned, a harder version of F appeared on an Educational Round not too long ago. Moreover, D is also relatively standard--I can't come up with the source right now, but I've seen very similar problems on at least a few occasions.
 » 5 years ago, # |   +8 Can someone "explain" how to solve F?
•  » » 5 years ago, # ^ | ← Rev. 2 →   +10 Consider the graph where the given points are vertices and two vertices are connected if and only if their corresponding points have the same X-coordinate or the same Y-coordinate. The answer is the result when N is subtracted from the sum over all connected components in this graph of the product of the numbers of distinct X and Y coordinates represented in that component.Proving that the connected components are independent is fairly easy. Then, the number of points created based on the starting points in each connected component is the product of the numbers of distinct X-coordinates and Y-coordinates in the component. We can prove by induction that we can always create all of these points.Note that we cannot construct the entire graph, since it could have O(N^2) edges. However, since we just need to run a BFS to construct connected components, this doesn't turn out to be a huge obstacle--we just store lists of points at each X or Y coordinate and use those lists to deal with transitions rather than building an adjacency list.As an aside, this was essentially an easier version of this problem. The same idea is outlined in the beginning of its editorial.
•  » » » 5 years ago, # ^ |   0 any link to your submission ?
•  » » » » 5 years ago, # ^ |   0 See here.
 » 5 years ago, # |   0 Can anyone tell me what's wrong with this submission, it's failing one test?Submission for Problem CThanks in advance!
•  » » 5 years ago, # ^ |   +8 Seems to be a precision issue. To calculate $\lceil\frac{A}{B}\rceil$ without converting to doubles you can do (A+B-1)/B.
 » 5 years ago, # |   +1 What does evenly divided by C and D signify in problem C?
•  » » 5 years ago, # ^ |   0 A number X is evenly divisible by another number Y if X can be divided by Y with no remainder. (In programming terms, this is equivalent to X % Y == 0.)
•  » » » 5 years ago, # ^ |   +1 Thank you so much. I was thinking that X%Y == 0 && X/Y should be even.
 » 5 years ago, # |   0 How to solve Problem F using DSU?
 » 5 years ago, # |   0 how to solve porblem F?
•  » » 5 years ago, # ^ |   0 Thx, I've just solved it.
 » 5 years ago, # |   +5 The time of english page in AtCoder is still broken. pls fix it.
 » 5 years ago, # |   0 How to solve C? I tried different approaches but was constantly getting WA.
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 The answer is: B-A+1 — (# integers of that are divisible by C or D)The last term = (# integers that are divisible by C) + (# integers that are divisible by D)- (# integers that are divisible by C and D <==> divisible by lcm(C,D))Here's my submission: https://atcoder.jp/contests/abc131/submissions/6064511
•  » » » 5 years ago, # ^ |   0 hi can you explain how you find divisible count ? and why your solution is working ?
•  » » » » 5 years ago, # ^ |   0 Hello,The divisible count(Going to propose a better way than the one I submitted, to calculate it)Let F(A,X) be the number of multiples of X in the range [1;A].The number of multiples of X in the range[L;R] will be: F(L,R,X) = F(R,X) - F(L-1,X) Finally it's not hard to see that F(A,X) = A/XWhy is it workingI'm going to explain it from scratch, and hopefully you'll see by yourself why it works.Given the two integers C and D from the problem, any integer X is either: divisible by D and not by C (1st type) divisible by C and not by D (2nd type) divisible by C and D (3rd type) divisible by neither C nor D (4th type) The problem asks for the number of integers of the fourth type, in the range [A;B].That will be equal to: the total number of integers in the range[A;B] - the number of integers of the 1st type in the range [A;B] - the number of integers of the 2nd type in the range [A;B] - the number of integers of the 3rd type in the range [A;B] which is equal to: B - A + 1 - N With N = the number of integers divisible by CORby D in the range [A;B]N will be equal to: nbr of integers divisible by C + nbr of integers divisible by D - nbr of integers divisible by C and D The first two, we can calculate, and the third term will be the nbr of integers divisible by LeastCommonMultiple(C,D).So N = F(A,B,C) + F(A,B,D) - F(A,B,lcm(C,D))Finally, the answer will be B - A + 1 - N.Here is a better submission for you to look at :)
 » 5 years ago, # |   0 sir // how to approach D & F problems ; ; can we have editorial for them;
•  » » 5 years ago, # ^ |   +1 Good day to you:Problem D: Sort the jobs by "deadline" and approach from end. For each job, let the TIME be minimum of "TIME-work" and "deadline-work". As you can see, if you end with TIME >= 0, you could do the jobProblem F: Observe that if two points have two same X (or vice versa Y) coordinate, then for each point with same Y coordinate as one of them, there will be a new point (well so basically statement ;-) ). So we would like to "group" all points with same X coordinate and with same Y coordinate (which could be done by — for example — two DSU's). Now we only need to check, the number of points in each union of partition: This mean for every partition of one coordinate, check all partitions of second coordinate, and multiply the cardinalities (obviously in the end we subtract the number of points on input ;-) )Good Luck & Wish you a nice day!
 » 5 years ago, # |   +3 When will the testset be added ?