Haha Yes :P

no offence, but plz stop complaining, start improving

Yes it is

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.

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.

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:

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

private int f(char p, char n) {
    int answer = Integer.MAX_VALUE;
    TreeMap<Integer, TreeSet<Integer>> pos = new TreeMap<>();
    TreeMap<Integer, TreeSet<Integer>> 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<Integer> a = pos.get(x);
        TreeSet<Integer> 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

Definitely there is. We can repeat rotating plane by 90 degree 4 times!
This idea made us publish this problem to AtCoder.

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

current money will be too big

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.

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

Overflow.

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

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

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

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

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.

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?

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.

Instead, I will share the content of 01-corner-03.txt so that it can help you debugging.

15
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