M-SOLUTIONS Programming Contest 2020 Announcement

4 years ago, # ^ |

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

→ Reply

huzaifa242

4 years ago, # ^ |

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

→ Reply

4 years ago, # ^ |

Thank you very much :)

→ Reply

will.earn.you

4 years ago, # ^ |

Thank you so much for sharing your approach.

→ Reply

huzaifa242

4 years ago, # ^ |

← Rev. 2 →

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

UPD: Link to Code

→ Reply

ISuckAtLife

4 years 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.

→ Reply

BurnoutAg7

4 years ago, # ^ |

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

→ Reply

https://codeforces.me/blog/entry/18169

4 years ago, # ^ |

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.

→ Reply

ahzong

4 years ago, # ^ |

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

→ Reply

BurnoutAg7

4 years ago, # ^ |

Err, like the comment above(https://codeforces.me/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.

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

→ Reply

tribute_to_Ukraine_2022

4 years ago, # ^ |

← Rev. 2 →

+33

Solution

First 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

EDIT

→ Reply

will.earn.you

4 years ago, # ^ |

Thank you so much. tribute_to_Ukraine_2022

→ Reply

_overrated_

4 years ago, # ^ |

← Rev. 2 →

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

→ Reply

ExplodingFreeze

4 years ago, # |

+15

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

→ Reply

practice_account_

4 years ago, # ^ |

I have the same doubt the code became too ugly

→ Reply

aviroop123

4 years ago, # ^ |

My Submission. (might be helpful)

→ Reply

4 years ago, # ^ |

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 f

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

→ Reply

square1001

4 years ago, # ^ |

+52

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

→ Reply

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

4 years ago, # |

Is problem E a bit-mask dp problem?

→ Reply

tribute_to_Ukraine_2022

4 years ago, # ^ |

+13

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

→ Reply

Default_______________28

4 years ago, # |

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

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

→ Reply

4 years ago, # ^ |

current money will be too big

→ Reply

Default_______________28

4 years ago, # ^ |

How to approach?

→ Reply

4 years ago, # ^ |

greedy

→ Reply

brezhart

4 years ago, # ^ |

← Rev. 3 →

Approach is: buy low sell high

Solution

n = 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])

→ Reply

practice_account_

4 years ago, # ^ |

try greedy for a change

→ Reply

keep__calm

4 years ago, # ^ |

← Rev. 3 →

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

Code

money:=1000
for i:=0;i+1<n;i++{
  stocks:=money/a[i]
  money+=stocks*max(a[i+1]-a[i],0)
}
Fprintln(out,money)

→ Reply

iabhishek15

4 years ago, # ^ |

Elegant solution.

→ Reply

squirrel123

4 years ago, # ^ |

← Rev. 2 →

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?

→ Reply

keep__calm

4 years ago, # ^ |

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.

Proof

→ Reply

dush1729

4 years ago, # ^ |

← Rev. 2 →

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

→ Reply

spookywooky

4 years ago, # ^ |

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

Extra handling for first/last day.

→ Reply

Imperial_Lord

4 years ago, # ^ |

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

→ Reply

spookywooky

4 years ago, # ^ |

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

→ Reply

feecIe6418

4 years ago, # |

+10

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

→ Reply

Imperial_Lord

4 years ago, # |

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?

→ Reply

AVL_trivial

4 years ago, # ^ |

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.

→ Reply

BenL

4 years ago, # ^ |

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

→ Reply

4 years ago, # |

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

→ Reply

hetp111

4 years ago, # ^ |

Overflow.

→ Reply

4 years ago, # ^ |

OMG, of course! /o\

→ Reply

meiniak

4 years ago, # ^ |

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

→ Reply

4 years ago, # ^ |

Yep, certainly.

→ Reply

Matuagkeetarp

4 years ago, # ^ |

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

→ Reply

4 years ago, # ^ |

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

→ Reply

toothbrush

4 years ago, # |

← Rev. 2 →

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

→ Reply

meiniak

4 years ago, # |

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.

→ Reply

Matuagkeetarp

4 years ago, # ^ |

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

→ Reply

4 years ago, # ^ |

You're guaranteed all scores are non-zero.

→ Reply

4 years 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

→ Reply

codingoo

4 years ago, # ^ |

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.

→ Reply