### chokudai's blog

By chokudai, history, 9 months ago,

We will hold M-SOLUTIONS Programming Contest 2020.

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

We are looking forward to your participation!

• +94

 » 9 months ago, # | ← Rev. 2 →   -9 .
•  » » 9 months ago, # ^ |   -7 Haha Yes :P
•  » » 9 months ago, # ^ |   0 no offence, but plz stop complaining, start improving
 » 9 months ago, # |   +1 Happy :)
 » 9 months ago, # |   +42 let's hope that the difficulty is similar to the ABC's.
•  » » 9 months ago, # ^ |   0 Yes it is
 » 9 months ago, # |   +11 Nice and interesting problems.
 » 9 months ago, # |   0 How to solve E and F?
•  » » 9 months ago, # ^ | ← Rev. 2 →   +8 For F case where they collide head on is trivial (store and upper bound for each plane on that line going in the opposite direction).Notice otherwise that if any two planes must collide, they must lie along a common diagonal of the appropriate type. For example, if we have a plane going up at 0, 0 and one going left at 3,3 they will collide (as would any two planes on this diagonal such that a lower one went up and a higher one went left), I store the info for every diagonal of each pair of directions that can collide and find the closest one of the other type by upper bounding for each of them, but there should be an easier way to implement it I guess.
 » 9 months ago, # |   -7 How to solve problem E?
•  » » 9 months ago, # ^ |   +21 I got AC simply by enumerating all the possible deployments of the rails.Key observation: a rail must be put across one site(residential area).First, enumerate the sites to put a rail across it. Then, enumerate the direction of the rails. Finally you can easily calculate the answer.The time complexity should be $O(3^N N^2)$.See my code here: https://atcoder.jp/contests/m-solutions2020/submissions/15450219PS: You can see it's running pretty slow but I think it's easy to think of.
•  » » » 9 months ago, # ^ |   0 Yes,But I think there may be two directions on one point.(two rails across it)
•  » » » » 9 months ago, # ^ |   +2 No, checking one direction individually is enough.Such scenario can arise if there are at least 3 points and they form a 'L' shape. For sake of simplicity let's just take 3 points A, B, C. Such that B is the point where rails in both directions are required. Thus We can view it as unidirectional rails across following pair of cities (A, C), (A, B), (B, C). Hence checking one direction is enough
•  » » » » » 9 months ago, # ^ |   0 Thank you very much :)
•  » » » 9 months ago, # ^ |   0 Thank you so much for sharing your approach.
•  » » » 9 months ago, # ^ | ← Rev. 2 →   0 My solution with $O(3^N * N * logN)$ (with few heuristics) is getting TLE. Can you look into it?? UPD: Link to Code
•  » » » » 9 months ago, # ^ |   -8 I hadn't looked at your code but if you had used set inside O(3^n) then TLE may be due to a huge factor of the set.
•  » » » » 9 months ago, # ^ |   0 I've been busy somehow so I can't edit your code but I can give a advice is that when N is as small as 15 you can try to do some reduction on the constant part instead of trying to get a more elegant theoretical time complexity. Vector is fast, but it's just fast among STLs, it can't be fast as a simple integer array (I think).
•  » » » 9 months ago, # ^ |   0 May be your code can perfectly deal with the problem that I mentioned above.Because if there are two rails on one point,suppose the East-West rail is $l$.If every point $a$ that on $l$ has a North-South rail across it,$l$ is useless.Otherwise,$l$ can be represented by the one without any North-South rail across it.
•  » » » 9 months ago, # ^ |   0 Is my submission $O(3^N N^2)$ as well? How can I optimise so that it passes just like yours?
•  » » » » 9 months ago, # ^ |   0 Err, like the comment above(https://codeforces.com/blog/entry/80595?#comment-669497), vectors are a bit slow (compared to simple integer array). And using powers of 3 to enumerate is also a bit slow compared to bitmasks. I'm not a native English speaker so I can't explain this to you clearly. Here's a blog for you to read. Hope it's helpful. https://codeforces.com/blog/entry/18169I mainly used the method No.9 and No.10 to iterate through.
•  » » 9 months ago, # ^ | ← Rev. 2 →   +33 SolutionFirst idea is: let's brute force which subset of points will have a horizontal line closest to it and which will have vertical.This way we reduce to 1D problem: given some set of points and number of people in each of them, for each $k$ from $0$ to number of points find minimum possible sum of distances for each people to nearest marked point/origin.First we can observe, that there is an optimal solution, where marked points coincide with some subset of input points (if not, we can choose some marked point which doesn't and if total number of people for whom current point is the closest is more on it's left we can move the marked point to the closest input point on the left and if not then to the closest on the right without increasing the answer).Given this we can solve the problem using some polynomial time dp, but this gets a bit ugly since we need to consider $0$ point as well. However given $N$ is very small we can solve this using some exponential time solution as well. Simple iterating through all sets of points we can choose gives $O(3^N)$ total subsets to check, but we still need to calculate distance sum which takes $O(n)$ with some two pointers or $O(n^2)$ with checking each pair: marked point, input point.At first I assumed $O(3^NN^2)$ will have low enough constant factor to pass, but sadly it didn't.The two pointers approach should be enough to pass, but I did something different, just because it's easier to implement:We still want to iterate through all sets of points which will be our input points and all its subsets which will be marked points, but we will do it in different order.First run through all subsets of points and assume those are the points which will be chosen, now for all other input points calculate distance to closest marked point (this phase implemented naively takes $O(n^2)$ in each loop, but it is inside $O(2^n)$ loop, so adds $O(2^nn^2)$ to total complexity, which is still less than $O(3^n)$) and then iterate through supersets of sets of marked points and for each of them calculate the score. Iterating through all of those points would take $O(3^N N)$ which stil should pass, but it's pretty easy to implement $O(3^N)$ in the following way:We know score for a set is just sum of scores over it's all elements, so just do: for set of all points equal to set of marked points, the score is $0$, for any other subset just pick one element $i$ and calculate score for element $i$ plus score for given set with element $i$ removed.Total time complexity $O(3^N)$, running time 130 ms. Code: https://atcoder.jp/contests/m-solutions2020/submissions/15439757 EDITAnother way, to speed up my first solution: instead of calculating score for each of input points, do it just for those which aren't markedComplexity is still $O(3^nn^2)$, but constant factors drops dramatically, which is enough to reach running time 1473 ms https://atcoder.jp/contests/m-solutions2020/submissions/15454904
•  » » » 9 months ago, # ^ |   +4 Thank you so much. Proszek_na_ludka
•  » » » 9 months ago, # ^ | ← Rev. 2 →   +4 My $O(2 ^ n * n ^ 3)$ solution code
 » 9 months ago, # |   +15 Any cleaner or simpler way to solve F than solving for both the axes and all 4 diagonals individually ?
