### chokudai's blog

By chokudai, history, 7 months ago, ,

We will hold AtCoder Beginner Contest 139.

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

We are looking forward to your participation!

• +63

 » 7 months ago, # |   -91 Why such worse time? There's going to be a football match here in Nanjing, China but because of this contest I can't watch it.
•  » » 7 months ago, # ^ |   +79 No one gives a fuck about Chinese football matches.
•  » » 7 months ago, # ^ |   +27 Seems that you're not very experienced in football, Chinese football matches aren't worth watching...
•  » » » 7 months ago, # ^ |   +3 i don't think so, It's just that it's not as fascinating as it is in Europe
•  » » 7 months ago, # ^ |   -36 I can understand your pain, guy. Chinese football matches are much better than foreign ones, and taking part in such a shitty contest is totally a shame! So all those who says "Chinese football matches aren't worth watching" please go away, far away!!!!!!!!
•  » » 7 months ago, # ^ | ← Rev. 3 →   0 LOL XD look at the down votes You can always watch the football match later after the game gets over
 » 7 months ago, # |   +24 Website is very slow today
•  » » 7 months ago, # ^ |   0 It took me around 40 seconds to read and code problem A but only because the website was slow, I was able to submit at 3:47. So sad :(
 » 7 months ago, # |   -14 B — Power Socket statement not clear
 » 7 months ago, # |   +40 Congratulations to everyone who was able to understand the problem statement of 'B' . First study English, then write problems, I request! Lesson learnt:- Never give an AtCoder Beginner Contest,because mortals like me still can't understand what was asked .
•  » » 7 months ago, # ^ |   0 Indeed :))
•  » » 7 months ago, # ^ |   0 It is just we need to find the minimum number of power strips is needed, A is the number of sockets in each of them. By logic, the next power circuit is connected with the previous one, to get power.
 » 7 months ago, # |   -41 What a fuck thing! Problem F has a same problem in BZOJ......
•  » » 7 months ago, # ^ |   +26 I think to publish it after the contest would be better.
•  » » 7 months ago, # ^ | ← Rev. 2 →   +36 As a writer of this contest, please refrain to write some hints about the problem during the contest. The fact like "this problem can be solved with DP" or "this contest is already published 3 years ago" should be written after the contest. It might cause BAN or some bad thing.
 » 7 months ago, # |   +50
•  » » 7 months ago, # ^ | ← Rev. 2 →   0 Could you please explain a solution?
•  » » 7 months ago, # ^ |   +26
•  » » » 7 months ago, # ^ |   0 How to solve the last subtask (n can be 200,000) ?
•  » » » » 7 months ago, # ^ | ← Rev. 2 →   0 Check out Geothermal's blog here: https://codeforces.com/blog/entry/69500 (the second solution).You can use two-pointers to speed it up from $\mathcal{O}(n^2)$ to $\mathcal{O}(n)$.
 » 7 months ago, # |   0 Can anyone please help in finding the error in my code on Problem E? I was getting TLE on last case. I used binary search. https://ideone.com/hiB9kPPlease Help!
 » 7 months ago, # |   +46 As usual, I've posted my solutions, which you can now find at this link.
 » 7 months ago, # | ← Rev. 4 →   0 How to solve F?I Tried all possible combination of coordinates... At an index either select it or don't. similar to knapsack dp
•  » » 7 months ago, # ^ |   0 HintMinkowski sum
•  » » » 6 months ago, # ^ |   0 Can you explain your method with more details?
 » 7 months ago, # |   +1 Does AtCoder run properly on mozilla?Website and questions were not loading in mozilla.
•  » » 7 months ago, # ^ |   +10 Maybe a connection or cache issue, I had no problem with atcoder and mozilla rather than at the begin of the contest.
 » 7 months ago, # |   0 That's a very bad thing, to have problems " copy-paste " from other judges, it makes the round a test for googling skills
