snuke's blog

By snuke, history, 5 years ago, In English

AtCoder Beginner Contest 131 is on this Saturday.

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

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

| Write comment?
»
5 years ago, # |
  Vote: I like it +2 Vote: I do not like it

How to solve last problem ? I have some ideas ,but i had a little time to think on them.

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

    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, # |
  Vote: I like it -8 Vote: I do not like it

DSU

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

How to solve F?

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

    DSU

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

      Please explain more.

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

          how to solve e? pls also explain that.

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

            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, # ^ |
                Vote: I like it 0 Vote: I do not like it

              thank you for you explaination :) it helped me a lot

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

can anyone tell me the approach for problem e.

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

    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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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-n

    As 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 -1

    else if k==mx we will print the above edges

    else if k<mx we will reduce the road of distance 2 by make the edge from 2 to 3 (in order to eliminate road 2-1-3) and 2 to 4 and 2 to ... until the remain roads of distance 2 equal k.

    #include <bits/stdc++.h>
    
    using namespace std;
    typedef pair<int,int> ii;
    vector<ii> 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<n;i++)
                for (int j=i+1;j<=n;j++)
                {
                    if (d==0)
                    {
                        cout << ans.size() << "\n";
                        for (ii v:ans) cout << v.first << " " << v.second << "\n";
                        return 0;
                    }
                    ans.push_back(ii(i,j));
                    d--;
                }
            cout << ans.size() << "\n";
            for (ii v:ans) cout << v.first << " " << v.second << "\n";
            return 0;
        }
    }
    
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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   Vote: I like it +1 Vote: I do not like it

          thanks i understood it. i set the upper bound to n-2 for the graph like 1 -- 2 -- 3 — .. -- n

          and then start adding edges. it gave wa for almost half of test cases.

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

            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   Vote: I like it +18 Vote: I do not like it

    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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # |
  Vote: I like it +13 Vote: I do not like it

The last problem reminded me this problem: 1012B

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

lots of RE in 3rd problem in python 3.4 my code seems right.

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

    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   Vote: I like it +8 Vote: I do not like it

Weak tests on F.

I got AC with an $$$O(N^2)$$$ solution.

https://atcoder.jp/contests/abc131/submissions/6073267

My code is quadratic in a case where all points have the same y-coordinate.

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

when we get editorial?

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

    They have a solution in brainf**k for problem A lmao

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

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, # |
  Vote: I like it +8 Vote: I do not like it

Can someone "explain" how to solve F?

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

    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, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone tell me what's wrong with this submission, it's failing one test?

Submission for Problem C

Thanks in advance!

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

    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, # |
  Vote: I like it +1 Vote: I do not like it

What does evenly divided by C and D signify in problem C?

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

    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, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Thank you so much. I was thinking that X%Y == 0 && X/Y should be even.

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

How to solve Problem F using DSU?

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

how to solve porblem F?

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

The time of english page in AtCoder is still broken. pls fix it.

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

How to solve C? I tried different approaches but was constantly getting WA.

  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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, # ^ |
        Vote: I like it 0 Vote: I do not like it

      hi can you explain how you find divisible count ? and why your solution is working ?

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

        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/X

        Why is it working

        I'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, # |
  Vote: I like it 0 Vote: I do not like it

sir // how to approach D & F problems ; ; can we have editorial for them;

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

    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 job

    Problem 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, # |
  Vote: I like it +3 Vote: I do not like it

When will the testset be added ?