•  » » 9 months ago, # ^ |   0 I have the same doubt the code became too ugly
•  » » 9 months ago, # ^ |   +3 My Submission. (might be helpful)
•  » » 9 months ago, # ^ |   +7 I did solve all 6 cases individually, but I wrote code that was relatively reusable for all 6 cases, so it wasn't too bad.So my code ended up looking like this: answer = Math.min(answer, f(R, L)); answer = Math.min(answer, f(U, D)); answer = Math.min(answer, f(U, L)); answer = Math.min(answer, f(R, D)); answer = Math.min(answer, f(D, L)); answer = Math.min(answer, f(R, U)); To actually compute f, I also isolated the part that's different based on L/R/D/U into move(positive, negative) and stay(positive, negative), which map the points onto a coordinate that stays fixed & a coordinate that moves in the pos/neg direction (I basically use the coordinates $x$, $y$, $x+y$, $x-y$ appropriately). How I actually compute fprivate int f(char p, char n) { int answer = Integer.MAX_VALUE; TreeMap> pos = new TreeMap<>(); TreeMap> neg = new TreeMap<>(); for (int i = 0; i < this.p.length; i++) { if (this.p[i].d == p) { add(pos, this.p[i].stay(p, n), this.p[i].move(p, n)); } else if (this.p[i].d == n) { add(neg, this.p[i].stay(p, n), this.p[i].move(p, n)); } } for (int x : pos.keySet()) { if (!neg.containsKey(x)) continue; TreeSet a = pos.get(x); TreeSet b = neg.get(x); b.add(Integer.MAX_VALUE); for (int i : a) { int j = b.ceiling(i); if (j == Integer.MAX_VALUE) continue; answer = Math.min(answer, j - i); } } return answer; } public int move(char p, char n) { if (p == R && n == L || p == U && n == D) return x + y - stay(p, n); return x + y + x - y - stay(p, n); } public int stay(char p, char n) { if (p == R && n == L || p == U && n == D) return p == R ? y : x; if (p == D && n == L || p == R && n == U) { return x + y; } return x - y; } Link to my submission: https://atcoder.jp/contests/m-solutions2020/submissions/15452216
•  » » 9 months ago, # ^ |   +52 Definitely there is. We can repeat rotating plane by 90 degree 4 times! This idea made us publish this problem to AtCoder.
 » 9 months ago, # |   0 Is problem E a bit-mask dp problem?