•  » » 7 months ago, # ^ | ← Rev. 2 →   +43 Not really, nowadays it's almost impossible to know all the problems from all platforms. In Poland, we're spending some time trying to find similar problems using Google. If we cannot find anything, then the task is fine.
 » 7 months ago, # |   0 How to solve F
 » 7 months ago, # | ← Rev. 5 →   +25 Unofficial editorial by me. All solutions here I verified got AC by the judge. A. (Tenki) ExplanationJust compare. A. Codedef solve(S,T): return sum(s==t for s,t in zip(S,T)) B. (Power Socket) ExplanationSimulate adding power sockets. B. Codedef solve(A, B): available = 1 ans = 0 while available < B: available += A-1 ans += 1 return ans C. (Lower) ExplanationLet dp[i] be the most hops you could have taken to reach this square. (We can also do this in constant space, but it is not necessary.) C. Codedef solve(N, A): dp = [0] * N for i in xrange(1, N): if A[i] <= A[i-1]: dp[i] = 1 + dp[i-1] return max(dp) D. (ModSum) ExplanationThe largest possible sum is clearly 0 + 1 + 2 + ... + N-1 as it maximizes each addend. But this is achievable by N, 1, 2, ..., N-1. D. Codedef solve(N): return N * (N-1) / 2 E. (League) ExplanationSimulate each round. We'll maintain now, the set of all people that might be paired. Whenever we pair some people in a round, we have to add them to later, which considers that they might be paired next round. E. Codedef solve(N, A): # A as deques of values in [0, N) now = range(N) todo = N * (N - 1) for ans in range(1, N * N): later = set() for i in now: # If this person has a future opponent and is unpaired: if A[i] and i not in later: j = A[i][0] # If that opponent j is unpaired and has a future opponent # and that opponent is i: if j not in later and A[j] and A[j][0] == i: later.add(A[i].popleft()) later.add(A[j].popleft()) todo -= 2 if not todo: return ans now = later return -1 F. (Engines) ExplanationSay the origin is O, and the final destination point is P. Only vectors with a projection that is positive onto OP should be added. These vectors are vectors in the halfplane marked by the line orthogonal to OP. Thus, we should only consider vectors belonging to the same halfplane.Sort the vectors by angle. We can directly compute the sum of vectors by prefix sums. One of these prefix sums will belong to the correct half plane. F. Codefrom math import atan2 def solve(N, A): A.sort(key = lambda (x, y): atan2(y, x)) P = [0] for x, y in A+A: P.append(P[-1] + (x + y * 1j)) ans = 0 for i in xrange(N): for j in xrange(i, i+N): ans = max(ans, abs(P[j+1] - P[i])) return ans
•  » » 7 months ago, # ^ |   0 here is my code for D #includeusing namespace std;int main() { int n; cin>>n; int a[n]; int x; if(n%2!=0){ x=n*(n-1)/2;} else x=(n/2)*(n-1); cout<
•  » » » 7 months ago, # ^ |   0 As x is of int data type, it would hold a max value of INT_MAX ( about 2*10^9) . Hence for bigger values of n, overflow would lead to WA.
•  » » 7 months ago, # ^ |   0 Thank you for your nice editorials and solution. Please continue this or someone should do this.
•  » » 7 months ago, # ^ |   0 For C, another approach is to let dp[i] be the number of moves you can achieve if you start from i.
 » 7 months ago, # |   +1 imo C and D are swapped :d
 » 7 months ago, # |   +14 I use randomize + greedy + soting and PASSED F!This is my codeBut I don't know how to solve it properly . I think I'm a little lucky
•  » » 7 months ago, # ^ |   0 I'm not so lucky like you. QWQI also used randomize + greedy, and I got WA.
•  » » 7 months ago, # ^ |   +15 Just maybe your sorting function is so good. I actually generated testcase which naive hill climbing algorithm may fail. I think it's the case of chenxiaoyan. However, I expected that simulated annealing algorithm may pass. Within this constraints, I don't think that there exists a killer case for SA algorithm. SA is so powerful that even solves a problem in AGC.
 » 7 months ago, # | ← Rev. 2 →   +29 I am really sorry that problem F was already published to some other contests. I published this because I thought to be both original and high-quality. While I was already solving 4,000+ problems in competitive programming, there were no instance of this problem, including similar problems. I attempted many times to search "maximum distance vector subset sum"-like keywords in google, but didn't find the same question. P.S. We created pretty tricky testcase for problem F, so only 1/10 of solutions passed, while we prepared extraordinary 7 sample testcases :)
 » 7 months ago, # | ← Rev. 2 →   0 My solution for the problem B :- http://ideone.com/yAZ9WRit gives WA for only ONE test case 09 and AC for the rest,can anyone help me find out a case for which my code doesn't work
•  » » 7 months ago, # ^ |   0 when b=1 ans should be 0
•  » » » 7 months ago, # ^ |   0 it gives 0 whenever B is 1
•  » » » » 7 months ago, # ^ |   0 then check for a=2 and let b=5
•  » » » » 7 months ago, # ^ |   0 check for a=2
 » 7 months ago, # |   +3 In problem E, after checking for cycle in the directed graph formed between the matches, I found the length of the longest directed chain in the graph.I got WA with this approach.Can anybody help me where I am wrong please?
