chokudai's blog

M-SOLUTIONS Programming Contest 2020 Announcement
By chokudai, history, 4 years ago, In English

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!

  • Vote: I like it
  • +94
  • Vote: I do not like it

Comments Comments (78)
| Write comment?
»
4 years ago, # |
← Rev. 2   Vote: I like it -9 Vote: I do not like it

.

→ Reply
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Happy :)

→ Reply
»
4 years ago, # |
  Vote: I like it +42 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Nice and interesting problems.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve E and F?

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it +8 Vote: I do not like it

    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.

    → Reply
»
4 years ago, # |
  Vote: I like it -7 Vote: I do not like it

How to solve problem E?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +2 Vote: I do not like 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

        → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you so much for sharing your approach.

      → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

      UPD: Link to Code

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it -8 Vote: I do not like it

        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
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it +33 Vote: I do not like it
    Solution
    EDIT
    → Reply
»
4 years ago, # |
  Vote: I like it +15 Vote: I do not like it

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

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I have the same doubt the code became too ugly

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    My Submission. (might be helpful)

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    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

    Link to my submission: https://atcoder.jp/contests/m-solutions2020/submissions/15452216

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +52 Vote: I do not like it

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

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is problem E a bit-mask dp problem?

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    current money will be too big

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How to approach?

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        greedy

        → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
        ← Rev. 3   Vote: I like it 0 Vote: I do not like it

        Approach is: buy low sell high

        Solution
        → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        try greedy for a change

        → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
        ← Rev. 3   Vote: I like it +8 Vote: I do not like it

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

        Code
        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Elegant solution.

          → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          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
          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

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

    Extra handling for first/last day.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +2 Vote: I do not like it

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

        → Reply
»
4 years ago, # |
  Vote: I like it +10 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # |
  Vote: I like it +1 Vote: I do not like it

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
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Overflow.

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # ^ |
        Vote: I like it +1 Vote: I do not like it

      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
»
4 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You're guaranteed all scores are non-zero.

      → Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 3   Vote: I like it +10 Vote: I do not like 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

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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
      • »
        »
        »
        »
        4 years ago, # ^ |
        ← Rev. 2   Vote: I like it +10 Vote: I do not like it

        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.

        → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +80 Vote: I do not like it

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

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

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

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

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

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    Thanks for the illustrations they are illustrative.

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    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!

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    When will the english editorial come?

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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!

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

    Input
    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply