chokudai's blog

AtCoder Beginner Contest 181 Announcement
By chokudai, 4 years ago, In English

We will hold AtCoder Beginner Contest 181.

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

We are looking forward to your participation!

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

Comments Comments (57)
| Write comment?
»
4 years ago, # |
  Vote: I like it +32 Vote: I do not like it

It collides with CF round. Can it be rescheduled?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    Yeah. Even if it started right after CF, I think there would be a lot more participants than the current time.

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

This is the first time i have seen two contests collide with each other...for this the both rounds may lose many of their participants....will be highly glad if the setter reschedule the round...

→ Reply
»
4 years ago, # |
  Vote: I like it +7 Vote: I do not like it

please，reschedule the round.

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

    There is no way to adjust the time apparently

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Sorry I can’t use Twitter,can you tell me what is it?

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

        Translated:

        I'm aware of Codeforces and ABC cover, and I think it's inevitable if I put both Saturday and Sunday, so I'll keep going. (Because there is no way to adjust this time)

        → Reply
»
4 years ago, # |
← Rev. 8   Vote: I like it +8 Vote: I do not like it

I believe problem F resembles an OI(maybe APIO) problem some years ago (but I can't find it)

Update: Instead of asking the maximum possible $$$R$$$, you are given $$$R$$$ and asked for the minimum number of points needed to be taken out so that the circle with radius $$$R$$$ can pass through. The constraints are similar ($$$N \leq 100$$$).

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 3   Vote: I like it +11 Vote: I do not like it

    A friend of mine got problem F as an interview question before. I think it was for Waymo's motion planning team? I also can't find it.

    EDIT: I think it was this one https://www.careercup.com/question?id=6266160824188928. Here the obstacles are balls and the circle is a point instead, but it is still essentially the same problem. Just need to check if the top and bottom are connected which will block all paths. (In the atcoder version you also need to binary search for the radius).

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

    AquaBlaze how to solve the question you mentioned or do you have link to the question?

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

      I think that version can be solved as follows : Draw n circles of radius R with centers as the n points and if any 2 of them intersect add an edge between them. Now for each component find the miny and maxy, and if miny — 2*R <= -100 or maxy + 2*R >= 100, then there is a blockade (I am assuming limits of (-100,100) similar to the question).

      Update : Answer is equal to sum of the minimum number of nodes that you have to remove for each blockade to be removed. This is equivalent to removing min number of vertices to disconnect graph which can be solved by max-flow, min-cut.

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

        sorry, I am not sure but did you mean that the answer is necessarily less than number of components ? i.e. for a connected component how will you determine the number of points to remove ? Could you explain for this ex: R = 100.

        points -> (0,0), (0,1)

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

          Yeah you were right. My solution had a mistake. Updated it now.

          → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 3   Vote: I like it +8 Vote: I do not like it

      The idea of modeling the given points into a graph is the same as in the problem F;

      • create $$$N$$$ nodes for each point and another 2 nodes for top line and bottom line
      • add an edge for any pair that has distance between their points less than $$$R$$$
      • add an edge between top line and any points that distance between that point and the top line is less than $$$R$$$
      • do similary with the bottom line.

      As we learn from problem F, if there is a path from the top line's node to the bottom line's node, then the circle can't pass through.

      So, what we want to do is remove nodes so that the top line's node and bottom line's node become disconnected.

      Finding the minimum number of nodes to be remove so that a pair of nodes become disconnected is minimum vertex-cut problem, which can be solved in $$$\mathcal{O}(N^3)$$$.

      → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to do F , and also in E i think i got logic but got heavily confused while implementing it .

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    In E: Sort h. for every element in W binary search where this element can be inserted in h. Now using the prefix, suffix arrays method find the minimum. Here is my submission,

    Complexity: O(nlogn)

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

      Thanks for the method. Can you suggest me how you get the idea of prefix and suffix here. Actually I thought that we have to update the whole range after the position of W.

      Can you also tell how you got this intuition and if you have solve this type of problem before can you please provide some resource .It would be great help .Thanks

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

        Just an observation of how the answer changes when w[i] is inserted in h array. It will come through practice. Do lot of questions.

        → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please explain the solution for the problem C?

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

    Run a triple loop and check the slopes by taking two points at a time out of the three i.e. (y2-y1)/(x2-x1) == (y3-y1)/(x3-x1). Note that you can cross multiply the equation to avoid divisibility by 0.

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

    If we consider two points at a time, they will always be collinear. For three points to be collinear, the slope/gradient of the line formed the by the first two points should be equal to the slope/gradient of the line formed by the last two points.

    The formula to calculate slope is (y2 - y1) / (x2 - x1). So I simple need to find these triplets and check if

    ((y2 - y1) / (x2 - x1)) == ((y3 - y2) / (x3 - x2)).

    The constraints allowed a O(n^3) solution which is the complexity to run three for loops to find the triplets. The only thing left to handle will be the division by 0.

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve E?

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    Sort h, find corresponding location of w[i] and then use prefix suffix sums accordingly.My Submission link : https://atcoder.jp/contests/abc181/submissions/17821951 O(nlogn)

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

      Why i do it in the contest but fail in one input.https://atcoder.jp/contests/abc181/submissions/17820310 Can you please help me? I have stuck in it too long...

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

        I think you are calculating the position wrong

        testcase : n=7 m=7 array h => 31 60 84 23 16 13 32 array w => 96 80 73 76 87 31 32

        position results of your code : pos — w[i] => 4 — 31 5 — 32 6 — 73 6 — 76 6 — 80 6 — 87 6 — 96

        It gives the same position for 73 and 96 which is certainly incorrect acc. to test case

        I have modified your pos function and it got accepted. Submission Link: https://atcoder.jp/contests/abc181/submissions/17888407

        Hope it helps :)

        → Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    First think how you will pair students if there was no teacher. One student will remain unpaired.

    My idea was: You can iterate till a student 'i'. And create a dp which has the quantity which we want to minimized considering if some student till 'i' has been paired with a teacher or not.

    dp[i][0] -> minimum pair height difference where none of the students till i have been paired with a teacher.

    dp[i][1]-> minimum pair height difference where one of the students till i has been paired with a teacher.

    You can try figuring out the state transitions.
    my submission: https://atcoder.jp/contests/abc181/submissions/17820721
    Edit: for pairing a student of height h[ i ] with a teacher, efficiently find out the closest w[ j ] to it.

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

    see my comment.

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve F?

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve D ?

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

    We know that a number is divisible by 8 if the last three digits of the number is divisible by 8. Now if the length of the string is less than 3 then you can directly check and see else you count the occurrences of each number in the string and generate all the 3 digit numbers divisible by 8 and then count the occurrences of each digit in that number and just check if the previous cnt is greater than or equal to this cnt for all the digits in the 3 digit number divisible by 8.

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

      I did just that but it didn't worked, am i missing something here ?

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

        length of string is 2*10^5 but you have used long long for input.

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

          thank you very much, i thought that s is a number <= 2*10^5, such a stupid mistake, waste my 8 submissions D:

          → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone point out the flaw in my code to problem D. It is showing WA in only one input D-Hachi

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    It will fail in tests when the length of the number = 2.(ex:61,42,23...),Because you check only the given permutation but not the reversed one.

    → Reply
