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$$$).
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)$$$.
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.
Can someone please explain the solution for the problem C?
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.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 :)
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.
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 ?
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.
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
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.
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
can we solve problem C in better complexity than $$$n^3$$$?
deleted
deleted
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.
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
What is the right hand rule mentioned in the editorial for F?
how to solve F in N2