•  » » 9 months ago, # ^ |   +13 It depends how exactly you approach it, but probably it's more of "bitmask brute force" problem
 » 9 months ago, # |   0 Can someone help me optimize this dp (task D)?https://atcoder.jp/contests/m-solutions2020/submissions/15446834j is the jth day, p is the current money and s is the number of stocks? Since the constraints were low i thought this would pass. :(
•  » » 9 months ago, # ^ |   0 current money will be too big
•  » » » 9 months ago, # ^ |   0 How to approach?
•  » » » » 9 months ago, # ^ |   0 greedy
•  » » » » 9 months ago, # ^ | ← Rev. 3 →   0 Approach is: buy low sell high Solutionn = int(input()) a = list(map(int,input().split())) m = 1000 stocks = 0 drops = [False]*(n-1) for i in range(n-1): if a[i] > a[i+1]: drops[i] = True for i in range(n-1): if drops[i]: m+=stocks*a[i] stocks = 0 else: stocks+=m//a[i] m -= (m//a[i])*a[i] print(m + stocks*a[-1]) 
•  » » » » 9 months ago, # ^ |   0 try greedy for a change
•  » » » » 9 months ago, # ^ | ← Rev. 3 →   +8 Simple greedy works."Buy stocks only if its profitable to buy today and sell tomorrow." Codemoney:=1000 for i:=0;i+1
•  » » » » » 9 months ago, # ^ |   0 Elegant solution.
•  » » » » » 9 months ago, # ^ | ← Rev. 2 →   0 Why is it optimal to buy whenever the current price is higher than a previous price? As opposed to buying at minimum turning points and selling at maximum turning points?
•  » » » » » » 9 months ago, # ^ |   0 We can prove that this strategy and "buying at minimum turning points and selling at maximum turning points" produces same result. So if one is correct other is also correct. ProofLet change this problem into -You can buy stocks at price ai in the evening on ith day. You can sell stocks at price ai in the morning on ith day.Let's say you bought c stocks on local minima at price x.Since you greedily chose maximum possible c. Your leftover money will be less than x.Then you sold those c stocks at local maxima. What I will be doing is - Buy those c stocks in the evening of local minima.Sell those c stocks in the morning the next day.Again buy those c stocks in the evening on the same day.Sell those c stocks in the morning the next day.Again buy those c stocks in the evening on the same day.Net result I have c stocks with no profit.I will keep doing it until local maxima. I will sell those c stocks in the morning of local maxima.I won't buy on local maxima because the price of local maxima is more than the price the next day. With these ideas, I would recommend you to pick some examples and verify yourself how exactly this is working here and how this is equivalent to buying at local minima and selling at local maxima.
•  » » 9 months ago, # ^ | ← Rev. 2 →   0 money will grow exponentially. Consider cases like(100, 200), (100, 200), (100, 200) ... n timesmoney will be 1000 * 2 ^ nTo solve you need buy stocks at local minima and sell at next local maxima
•  » » 9 months ago, # ^ |   +6 I think D is more greedy. Buy on all local minimas, sell on all local maximas.Extra handling for first/last day.
•  » » » 9 months ago, # ^ |   +4 The worst part is, a similar question was already available on the internet...
•  » » » » 9 months ago, # ^ |   +2 Well, in AtCoder abc this is normal, at least for problems A-D.
•  » » 9 months ago, # ^ |   0 Thanks everyone for the reply!!!! I will look into greedy!
 » 9 months ago, # |   +10 Rank12! It's the highest rank I've ever had.
 » 9 months ago, # |   0 I felt E and F were tougher today than usual. I understood F could be done, by checking out the points of intersection for the lines, but that would make it O(n*n), and, the constraints would result in TLE. Google told me about some Sweep Line approach that would do this in O(n*logn), any ideas about how we could do this, or is this approach wrong altogether?
•  » » 9 months ago, # ^ |   0 I don't think line sweep is applicable here . Anyways I though of a solution that involved checking along the diagonals and along the same x and y axis . But it was very implementation heavy.I wonder there might be an easier solution.
•  » » 9 months ago, # ^ |   0 you can consider lines of the form: $x+y = c$ or $x - y = c$ and you can solve it in $O(n)$.
 » 9 months ago, # |   +1 Can anyone spot a mistake in this submission for C? https://atcoder.jp/contests/m-solutions2020/submissions/15433972 I got completely demotivated by screwing this one up :(
