chokudai's blog

AtCoder Beginner Contest 181 Announcement
By chokudai, 4 weeks 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 (94)
»
4 weeks ago, # |
  Vote: I like it +32 Vote: I do not like it

It collides with CF round. Can it be rescheduled?

→ Reply
  • »
    »
    4 weeks 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 weeks 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 weeks ago, # |
  Vote: I like it +7 Vote: I do not like it

please，reschedule the round.

→ Reply
»
4 weeks 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 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What about E ?

    → Reply
  • »
    »
    4 weeks 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
  • »
    »
    3 weeks 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
    • »
      »
      »
      3 weeks 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
      • »
        »
        »
        »
        3 weeks 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
        • »
          »
          »
          »
          »
          3 weeks 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
    • »
      »
      »
      3 weeks 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 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

What's wrong with 1 test case of problem C? Can anyone help, Here's my Submission

→ Reply
»
4 weeks 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 weeks 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 weeks 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 weeks 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 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

What was wrong with C I have done using area if area ==0 then colinear and yes .but it doesn't work.

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

    I did the same thing and my code accepted! My submission

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

    I think you are not considering all the possible combinations. Becoz I was also doing same mistake but then corrected and it got accepted

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

      It was silly mistake. Doing contest after long time so it took time to find it.

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

    this question related to geometry ?

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

Can someone please explain the solution for the problem C?

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

    Brute force 3 for loops and then check if area == 0 then it will be colinear. For area of triangle using 3 points Google the formula.

    → Reply
  • »
    »
    4 weeks 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 weeks 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 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can check if some points lie in a same line by two ways (I know only two :p ) :

    1) all the points on the same line will have same slope. Why it is so ? You can google it or better think of it. So you can take 3 points each time and can check between the twos if they have same slope

    2) You can use some kinds if determinant formula. Think of the 3 points as 3 points of a triangle. If you can find the area of that triangle then it is obvious that they are not in the same line. But if all of them lie in same line then is it possible to find any area of triangle? Think it like this...

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

How to solve E?

→ Reply
  • »
    »
    4 weeks 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 weeks 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
      • »
        »
        »
        »
        3 weeks 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
        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Thanks a lot for spending time checking for my submissions!I have known why it didn't work.Actually it blame on my special check when case is (l==r-1). I have read yours and change it to the right one.

          → Reply
  • »
    »
    4 weeks 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 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks!! I had like a binary search idea for this problem but could not implement it.

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

      I had the similar idea but could not implement.Can you help me understand how are you doing the transitions. Thanks!

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

        Consider you have the constructed the dp[][] array till i-1th student.
        now for the ith student, you need to solve for dp[i][0] and dp[i][1].

        If i is 0 based
        / Lets solve for none of the students getting paired with a teacher, first i.e dp[i][0]:
        You can see that if i is odd you can pair it with previous student.
        dp[i][0] = dp[i-2][0] + h[i]-h[i-1]

        If i is even:
        It will remain unpaired for now. Because state dp[i][0] has odd number of elements.

        Now consider the state dp[i][1]:
        If i is even:
        there are two possibilities:
        1. student i is paired with a teacher.
        2. student j is paired with a teacher, in which case student i can be paired with i-1. Note 0<= j <= i-2

        So we get
        dp[i][1] = min(dp[i-1][0] + cost of pairing ``i`` with teacher, dp[i-2][1] + h[i]-h[i-1])

        if i is odd:
        you cannot pair with a teacher because there are already an even number of students in the dp[i][1] state. So some one will remain unpaired.

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

    see my comment.

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

How to solve F?

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

How to solve D ?

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

    A number is always divisible by 8 , if its last three digit is divisible 8 . I made three cases for n==1 ,n==2 ,n>=3 . Where n is length of string .

    For n>=3 , i iterated all 3 digit multiple of 8 , and checked if it can be formed from given string, using frequency count array for them. Also a special case 000 ,that is if f[0]>=3 ,it is always possible.

    → Reply
  • »
    »
    4 weeks 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 weeks 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 weeks 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 weeks 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 weeks 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 weeks 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 weeks 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 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

https://atcoder.jp/contests/abc181/tasks/abc181_e Can someone please help me why i lost 1 testcase.lol.I manage to do this by using binarysearch and prefix.

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

    It seem that it was just a small testcase

    → Reply
»
4 weeks 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 weeks 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 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In E: My code passed the cases for small and medium but for large and max cases its showing tle. Can anyone tell how to optimize my code. Here is the code.

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

How to solve F ?

→ Reply
»
4 weeks 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 weeks 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 weeks 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 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    For every point with another point we calculate a slope. If there is 2 or more same slopes for this point we found points that lie in same line.

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

    here is a code. complexity n*n*logn

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

      or maybe we can use unordered_set as dx and dy are quite small $$$10^3$$$. simple hashing for pair will work.

      struct pair_hash {
  inline std::size_t operator()(const std::pair<int, int>& v) const {
    return v.first * 1000 + v.second;
  }
};

      https://atcoder.jp/contests/abc181/submissions/17867299

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

      WHY (LOGN) IS ALSO THERE ? WHETHER IT SHOULD BE NOT JUST N^2 ?U DO NOT NEED TO FIND GCD EVEN? JUST STORE dx/dy ...

      JUST FIND SLOPES FOR ALL POINTS AND PUT IT IN THE UNORDER MAP AND SEE IF ANY OF THE KEYS HAVE FREQ >=2 THEN ANS IS YES ELSE ANS IS NO

      → Reply
»
4 weeks 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 weeks 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 weeks 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 weeks 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 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Please post the editorial.

→ Reply
»
3 weeks 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
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Plz can anyone debug my code in problem E. Where is problem ? Submission Link: https://atcoder.jp/contests/abc181/submissions/17896013

→ Reply
»
3 weeks 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
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

pragma GCC optimize "trapv"

pragma GCC optimize("O3")

include <bits/stdc++.h>

define sq(a) a*a

const double pi = 2 * acos(0.0) ; using namespace std ; using ll = long long ;

define x1 vc[i][0]

define y1 vc[i][1]

define x2 vc[i+1][0]

define y2 vc[i+1][1]

define x3 vc[i+2][0]

define y3 vc[i+2][1]

template<typename... T> void read(T&... args){ ((cin >> args),...) ; }

int main(){

ifdef LOCAL

freopen("in2","r",stdin) ;

endif

ios::sync_with_stdio(0) ; 
cin.tie(nullptr) ;
int n ; read(n) ; 
vector<vector<int>> vc(n, vector<int> (2)) ; 
for(int i = 0 ; i < n ; ++i)
  read(vc[i][0],vc[i][1]) ; 
int p = 0 ; 
for(int i = 0 ; i <= n-3 ; ++i){
  if(y2*x3  - y3*x2 + y1*x2 - y2*x1 + y3*x1 - y1*x3 == 0){
    p = 1 ; 
    break ; 
  }
}
cout << (p?"Yes\n":"No\n") ;
return 0 ;

}

This was my submission to problem C, but I got a WA can anybody tell me why?

→ Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I tried to use next_permutation to solve problem D but failed in a couple of tests can anyone tell me the reason? thanks a lot

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

    Just a couple to test cases ?
    For example if s = 1122334455. The possible permutations all the way from 1122334455 to 5544332211 is 113400.
    As you can see this becomes very big very quickly. I think this increases as a function O(len(s)!). This approach fails for : s = 1111122222333334444455555.

    Code : https://atcoder.jp/contests/abc181/submissions/18018629

    → Reply