•  » » 7 months ago, # ^ |   +4 Nevermind, It worked, messed up the cycle check back then :( Check out my solution if anyone wants : https://atcoder.jp/contests/abc139/submissions/7293559
•  » » » 7 months ago, # ^ |   0 I solved it with the same idea but get WA https://paste.ofcode.org/349znw527FjtNqWSTAeDdiM could you tell me why please
•  » » 7 months ago, # ^ |   +1 Can you please explain the logic behind your approach, thank in you advance
•  » » » 7 months ago, # ^ |   0 First after we make the directed graph, and check the absence of cycles in it, to find minimum days, you must understand that the graph will be overlaps of some directed chains, and if you take the length of largest such chain, there's no other chain larger than it, and hence in those many days the rest of the chains can be allocated a day easily because at any point of intersection the topologically higher part will be contributing iff it is the longest subchain compared to the other chains and hence day assignment won't be a problem. Although I believe such is the solution, I cannot completely confirm it for any edgy test cases.
•  » » » » 7 months ago, # ^ |   0 rohit_goyal, Thank you for your explanation ... I got some questions. How are you storing the graph (as adj lists or matrix) ? Can you send some links (tutorials, editorials and questions related to this problem) ?
•  » » » » » 7 months ago, # ^ |   0 I am storing the graph as adjacency list (instead of using pair as an element in list, I use compressed index for denoting pair (l, r) ). The only tutorial I can provide you is about how to check for cycle in graph : Link But if you want to check out another approach or more detailed solutions, check out this link below: Link
 » 7 months ago, # |   0 Can anyone give a tutorial for problem E??
 » 7 months ago, # |   +3 Please elaborate the problem B, what exactly we need to do in this and how to do:)
•  » » 7 months ago, # ^ |   0 From what I could comprehend, after you apply a socket wire ( or whatever it was called, having parameter A), the old socket is converted to a multi — socket of size A. So how many minimum we need to apply to at least get B sockets? You can refer the image for A = 3 and transitions: Link : https://ibb.co/bXcss0W See the numbererd nodes?They are our sockets after adding each wire at each step of size A.
•  » » » 7 months ago, # ^ |   0 now i understand clearly
•  » » 7 months ago, # ^ |   0 Initially, you have only 1 plug which is open. You want "B" open plugs. You have only "A" sized boards (which means each board has A open plugs.) Target is to find the minimum number of "A" sized boards required to get "B" open plugs.The key idea is Whenever you use a brand new board, you will have to use an empty plug from previous to connect this.So essentially whenever you add a board you add "A-1" open plugs and not "A". Just simulate this by adding boards until you reach B or more.
 » 7 months ago, # |   +16 My approach for F:Keep track of the convex region we can reach. This can be described as a set of points. For each incoming vector, apply it to every point on the boundary, and keep only the convex hull of the resulting set of points.I was concerned this would TLE if the hull got too big, but surprisingly this passed in 2ms. Are there any countertests for such an approach when n = 100? The POI version where n=200,000 seems like it would break this.
•  » » 7 months ago, # ^ |   +5 Useful conclusion: a convex hull on integral points with $x$ and $y$ coordinates both in range $[1,A]$ contains at most $O(\sqrt{A})$ points. In this problem, the maximum absolute value you can reach is $N \cdot maxX \leq 10^8$, so at most $O(\sqrt{N \cdot maxX}) \leq 10^4$ points.Thus, even if you brute-force the convex hull after each vector, the total complexity will be $O(NP \log P)$(Let the size of the hull be $P$), which can fit the time limit.Of course this won't work for $N=200,000$. In fact, we can scan the vectors with a half plane. Update the answer when their is a vector go into/out of the half plane. The total complexity is $O(N \log N)$(imo). Maybe you can share your convex hull code here, because I didn't implement it :D
•  » » » 7 months ago, # ^ |   +10 I think the convex hull on integral points with $x$ and $y$ coordinates both in range $[1, A]$ contains at most $O(A^{2/3})$ points, not $O(\sqrt{A})$ points. That's because there are $O(n^{2/3})$ pair of $(x, y)$ which is $1 \leq x, y \leq O(n^{1/3})$ and $gcd(x, y) = 1$.
•  » » » » 7 months ago, # ^ |   0 Can you link some proof regarding this claim, I am not able to find on google..
•  » » » 7 months ago, # ^ |   0 That is a very useful conclusion! While the result seems intuitive, is there a constructive proof?Here's my code from the contest: https://atcoder.jp/contests/abc139/submissions/7268385
•  » » » » 7 months ago, # ^ |   +5 See this comment.
•  » » 7 months ago, # ^ |   +5 Wow, grats for actually thinking of this in contest fairly quickly. I saw it and immediately thought of https://codeforces.com/contest/995/problem/C, remembering that even though there was an elegant solution, randomization + greedy heuristic solved all cases and was hard to break.Turns out same was true for this one.
 » 7 months ago, # |   0 The sample code of problem F in official editorial returns 404.
 » 7 months ago, # |   0 Can Some one please explain E: League and F:Engines solution.
