We will hold AtCoder Beginner Contest 181.
- Contest URL: https://atcoder.jp/contests/abc181
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20201101T2100&p1=248
- Duration: TBD (around 2 hours)
- Number of Tasks: 6
- Writer: evima, tatyam, tempura0224, tozangezan, YoshikaMiyafuji
- Rated range: ~ 1999
The point values will be 100-200-300-400-500-600.
We are looking forward to your participation!
It collides with CF round. Can it be rescheduled?
Yeah. Even if it started right after CF, I think there would be a lot more participants than the current time.
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...
please,reschedule the round.
There is no way to adjust the time apparently
Sorry I can’t use Twitter,can you tell me what is 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)
Thank you very much
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$$$).
What about E ?
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).
AquaBlaze how to solve the question you mentioned or do you have link to the question?
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.
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)
Yeah you were right. My solution had a mistake. Updated it now.
The idea of modeling the given points into a graph is the same as in the problem F;
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)$$$.
What's wrong with 1 test case of problem C? Can anyone help, Here's my Submission
How to do F , and also in E i think i got logic but got heavily confused while implementing 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)
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
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.
What was wrong with C I have done using area if area ==0 then colinear and yes .but it doesn't work.
I did the same thing and my code accepted! My submission
Damn, I had the same idea but it had complexity O(n^3) so I thought I'd get a TLE, so I spent a lot of time trying to find a better solution. Ended up not submitting sadly, I feel bad.
Ohh! Because n <= 100, O(n^3) wouldn't get TLE.
Yeah, should've submitted :/
my O(n^2) solution.
I think you are not considering all the possible combinations. Becoz I was also doing same mistake but then corrected and it got accepted
It was silly mistake. Doing contest after long time so it took time to find it.
this question related to geometry ?
Can someone please explain the solution for the problem C?
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.
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.
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.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...
How to solve E?
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)
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...
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 :)
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.
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.
Thanks!! I had like a binary search idea for this problem but could not implement it.
I had the similar idea but could not implement.Can you help me understand how are you doing the transitions. Thanks!
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]
anddp[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 studenti
can be paired withi-1
. Note0<= 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.Thanks a lot s3ct4l-r3x
see my comment.
How to solve F?
You can solve it using binary search and DSU.
Binary search for a radius r, such that it is not blocked.
A circle of radius r is blocked if you can form a set of connections between the two boundaries parallel to x-axis by connecting the nails if the distance of each connection(between two nails or a nail and a boundary) is less than r.
This can be checked using DSU.
Can you share your submission?
Not mine but the cleanest I found : https://atcoder.jp/contests/abc181/submissions/17798965
DSU means?
Disjoint Set Union
How to solve D ?
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.
can you tell me what am I doing wrong in my code! Or which type of case I missed in my code. my code
Your code will fail for test which have repeated digits e.g; "888"
I store the loop index i value in n [line 80] and then separate the digit for checking. now your given test case ar giving "Yes" output but it still gives wa. I add a new statement in line 84. My New Code
can u please tell , where I am wrong in this code https://atcoder.jp/contests/abc181/submissions/17854300
can anyone help me with D, why my code fails for 6 test cases :(
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.
I did just that but it didn't worked, am i missing something here ?
length of string is 2*10^5 but you have used long long for input.
thank you very much, i thought that s is a number <= 2*10^5, such a stupid mistake, waste my 8 submissions D:
Can someone point out the flaw in my code to problem D. It is showing WA in only one input D-Hachi
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.
Oh, thanks mate.
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
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.
It seem that it was just a small testcase
next_premutation in problem D-Hachi gave me TLE .Somebody please explain why? Thanks.
It will obviously give TLE.Do you realise you are trying to do $$$10^5!$$$ permutations.
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.
How to solve F ?
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.
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.
Unofficial Editorial
This is the best solution to F. Thanks.
can we solve problem C in better complexity than $$$n^3$$$?
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.
here is a code. complexity n*n*logn
or maybe we can use
unordered_set
asdx
anddy
are quite small $$$10^3$$$. simple hashing for pair will work.https://atcoder.jp/contests/abc181/submissions/17867299
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
please help why this code is giving WA https://atcoder.jp/contests/abc181/submissions/17866014
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.
Each character of $$$S$$$ is one of the digits from $$$1$$$ through $$$9$$$.
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.
Please post the editorial.
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
yes you are absolutely right.i checked this now
Plz can anyone debug my code in problem E. Where is problem ? Submission Link: https://atcoder.jp/contests/abc181/submissions/17896013
What is the right hand rule mentioned in the editorial for F?
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
endif
}
This was my submission to problem C, but I got a WA can anybody tell me why?
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
Just a couple to test cases ?
For example if s = 1122334455. The possible permutations all the way from
1122334455
to5544332211
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
I see. brute force takes too much time.