»
4 years ago, # |
← Rev. 4   Vote: I like it +6 Vote: I do not like it

Ideas for Problem F: 1.) Binary search can be used. 2.) To test a particular value of radius, we can make circle of that length taking nail coordinates as centers. 3.) Make a graph, with nodes as nails coordinates and edge if the two circles centered at nails coordinate overlap. 4.) Check if there exist a path of nodes that completely blocks the passage using bfs/dfs. 5.) If no such blockage exist, then test is successful otherwise failed.

Code

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

next_premutation in problem D-Hachi gave me TLE .Somebody please explain why? Thanks.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    It will obviously give TLE.Do you realise you are trying to do $$$10^5!$$$ permutations.

    → Reply
»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Solution for F: First we need to understand that binary search over radius works in this problem because as the radius increases, the area of the possible loci decreases. Now I convert the problem to the following for checking existence of loci for a particular value of radius, say r : Given N circles, each of radius r, check if there exist a valid line path that doesn't pass through any of them. To solve this problem, notice that the Y borders have changed from [-100+r, 100-r]. Another observation is that if there is no path, there is a set of circles that overlap such that minimum Y and the maximum Y covered by the set of circles is less than equal to -100 + r and more than equal to 100 — r, and by iterating on arc of any of the circles from the set, we should be able to reach the arc of any other circle. This can easily be found by union find algo. and maintaining minY and maxY for each connected component of circles, and in the end checking if it is possible for the given r.

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

In problem F, you don't have to do binary search. This is because the maximum possible radius of a circle is definitely equal to the one of the lengths between two points or a point and the line. So you just need to sort by length and check in the ascending order. Of course, you need DSU to see if it is possible for a circle to get through.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can we solve problem C in better complexity than $$$n^3$$$?

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

please help why this code is giving WA https://atcoder.jp/contests/abc181/submissions/17866014

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

    to_string(i); does not create the leading zeros.

    In example if the number ends in "...008", then it is divisable by 8, but you need two zeros. Your code does not check this correct.

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

      Each character of $$$S$$$ is one of the digits from $$$1$$$ through $$$9$$$.

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

        Yes, S does not contain zeros, but numbers divisable by 8 do. Consider the loop where to_string(i) return "8". The code checks if S contains a single '8', which is not sufficient.

        → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Test cases for Problem D is weak. Here is a submission which passed all test cases, but it fail on this test case $$$61$$$, the answer should be Yes but the above submission prints No

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What is the right hand rule mentioned in the editorial for F?

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve F in N2

→ Reply