•  » » 9 months ago, # ^ |   0 Overflow.
•  » » » 9 months ago, # ^ |   +1 OMG, of course! /o\
•  » » 9 months ago, # ^ |   0 Me too. But the general idea is we don't need to calculate product in order to check for the condition . Lets assume product of first k exam is P which is constant. Now for the i'th exam grade we will do P = P/ar[i-k] * ar[i]. But if we see ar[i] > ar[i-k] then grade at i'th exam will be greater than the grade at i-th exam
•  » » » 9 months ago, # ^ |   +1 Yep, certainly.
•  » » » » 9 months ago, # ^ |   0 https://atcoder.jp/contests/m-solutions2020/submissions/15427322 My solution uses two pointer approach. Put one pointer at kth index and second pointer at 0th index. Start comparing and incrementing both pointers.
•  » » 9 months ago, # ^ |   0 You don't need to store the actual multiplication. You can just check if next multiplication is greater than previous or not.You can do this just by looking at for every i from 1 to n-k -> if (a[k+i] + a[i+1] — a[k+i-1] — a[i]) is greater than 0 or not. Also just keep checking if you've encountered a 0 or not because it will make every multiplication 0.I still couldn't do it as I got urgent work and leave the contest in between after 2 wrong tries in C. ;(
•  » » » 9 months ago, # ^ |   +1 Yup, I had an epic eclipse of the brain thinking that 2 * 10^5 multiplies of 10^9 won't overflow the long long!
 » 9 months ago, # | ← Rev. 2 →   +3 Is there going to be an editorial in English? Nevertheless, can someone share their approach to solving E?
 » 9 months ago, # |   0 In question C , i use sliding window to calculate grade, I want to know that will it cause me overflow. I was using long long. I was getting wrong answer but i think it will remain in bounds.
•  » » 9 months ago, # ^ |   0 Even 3 numbers of 1e9 will be 1e27, which exceeds long long.
•  » » » 9 months ago, # ^ |   0 oh my bad. got it
•  » » 9 months ago, # ^ |   0 Check for 0 element(s) as It will make certain multiplications zero also we can not divide anything with it :)
•  » » » 9 months ago, # ^ |   0 You're guaranteed all scores are non-zero.
•  » » » » 9 months ago, # ^ |   0 Ohh Yes, But can you help then why this logic fails. I thought if I'm at i-th index and go to (i+1)th index (to see if grades increased or not ) then I also move from (i-k)th index to (i-k+1)th index at back to main the window size. Then the multiplication will increase if (a[i+1]+a[i-k+1] — a[k] — a[i-k]) > 0 otherwise not. this worked for 12 test cases and 8 test cases shown WA. Can you help?
•  » » 9 months ago, # ^ | ← Rev. 3 →   +10 Instead of computing the grades, you can note that $\displaystyle g_i = \prod_{j=i-k+1}^i a_j$, and $\displaystyle g_{i-1} = \prod_{j=i-k}^{i-1} a_j$You can divide them and get $\displaystyle \frac{g_i }{ g_{i-1}} = \frac{a_i }{ a_{i-k}}$, so you only need to compare $a_i$ and $a_{i-k}$ and don't need to multiply out the full products.Link to my submission: https://atcoder.jp/contests/m-solutions2020/submissions/15416319
•  » » » 8 months ago, # ^ |   0 I actually understand the implementation of your code but the problem and it's explanation is bit tricky. After reading a problem I just multiply the product and stores in the vector and got wrong answer . As I am new to Competitive Programming.
•  » » » » 8 months ago, # ^ | ← Rev. 2 →   +10 As others have discussed, the problem is something called "overflow" -- if you just multiply everything, the answer will be too large for the computer to store correctly. To illustrate for yourself, try writing code to print $1, 3, 3^2, ..., 3^{100}$ and you'll see at some point the numbers "wrap around" and become negative or something.
•  » » » » » 8 months ago, # ^ |   0 Thanks for your help. Now I understand why my code don't produce the desired output.
•  » » 9 months ago, # ^ |   0 Let Ai (1<=i<=N) equals 10^9, N equals 200000, and K equals N-1. Therefore the grade for each term will be 1000000000^199999. Absolutely overflow.
•  » » 9 months ago, # ^ |   0 You can use average too. Instead of multiplication compare their averages like this#include using namespace std; typedef long long ll; //Micro Futures scalping to get my tendies int main(){ ll n,k; cin>>n>>k; ll arr[n]; for(int i = 0; i < n; i++){ cin>>arr[i]; } ll pre[n+1]; pre[0] = 0; for(int i = 1; i < n+1; i++){ pre[i] = pre[i-1]+arr[i-1]; } for(int i = k+1; i <= n; i++){ double sum1 = pre[i-1]-pre[(i-1)-k]; double sum2 = pre[i]-pre[i-k]; sum1 = sum1/(double)k; sum2 = sum2/(double)k; if(sum2-sum1 > 0.000000000) cout<<"Yes\n"; else cout<<"No\n"; } } 
 » 9 months ago, # | ← Rev. 2 →   +80 Hello from Japan, I am the writer of this contest. First of all, thank you for your participation, and if you like some of our problems, I will be glad. Anyway, this time, we gathered the problems which are educational, which are based on algorithms and implementation techniques that may need if you want to get high performances in ARC/AGC. Competitive programming is not only thinking but also implementation. Especially in problem F, you may come up with the solution easily. But, if you doesn't choose appropriate implementation way, the code length will be much longer than the writer's solution. In addition, we made practical and social-issue-based problems — For problem D, this problem can be used in stock market. For problem E, this problem can be used in city planning. For problem F, this problem can be used in airlines. Again, I am very glad to see you in the standings. Thank you :)
