chokudai's blog

By chokudai, history, 3 weeks 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

»
3 weeks ago, # |
Rev. 2   Vote: I like it -9 Vote: I do not like it

.

»
3 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Happy :)

»
3 weeks ago, # |
  Vote: I like it +42 Vote: I do not like it

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

»
3 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

Nice and interesting problems.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve E and F?

  • »
    »
    3 weeks 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.

»
3 weeks ago, # |
  Vote: I like it -7 Vote: I do not like it

How to solve problem E?

  • »
    »
    3 weeks 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.

    • »
      »
      »
      3 weeks 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)

      • »
        »
        »
        »
        3 weeks 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

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you so much for sharing your approach.

    • »
      »
      »
      3 weeks 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

      • »
        »
        »
        »
        3 weeks 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.

      • »
        »
        »
        »
        3 weeks 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).

    • »
      »
      »
      3 weeks 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.

    • »
      »
      »
      3 weeks 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?

  • »
    »
    3 weeks ago, # ^ |
    Rev. 2   Vote: I like it +33 Vote: I do not like it
    Solution
    EDIT
»
3 weeks 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 ?

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I have the same doubt the code became too ugly

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    My Submission. (might be helpful)

  • »
    »
    3 weeks 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

  • »
    »
    3 weeks 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.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Is problem E a bit-mask dp problem?

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

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

»
3 weeks 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. :(

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    current money will be too big

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How to approach?

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        greedy

      • »
        »
        »
        »
        3 weeks ago, # ^ |
        Rev. 3   Vote: I like it 0 Vote: I do not like it

        Approach is: buy low sell high

        Solution
      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        try greedy for a change

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

          Elegant solution.

        • »
          »
          »
          »
          »
          3 weeks 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?

          • »
            »
            »
            »
            »
            »
            3 weeks 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
  • »
    »
    3 weeks 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

  • »
    »
    3 weeks 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.

    • »
      »
      »
      3 weeks 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...

      • »
        »
        »
        »
        3 weeks 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.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
3 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

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

»
3 weeks 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?

  • »
    »
    3 weeks 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.

  • »
    »
    2 weeks 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)$$$.

»
3 weeks 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 :(

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Overflow.

  • »
    »
    3 weeks 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

  • »
    »
    3 weeks 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. ;(

    • »
      »
      »
      3 weeks 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!

»
3 weeks 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?

»
3 weeks 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.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 weeks 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 :)

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You're guaranteed all scores are non-zero.

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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?

  • »
    »
    3 weeks 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

    • »
      »
      »
      11 days 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.

      • »
        »
        »
        »
        11 days 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.

        • »
          »
          »
          »
          »
          11 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 weeks 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.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    like this
»
3 weeks 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 :)

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

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

  • »
    »
    3 weeks 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 .

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    Thanks for the illustrations they are illustrative.

  • »
    »
    3 weeks 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!

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    When will the english editorial come?

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Are there any English translations for the editorial?

»
2 weeks 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?

»
11 days 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 !

»
6 days 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!

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

chokudai Any update on the english editorial ?