We will hold M-SOLUTIONS Programming Contest 2020.

- Contest URL: https://atcoder.jp/contests/m-solutions2020
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20200725T2100&p1=248
- Duration: 100 minutes
- Number of Tasks: 6
- Writer: E869120, square1001
- Rated range: ~ 1999

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

We are looking forward to your participation!

.

Haha Yes :P

no offence, but plz stop complaining, start improving

Happy :)

let's hope that the difficulty is similar to the ABC's.

Yes it is

Nice and interesting problems.

How to solve E and F?

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.

How to solve problem E?

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/15450219

PS: You can see it's running pretty slow but I think it's easy to think of.

Yes,But I think there may be two directions on one point.(two rails across it)

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

Thank you very much :)

Thank you so much for sharing your approach.

My solution with $$$O(3^N * N * logN)$$$ (with few heuristics) is getting TLE. Can you look into it??

UPD: Link to Code

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.

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).

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.

Is my submission $$$O(3^N N^2)$$$ as well? How can I optimise so that it passes just like yours?

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/18169

I mainly used the method No.9 and No.10 to iterate through.

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 marked

Complexity 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

Thank you so much. I_love_chickpea

My $$$O(2 ^ n * n ^ 3)$$$ solution code

Any cleaner or simpler way to solve F than solving for both the axes and all 4 diagonals individually ?

I have the same doubt the code became too ugly

My Submission. (might be helpful)

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:

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 fLink to my submission: https://atcoder.jp/contests/m-solutions2020/submissions/15452216

Definitely there is. We can repeat rotating plane by 90 degree 4 times!

This idea made us publish this problem to AtCoder.

Is problem E a bit-mask dp problem?

It depends how exactly you approach it, but probably it's more of "bitmask brute force" problem

Can someone help me optimize this dp (task D)?

https://atcoder.jp/contests/m-solutions2020/submissions/15446834

j 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. :(

current money will be too big

How to approach?

greedy

Approach is: buy low sell high

Solutiontry greedy for a change

Simple greedy works.

"Buy stocks only if its profitable to buy today and sell tomorrow."

CodeElegant solution.

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?

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.

money will grow exponentially. Consider cases like

(100, 200), (100, 200), (100, 200) ... n times

money will be 1000 * 2 ^ n

To solve you need buy stocks at local minima and sell at next local maxima

I think D is more greedy. Buy on all local minimas, sell on all local maximas.

Extra handling for first/last day.

The worst part is, a similar question was already available on the internet...

Well, in AtCoder abc this is normal, at least for problems A-D.

Thanks everyone for the reply!!!! I will look into greedy!

Rank12! It's the highest rank I've ever had.

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 Lineapproach that would do this in O(n*logn), any ideas about how we could do this, or is this approach wrong altogether?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.

you can consider lines of the form: $$$x+y = c$$$ or $$$x - y = c$$$ and you can solve it in $$$O(n)$$$.

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 :(

Overflow.

OMG, of course! /o\

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

Yep, certainly.

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.

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. ;(

Yup, I had an epic eclipse of the brain thinking that 2 * 10^5 multiplies of 10^9 won't overflow the long long!

Is there going to be an editorial in English? Nevertheless, can someone share their approach to solving E?

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.

Even 3 numbers of 1e9 will be 1e27, which exceeds long long.

oh my bad. got it

Check for 0 element(s) as It will make certain multiplications zero also we can not divide anything with it :)

You're guaranteed all scores are non-zero.

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?

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

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.

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.

Thanks for your help. Now I understand why my code don't produce the desired output.

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.

You can use average too. Instead of multiplication compare their averages

like thisHello 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 :)

Solid contest, I really liked the problems. Keep up the good work!

I wrote a 200 liner code for F ( without the template) , but in the end i just couldn't debug it . Anyways Awesome Contest .

Thanks for the illustrations they are illustrative.

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!

When will the english editorial come?

I was wondering how to solve D if there were multiple stocks. I think this would be quite hard.

There will be a dp solution definitely that I can't think about.

Are there any English translations for the editorial?

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?

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.

Thanks and I'll wait for more days to see.

Please add the english editorial for this contest on the atcoder website ASAP. Please !

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!

Instead, I will share the content of

`01-corner-03.txt`

so that it can help you debugging.InputGreat, thank you :)

chokudai Any update on the english editorial ?