•  » » 9 months ago, # ^ |   +11 Solid contest, I really liked the problems. Keep up the good work!
•  » » 9 months ago, # ^ |   +19 I wrote a 200 liner code for F ( without the template) , but in the end i just couldn't debug it . Anyways Awesome Contest .
•  » » 9 months ago, # ^ |   +10 Thanks for the illustrations they are illustrative.
•  » » 9 months ago, # ^ |   +10 The contest was really helpful for beginners like me. For us, who don't know all the standard techniques, contests like these help a lot in our learning process.For example, I kept getting Wrong Answer in D (17/21) passed, only to find in the comment section that the stocks can be long long as well, inspite of such small constraints!
•  » » 9 months ago, # ^ |   +5 When will the english editorial come?
 » 9 months ago, # |   0 I was wondering how to solve D if there were multiple stocks. I think this would be quite hard.
•  » » 9 months ago, # ^ |   0 There will be a dp solution definitely that I can't think about.
 » 9 months ago, # |   0 Are there any English translations for the editorial?
 » 9 months ago, # |   0 hi, chokudai, i got only one WA at testcase 01-corner-05.txt of problem E, is it possible that i could obtain this testcase for debugging?
•  » » 9 months ago, # ^ |   0 Usually testcases get published here after some time: https://www.dropbox.com/sh/nx3tnilzqz7df8a/AAAYlTq2tiEHl5hsESw6-yfLa?dl=0. At the moment testcases of this contest haven't been published yet, but I'm sure they will be in a few days.
•  » » » 9 months ago, # ^ |   0 Thanks and I'll wait for more days to see.
 » 8 months ago, # |   +5 Please add the english editorial for this contest on the atcoder website ASAP. Please !
 » 8 months ago, # | ← Rev. 2 →   0 chokudai: When will the test data be available?I'm trying to solve E in $O(3^N N)$ but I'm getting WA on test 01-corner-03.txt only, even my stress testing failed to detect a case.UPD: I was able to fix the bug and got AC code.My idea is to get permutations representing the sorted points (both by X and Y) then try all the possible $3^N$ combinations (0 no line, 1 horizontal line, 2 vertical line), then for each combination (i.e. "0021022101") for each 0 we calculate the distance to the nearest 1 and 2, and since that we know the order in both X, Y we can do this in a linear time, so the overall complexity is $O(3^N N)$.Thanks for the strong tests!
•  » » 8 months ago, # ^ |   +1 Instead, I will share the content of 01-corner-03.txt so that it can help you debugging. Input15 2000 10000 999975 4000 8000 999984 6000 6000 999991 8000 4000 999962 10000 2000 999975 -2000 -10000 999919 -4000 -8000 999964 -6000 -6000 999977 -8000 -4000 999989 -10000 -2000 999995 9997 -9997 1000000 9991 -9991 999904 9000 -9000 999947 -9997 9997 999926 -9991 9991 999930 
•  » » » 8 months ago, # ^ |   +10 Great, thank you :)
 » 8 months ago, # |   0 chokudai Any update on the english editorial ?
 » 7 months ago, # |   0 The official editorial is finally published in English! In fact, the translation has completed in August 25th, and I am sorry for the late announce. Since we wrote a 16-page Japanese editorial (2x longer than usual), I guess that the translation was a long work.