•  » » 7 months ago, # ^ |   +3 Let's create a directed graph. Where each node is a match played between two players. Now let's add edges to this digraph. For an ith person's required order we add a directed each for each adjacent positions. That is for j in range (1..n-1) add directed edge from (j-1) to j. Also since match played between a&b and b&a is similar we merge these edges into one.Now we have a directed graph. We just check the topological ordering of this graph. If it's cyclic then we don't have an answer.Now to find the minimum days: For a node who has not yet finished (is still waiting on some nodes to finish), this node can only finish when the max days taking node it is still waiting for finishes and then it takes 1 more extra day to finish.Obviously, the nodes which don't wait for others to finish end on day 1. For other nodes, we update them using the previously done. And maintain maximum throughout.
•  » » » 7 months ago, # ^ |   0 What I have done is create a vector of set where each set in a vector represents the team that played on that particular day and at last output the size of vector (the number of days). How I did it? Iterate through all the existing sets of vectors, if neither of the two element(i and Aij) are present in that set, add both the elements to that set and if none of the set satifies this condition then add a new set to vector. Also, I have kept a value = temp1 which is equal to the kth vector(the vector in which last pasir of elements were added), this also helps to know if any two cases are contradicting.Can someone please help me out in finding error as I am getting WA in some test cases.Here is my solution:- https://atcoder.jp/contests/abc139/submissions/7296021
•  » » 7 months ago, # ^ |   +2 In E : first observation was to see, among all the possible matches , which would be the first match . if we say the i th player played the first match with the j th player. then in the column of i , j would be the first element and in the column of j , i would be the first element . Now since on day 1, i th and j th player has played , so they can't play more matches on day 1. so we try to find some more pairs for day 1, if they satisfy the above criteria . we can do this while traversing the first column. after finding all the pairs which played on day 1 , we can start to find pairs who played on day 2. for finding the pairs what i did was to initialize n pointers to 1. if some pair satisfy the criteria , I incremented their respective pointer by 1.when we find no pair , we break out of the loop. at the end, if all pointers are at n , which means all have played , we simply print the number of days , else we print -1 . Hope it helps. for more clarity, you can see my code : Link
•  » » » 7 months ago, # ^ |   +3 What is the time complexity of your solution? To me it looks O(n^3) in case where only one match is played in each day because your while loop will run n^2 and inner loop i O(n) or am I wrong?
•  » » » » 7 months ago, # ^ |   0 Yup ,you are absolutely correct. It is my bad that i didn't calculate the worst time complexity of my solution. On a little thought , it can be optimised by using containers like map or set where finding such a pair is relatively easy.
 » 7 months ago, # |   0 F was well-known, but I didn't know it.I hope there will be no well-known problems next round.
•  » » 7 months ago, # ^ |   0 well, an well known problem appearing in any contest doesn't destroy the fun of problem solving as long as the problem is elegant/crafty, right? if someone knows the solution beforehand they can just solve it quickly and go rewatch some rick and mortys. On the other hand, it might turn out to be a wonderful contest with cool problems :)
 » 7 months ago, # |   +3 An observation for F: we always choose a vector forming an angle with the previous vector in range (-pi/2; pi/2). Therefore, F can be solved in O(nlogn) by sorting and two pointers.
 » 7 months ago, # |   +1 how can i solve E-league with topological sort? I've figured out that if it contains cycle than answer is not possible. In all other cases we have to output maximum depth of that tree. Is it right approach? My WA solution
 » 7 months ago, # | ← Rev. 2 →   -10 in E why numbering of node for (x,y) is min(x,y)*N+max(x,y)?
•  » » 7 months ago, # ^ | ← Rev. 2 →   0 Assuming you are asking 0-indexed numbering: First of all taking minimum and maximum is to avoid distinction between pairs like (1,2) and (2,1) or you can say we need unordered pairs in the problem. Secondly the numbering is one of possible numbers you can take. This numbering is just indicating, say in a grid, you are at (1,5) and grid size is 6*6, so the assigning numbers from first cell to the required cell, starting with 0,you get number 1*6 + 5(only for 0 based indexing ), so think it like this, at (i, j) cell, you need to move n*i number of cells along rows and then the jth cell is your requirement, hence the number n*i+j.
•  » » » 7 months ago, # ^ |   0 Thank u :D
•  » » » » 7 months ago, # ^ |   0 Anytime mate!
 » 7 months ago, # | ← Rev. 2 →   0 Why English editorials are not linked on englsh website, they are available on Japanese one?
 » 7 months ago, # |   +1 Problem "D" should be swapped with problem "B" or "C".
 » 7 months ago, # |   -7 Aside from simulating, there is a one liner solution for B: Spoilerceil((b-a)/(a-1))+1Because of the following inequality: (n-1)*(A-1) + A >= B
 » 7 months ago, # |   +1 I passed F just by random_shuffle.https://atcoder.jp/contests/abc139/submissions/7278813
•  » » 7 months ago, # ^ |   +6 you guys must have some kind of magic wand!
 » 7 months ago, # |   +1 Problem E:Can someone speed up my solution?I'm using deque and finding possible matches between players, and combining if it's possible. For some reason it's TLEing in one test :- Submission
 » 7 months ago, # | ← Rev. 2 →   0 Here's my solution code for F. Notice that the solution set of vectors will consist of those vectors which are all in one half of the plane so that they all add positive components toward the final destination vector. So we need to pick contiguous vectors (sorted by angle) with the max difference of angles being 180 degrees. However, we need not worry about the 180-degree difference limit as while checking for all possibilities, the extra vectors will only reduce the answer. The answer remains unaffected. So our task is reduced to finding some set of contiguous vectors so that the final answer is maximized. This is easily done by prefix sum in O(n^2). Make sure to consider the original vectors twice, so that the conditions such as (i, i+1, ..., n, 1, 2 ) are considered while constructing the solution. We pick anywhere from 1 to n vectors to check for a possible solution. #include using namespace std; #define fastIO \ ios_base::sync_with_stdio(false); cin.tie(NULL); #define endl "\n" #define ll long long #define MOD 1000000007 #define pb push_back #define ff first #define ss second #define mp make_pair #define pii pair bool compare(const pii &a, const pii &b){ return atan2(a.ss,a.ff) < atan2(b.ss,b.ff); } long double dis(pair a, pair b){ long double x = abs(a.ff-b.ff), y = abs(a.ss-b.ss); return (x*x + y*y); } int main(){ int n; cin >> n; vector v(n); for(int i=0;i> v[i].ff >> v[i].ss; sort(v.begin(), v.end(), compare); vector < pair > prefix(2*n); prefix[0] = v[0]; for(int i=1;i<2*n;i++) prefix[i] = mp(prefix[i-1].ff + v[i%n].ff, prefix[i-1].ss + v[i%n].ss); long double ans = 0.0; for(int i=0;i0?prefix[i-1]:mp(0LL,0LL))); cout << fixed << setprecision(50) << sqrt(ans) << endl; return 0; }
 » 7 months ago, # |   0 I wonder why use cross product to sort can not pass? But atan2() is ok...
 » 7 months ago, # |   0 The built-in function 'max' can compare how much data field? When I was doing The C problem,I used the function ,but I got a 'wa'!Then I write a max function myself,I got 'AC'!
•  » » 7 months ago, # ^ | ← Rev. 2 →   0 Edit: Found the bug , was printing the last cnt instead of max value Got AC. Can you help me finding what is wrong with my solution? #include using namespace std; int main() { long long n,i; cin>>n; long long int ara[n+2]; for(i=0;i>ara[i]; long long cnt=0,mval=0,l=n-1; for(i=0;iara[i])cnt=0; else cnt++; if(cnt>mval)mval=cnt; } cout<
•  » » » 7 months ago, # ^ |   0 Congratulation!
 » 7 months ago, # |   0 Went over AtCoder Problems and found that the difficulty of D in this contest is extraordinarily low.. Thought I'll give it a try. Surprised of how I came up with the solution instantly. Normally I could only solve problem A, B and C. Even problem C could be tough to me.