chokudai's blog

By chokudai, history, 6 months ago, In English

We will hold AtCoder Beginner Contest 165.

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

We are looking forward to your participation!

UPD:

In Problem E, the constraints says N <= 100000, but it turned out that the inputs are made under the condition N <= 200000.

It was revealed that only 6 people were affected by the defect of the problem E constraint, and 4 among them were rated competitors. As the impact is very minor, contestants excluding the four are going be rated, and the affected four will also be rated after rejudging to get AC on their submissions.

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

»
6 months ago, # |
  Vote: I like it +35 Vote: I do not like it

2 ABC this weekend, what a time to be alive! Thanks a lot AtCoder team for making this quarantine more fun!

  • »
    »
    6 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    I guess extra contests are to cover up for the unrated ones

»
6 months ago, # |
  Vote: I like it +11 Vote: I do not like it

Did the start time just got extended by 5 minutes?

»
6 months ago, # |
  Vote: I like it +1 Vote: I do not like it

website crashed ?

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

site is not loading?

»
6 months ago, # |
  Vote: I like it +5 Vote: I do not like it

RIP

»
6 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Site down?

»
6 months ago, # |
  Vote: I like it +7 Vote: I do not like it

Again 502 Bad Gateway :(

»
6 months ago, # |
  Vote: I like it +1 Vote: I do not like it

504 Gateway Time-out:(

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Postponed for 5 minutes.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Start time extended by 10 minutes.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Its good that they acted quickly otherwise this contest also could be unrated :D

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Looks like the start time is extended by 10 minutes.

»
6 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

extended by more 5 min :(

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

website is loading too slow

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Will they just postpone the contest by increments of 5 minutes until enough people go away and there is less load on their servers??

»
6 months ago, # |
  Vote: I like it -9 Vote: I do not like it

delayed due to inadequacy in problem

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

“The start will be delayed for 10 minutes due to an inadequacy discovered in the problem. I'm sorry.“

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Here we go

»
6 months ago, # |
  Vote: I like it -6 Vote: I do not like it

C is too hard for C, imo.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    easy

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Same for me. That C was insane :(.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Solved E, but didn't C...

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I solved C but couldn't solve E :(

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      10! algorithm would work

      take a look at the constraints

      • »
        »
        »
        »
        6 months ago, # ^ |
        Rev. 3   Vote: I like it +7 Vote: I do not like it

        it would be (n+m-1)C(m-1), so worst case 19C10

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

          How could you get this formula?I saw same question in one educational round but i don't know proof behind this formula?

          • »
            »
            »
            »
            »
            »
            6 months ago, # ^ |
            Rev. 2   Vote: I like it 0 Vote: I do not like it

            there's a n*m size rectangle, at the beginning, you are at the bottom-left corner, now that formula is the number of ways to get to the right side of the rectangle only go right or top.

          • »
            »
            »
            »
            »
            »
            6 months ago, # ^ |
            Rev. 2   Vote: I like it +7 Vote: I do not like it

            You have M distinct numbers you can give each number some frequency and frequency of each number can be between [0, N] (N = length of sequence), since you have to make sequence increasing so for any fix combination of numbers and frequencies there will be only one increasing sequence. So now the problem is reduced to find the number of solutions of equation f1+f2+f3+..+fm = N, where fi is frequency of ith number in the sequence.

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Solved F but not C and E.

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

        same. F was easy, if you know O(nlogn) solution for finding LIS.

        • »
          »
          »
          »
          »
          6 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Well actually I was doing LIS in O(nlogn) and I got TLE on 6 tests :C

      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I tried solving F using coordinate compression and range-max segment tree. But i kept getting WA :( . Been trying to figure out the error, but I wasn't able to. Here is my submission WA solution

        • »
          »
          »
          »
          »
          6 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          It also happened to me.

          lets denote some variable: max_val=maximum compressed value

          prev_val=query(pos[u],pos[u])[value of the index of pos[u] , before line 45]

          1) in line 45:

          update(pos[u], val) -> update(pos[u],max(val,prev_val))

          2) in line 46:

          ans[u] = val -> ans[u] = query(0,max_val)

          3) in line 52:

          update(pos[u], 0) -> update(pos[u],prev_val)

          I suppose this works fine...

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

            Thanks a lot. Realized that for considering the LIS for a path from 1 to k, I take the answer as dp(k), instead of max(dp(i)) for i from 1 to k.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    +1. Solved rest but couldnt do this.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It was too hard for me too. I thought number of combinations will be too large. But turns out there can be at max 92378 for n=10 and m=10. So brute force works.

»
6 months ago, # |
  Vote: I like it +3 Vote: I do not like it

How to solve C !

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    just try all the state.

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      Though I doubted whether it will get TLE in the beginning...

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How does this work, I came to the conclusion that there are $$$10^{10}/2$$$ possible arrays to check. To much.

      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        No you are wrong ,There are much fewer arrays!! You can write a dfs to count them.

      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        There are 92378 possible arrays for N = 10, M = 10 that have A[i]>=A[i-1] only.

        • »
          »
          »
          »
          »
          6 months ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          Well, thanks for explanation.

        • »
          »
          »
          »
          »
          6 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          how did you got this ?

          • »
            »
            »
            »
            »
            »
            6 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Either go with a brute solution and find using code or use P&C and we can say sum of gaps between consecutive numbers is at max m-1 and number of gaps are n-1, so g1+g2+g3... gn-1 + k = m-1, so number of whole number solutions of this equation are m-1+n-1Cn-1

      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        actually the number of array is 10 choose 10 with repetition so that means it is 19 choose 10 which is equal to 92378. I have solved it in the most crazy way. my submission

        • »
          »
          »
          »
          »
          6 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I did'nt get it... how is it becoming 19C10?

          • »
            »
            »
            »
            »
            »
            6 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            It is a well known concept called combination with replacement. Imagine you have a pool of numbers from $$$1 - 10$$$, and you want to select $$$10$$$ numbers with replacement (ex you can take the same number multiple times) this can be found using $$$n+k-1 \choose k$$$. If you want to read more about [here](https://en.m.wikipedia.org/wiki/Stars_and_bars_(combinatorics))

            • »
              »
              »
              »
              »
              »
              »
              6 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Correction: it is $$$n + k - 1 \choose n$$$ which equal to $$$n + k - 1 \choose k - 1$$$

        • »
          »
          »
          »
          »
          6 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          262 line code! really u r a coder.

      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        we should only consider monotonically increasing sequence

      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it +26 Vote: I do not like it

        Combinatorial way to look at it.

        You need to find number of arrays $$$A = \{ A_1, A_2, ..., A_N \} $$$, such that $$$ 1 \le A_1 \le A_2 \le ... \le A_N \le M $$$.

        Let $$$ x_i $$$ be the number of occurences of $$$ i $$$ in the array. Then we require number of solutions to $$$ x_1 + x_2 + ... + x_M = N $$$, where $$$ x_i \ge 0 $$$.

        This, given by Stars and Bars, is simply $$$ {N+M-1} \choose {M-1} $$$ = $$$ {10+10-1} \choose {10-1} $$$ = $$$ 19 \choose 9 $$$ = $$$92378$$$.

        I usually use this website to do quick calculations for combinations, during contests.

    • »
      »
      »
      6 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      :)

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Backtracking

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    just

    int k = v[cur — 1]; while (k<= m) { v.push_back(k); dfs(cur + 1); v.erase(v.begin() + cur); ++k; }

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can write a recursive brute force, which will include all possible states we can go to.

    Consider we want to fill n places. We start from place_id = 1, and num = 1.

    Now we have 3 possible cases:

    • Don't include the current number at this place, so increment the 'num' by +1.
    • Include the number so now we need to fill next place, so increment 'place_id' by +1 and continue using the same number for further positions.
    • Include the number at the current position, but we don't want to use the same number for next pos, so increment both 'place_id' and 'num' by +1.

    If you are confused, you can take a look at my submission, though it isn't the cleanest. Submission

    I hope it helped.

»
6 months ago, # |
  Vote: I like it -11 Vote: I do not like it

Honestly, I think it is not very wise to give such C and D in abc contest.

I am sure there a thousends(?) of possible participants not submitting any solution because scared by a hard C and a D full of corner cases.

Dont get me wrong, I think these are nice problems, but simply misplaced.

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

    I can solve D by math with no corner cases. https://atcoder.jp/contests/abc165/submissions/12609383 Can not solve C. E. F.

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

      D was just to take x as min(b-1,n).

    • »
      »
      »
      6 months ago, # ^ |
      Rev. 2   Vote: I like it +5 Vote: I do not like it

      F was easy with segment tree i think

      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Are you serious ?Why you used segment tree for E?

        • »
          »
          »
          »
          »
          6 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          sorry my bad, F

          • »
            »
            »
            »
            »
            »
            6 months ago, # ^ |
            Rev. 2   Vote: I like it +6 Vote: I do not like it

            I think F by set will be more easy

            check that
    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Would you please simulate your math formula!

      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Take x as min(b-1,n)

        The second part of the function becomes zero and the first part becomes maximum.

      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it +6 Vote: I do not like it

        you need to maximize, but if you observe for any x >= b, float[x/b] will always be greater than 0, and then you multiply it with A, but float[Ax/b] can atmost be equal to that. Thus its always optimal to make float[x/b] = 0, so that you answer is float[Ax/b]. To make that equal to 0, just take max x < b, but since x <= N, x = min(n, b-1). Then return the answer.

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      can you explain your solution please?

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Explanation for D; If x increased by B, value not change, so we only consider x in range 0 — min(b-1,n); So The second part of the function becomes zero and the first part becomes maximum.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Is C very hard?just try all the state!

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I thought about that, just can not believe it will not get TLE. Maybe I evaluate time complexity wrong.

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

        Why not write a simple dfs to count the number of them?

        • »
          »
          »
          »
          »
          6 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I calculated Combination(20, 10), and ... What the fxxx was I thinking about!!!

          • »
            »
            »
            »
            »
            »
            6 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Is it $$$C_{m+n-1}^n$$$ ?

            • »
              »
              »
              »
              »
              »
              »
              6 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Yes, you are right. I do not know how to input formula.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

The English Commentary for Problem C and D is here

  • »
    »
    6 months ago, # ^ |
    Rev. 2   Vote: I like it +5 Vote: I do not like it

    D with binary search... Wait. what? How? What does your check function do? The function isn't strictly increasing nor decreasing as far as I understand..

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      it's not increasing nor decreasing... however if you notice function is increasing in intervals of b. eg. from x = 0,1,2,..b — 1 f(x) is increasing at x = b f(x) again drops and starts increasing same as for previous x

      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Exactly, since it drops at B, you can't binary search on interval (0,n). If you are Bsearching on interval (0,B-1), that isn't required, since it is increasing from 0 to B-1...so B-1 is going to give you maximum.

        Also, I am not sure if this Bsearch on (O,N) will work always. Since it is repeating maybe that is why it worked.

  • »
    »
    6 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Please provide proof of your construction in D

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone give a hint on E and F?

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why is my ternary search failing on one test case for D? :((

https://atcoder.jp/contests/abc165/submissions/12647186

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Why you are using ternary search ... Its just simple math

    • »
      »
      »
      6 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      F

      I just assumed the function was unimodal and tried ternary search and it almost AC'd. Can you elaborate your solution?

      EDIT: unimodal not monotonic

      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        The function is repeating after every B values of X.

        Try to express X = qB + r and solve the equation. You will find that, function is max when r = (B-1). Also, in case, b — 1 > N, then N is your answer cause, from 0 to B-1 the answer is increasing.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    @chosun Notice that if n>b no binary search or ternary search if you apply binary search from 1 to n. Binary search's lower and higher bounds will be [1, min(n, b)]

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      It works now thanks. Damn I was pulling my hair out last 5 minutes trying to debug this thing!

      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        This simple mistake cost 4 wrong submissions to me :(

  • »
    »
    6 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    No need for ternary search, answer is monotonic with modulo value with B.

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      When you know it is monotonic between 0 to B-1, when not just return B-1...

  • »
    »
    6 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    or binary search My submission

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Anyone tell how to do C

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    C is just backtracking. Try all possibilities of the sequence

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem statement of C was so confusing.Can anyone explain it?

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Please look at English Commentary of problem C here Thank you! Hope that helps!

  • »
    »
    6 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    You are asked to create an array a, of size N. You should place values in that array from 1 up to M. The array should be not decreasing.

    Then you get those quadrupels. If you put at position a and b values, so that the difference is c, you get d points.

    Try to find an array with maximum possible points.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I`m soooo stupid.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve F ?

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Apply the O(nlogn) algorithm for LIS during the dfs while nullifying the changes made by a particular branch of a node when we visit its another branch.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I maintained a segment tree for current root to node path for lis, and as i move down i make updates like in normal lis, and as i move up, i roll-back on the changes i did previously.

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      With segment trees and coordinate compression was required I think to backtrack.

»
6 months ago, # |
  Vote: I like it +26 Vote: I do not like it

All the people complaining about C being too hard. Is it possible that they didn't notice the constraints that array is in increasing order A[1] <= A[2] <= A[3]..... <= A[N]? Because I skipped it initially and thought for several minutes that total case are $$$10^{10}$$$ which was outside the time limit.

  • »
    »
    6 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Same happened with me. How many possible combinations are possible ?

    a1 <= a2 <= ... <= an , (1<=ai<=m)

    Solved it, but I couldn't prove the time complexity.

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it +21 Vote: I do not like it

      Observe, that if you pick set of numbers, there can be only one possible array, so you just need to count number to choose n elements from 1 to m, it is exactly $$$\binom{n+m-1}{n}\le 92378$$$

      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        There is a small mistake. I think the time complexity should be $$$C_{n+m-1}^{m-1}$$$.

        • »
          »
          »
          »
          »
          6 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          It's actually the same because $$$\binom{n}{k}=\binom{n}{n-k}$$$

          • »
            »
            »
            »
            »
            »
            6 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            I'm sorry. It's my mistake. I didn’t think twice. So stupid.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it -10 Vote: I do not like it

    And... is 10^10 not outside the time limit?

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    First i wrote a dp solution to count how many such arrays exists. Then used brute force.

    Spoiler
  • »
    »
    6 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    In fact there are only $$$C_{m+n-1}^n$$$

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

how to implement problem B ?? can anyone post their accepted solution

»
6 months ago, # |
  Vote: I like it +39 Vote: I do not like it

Solns/Approaches

  • A. Check every element

  • B. Observe that answer never exceeds 5000 (use log to check). We can loop until success.

  • C. Generate every possible combination. In python, we have combinations_with_replacement which generates exactly what we need

  • D. Observe that for $$$x < b$$$, $$$\lfloor x/b \rfloor$$$ is zero. We want to take $$$x = kb-1$$$. Also observe that taking $$$k > 1$$$ always make the answer worst. We take $$$x$$$ as $$$\min(n, b-1)$$$.

  • E. What we need is set of $$$(a, b)$$$s such that distance between $$$a, b$$$ never occurs twice. (Considering not only b-a, but we have to consider the other way. e.g, when $$$n = 10$$$, distance between $$$1$$$ and $$$10$$$ is 1 and 9. both should not appear again.)
    When $$$n$$$ is odd, take $$$(1, n), (2, n-1), \dots$$$. One can easily show that this is valid.
    When $$$n$$$ is even, take those values until we can't. (e.g, when $$$n = 10$$$, we take $$$(1, 10)$$$, $$$(2, 9)$$$ but not $$$(3, 8)$$$ since distance between $$$(3, 8)$$$ is 5 and 5 — repeated.) Then, discard one unused value and proceed. (e.g, after two takes, use $$$(3, 7)$$$ instead of $$$(3, 8)$$$, and $$$(4, 6)$$$.
    Submission : https://atcoder.jp/contests/abc165/submissions/12617571

  • F. Consider computing LIS length in $$$O(n \log n)$$$ time with DP and lower_bound. (without considering the actual values). When we do this, we discard what was in that spot (lower bound). Instead of doing this, keep those values by multiset or stuff like that. We traverse tree in DFS order, pushing values we meet in LIS-solving pattern but keeping values instead of throwing away. When we traversed all of it's subtrees, we erase value of the node from where we pushed. To do this we track the number of non-empty multisets and index we pushed each value in. Time complexity $$$O(n \log n)$$$.
    Submission : https://atcoder.jp/contests/abc165/submissions/12637543

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    @gratus907 can you please tell how you came to conclusion for problem E?

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I thought it intuitively after some casework... and I tried to prove my thought (I mean, not rigorously, but like convincing enough to start writing code)
      As I've wrote, a case when two people meet twice is only when there exists $$$(a, b)$$$ and $$$(c, d)$$$ which $$$b-a$$$, $$$n+a-b$$$, $$$d-c$$$, $$$n+c-d$$$ has repetitions. Try some casework in $$$n = 8$$$, $$$n = 10$$$ to convince yourself with this statement :)

      I actually have nothing much to say as I did tons of caseworks on paper...:(

  • »
    »
    6 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    You don't really need any multiset for problem F. Just change the value at lower_bound and remember what it was. After solving all subtrees and updating the answer just return the value to what it was. Submission

    • »
      »
      »
      6 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Apparently yes.. I discussed this problem with my friend after the contest and he also said the same thing. I felt very dumb since he coded like 800 bytes while I coded more than 2000... lol
      I have no idea how I managed to think returning values by dfs tree and then thought something like "WOW I want vector<multiset<int>>" and started coding :(

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve D?

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    take x as min(b-1,n)

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The target is to keep the minus part as small as possible.So tried to make the second part 0. So if n>=b, made it x=b-1 and it worked fine.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

The Editorial is in Japanese. I want an English editorial.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Generally they used to post english editorial after 5-6 days,but if you want you can google translate the pdf.(After translation it will have weird english but understandable)

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I'm assuming some greedy strategy works for C. Can somebody please post their logic/solution? I filtered queries such that for each (a, b) indices pair — the optimal c for maximum d is known. For the array A[n], I set A[0] = 1. From here, I am confused about how to construct the rest of the array. I tried a couple of ways but there were always some cases not adhering to the rule.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    C was a pruned brute solution i think.

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yeah. During the contest, I thought the time complexity would be too much. I wish I had checked it with a program though. For n = m = 10, there are about 48,000 possible sequences only.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Spoiler
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

It seems difficult orz

»
6 months ago, # |
  Vote: I like it +43 Vote: I do not like it

I think E is harder than F, as I'm not good at construction and pattern observing

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    F was like if you know segment tree you will solve it immediately. Nothing special was in it

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it +19 Vote: I do not like it

      How is segment tree related to F? I think most contestants solve it like this: submission

      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        You can find lenghh of LIS ending at a node u, using segment tree as well after compressing a[i] s

        • »
          »
          »
          »
          »
          6 months ago, # ^ |
            Vote: I like it +28 Vote: I do not like it

          Oh, I got it. But I think this implementation is much easier.

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Could you please Explain, how to solve F using segment tree. Thanks It_Wasnt_Me

»
6 months ago, # |
  Vote: I like it +12 Vote: I do not like it

Is this round a bit easier than before? I used to solve 4 or 5 problems but today I solved 6 within a short time. Well anyway the problems are still very good (like, you can solve D and E with about 300 bytes of code but you need to think a long while). BTW, I think C is a bit hard for C. Since DFS may be not very "beginner-friendly".

»
6 months ago, # |
  Vote: I like it +4 Vote: I do not like it

D one was way too easier than the C one

»
6 months ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

Check Same question ... I still missed it.. hard luck today.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

F is an easier version of NA Southeast Regional 2019 problem G

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

谁知道结果什么时候出来啊(When rating changes?)(I can't speak English well……)

»
6 months ago, # |
Rev. 4   Vote: I like it -29 Vote: I do not like it

Nice contest!

  • »
    »
    6 months ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    This comment shouldn't be answered. This is a problem from an ongoing contest, Bubblecup.

»
6 months ago, # |
Rev. 2   Vote: I like it +8 Vote: I do not like it

From stars and bars trick we get for C only 92378 states are there i.e ncr(10+10-1,10-1)

»
6 months ago, # |
  Vote: I like it +4 Vote: I do not like it

A. Oh, constraints are really small, let's just iterate.
B. Hm, it's exponential growth, I think max answer is not too big. Let's write and see (turns out max answer was in samples, but I didn't notice).
C. Hm, seems like a lot of states, no idea, let's read D.
D. Hmm, let's write bruteforce and see. Oh, it's always zero for multiples, ok, let's take multiple-1 if we can.
C. Hmm, maybe there are not too many states? Let's write bruteforce and see. Oh, it's really small, dumb me. (It's just C(n + m — 1, n))

E and F are nice, but quite easy.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How do you arrive at C(n + m — 1, n)? I had to count them by writing the dfs.

    • »
      »
      »
      6 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      The sum of gaps between consecutive numbers is less than equal to m-1, it's basic P&C afterwards.

    • »
      »
      »
      6 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it
    • »
      »
      »
      6 months ago, # ^ |
      Rev. 3   Vote: I like it +24 Vote: I do not like it

      This is a classic stars and bars application.

      Note the condition that $$$1 \leq A_1 \leq A_2 \leq ... \leq A_n \leq M$$$. Thus, it is sufficient to count how many times each number from $$$1$$$ to $$$M$$$ appears in the sequence (because we would then only have one way to arrange these numbers---in nondecreasing order). So, now imagine a line with $$$N$$$ stars and $$$M-1$$$ bars. The stars before the 1st bar corresponds to the number of 1s, the stars between the 1st and 2nd bar correspond to the number of 2s, etc. For example, if m=4 and n=7, then *||****|** corresponds to one $$$1$$$, zero $$$2$$$s, four $$$3$$$s, and two $$$4$$$s. So, how many possible ways are there to arrange $$$M-1$$$ bars and $$$N$$$ stars in a line? There are $$$M+N-1$$$ "spaces", and of them we need to choose $$$N$$$ locations to be where we place the stars. We place the bars in all other locations.

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

        Thanks!

      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Isn't it "N locations to be where we place the stars. We place the bars in all other places"?

        • »
          »
          »
          »
          »
          6 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          You are correct, I have edited it now. Thanks

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain the observation made in problem E.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

in problem E: if i match 1 with n then 2 with n-1 and so on (m times) why is it wrong

I got WA with this approach in 9 test cases

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone prove the running time complexity for the brute solution of C please?

  • »
    »
    6 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    O(Q * 92378) because number of valid(non-decreasing arrays) arrays with n = 10 and m = 10 are 92378. You can calculate this with dp or with Combinatorics.

    Code for Counting with Dp
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by chokudai (previous revision, new revision, compare).

»
6 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

May someone help me debug F: LIS on Tree? I have done using binary search and dynamic programming. I have used 0-indexed dp. My submission: https://atcoder.jp/contests/abc165/submissions/12674946

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it
»
6 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

How does the checker work in E? chokudai

  • »
    »
    6 months ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    For all the pairs given by the user check their difference both ways. Like 1 and 10 will have difference 1 and 9. These differences should be all different. So you can check in O(M).

»
6 months ago, # |
  Vote: I like it -6 Vote: I do not like it

I can't understand why my A solution fails Here's my code

k=int(input()) a,b=map(int,input().split()) if b-a+1>=k: print('OK') else: print('NG')

can anyone point out my mistake

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

why would I get WA for problem.E

#include <bits/stdc++.h>

#define x first
#define y second
#define pii pair<int,int>
#define sz(x) (int)(x).size()
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long LL;
const int maxn = 1005;
int main(){
    int n,m; cin >> n >> m;
    vector<pii> ans;
    int L = 1,R = n;
    while(m){
        if(L+n-R == R-L) L += 1;
        else{
            ans.push_back(pii(L,R));
            L++; R--; m--;
        }
    }
    for(int i = 0;i < sz(ans); ++i) 
        cout << ans[i].x << " " << ans[i].y << '\n';
    return 0;
}
»
6 months ago, # |
Rev. 2   Vote: I like it +24 Vote: I do not like it

I believe the test files for the problem E were incorrect.
Instead of n <= 100000 , it should be m <= 100000 . If I write an assert statement for the value of n being less than or equal to 1e5, the verdict is RE, while for 2e5+2 it is AC.

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

    Oh, there was a clarification as well, my bad. :(

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem F:I have used LIS(nlogn) with B.F.S. but getting T.L.E......please help. https://atcoder.jp/contests/abc165/submissions/12695808

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

    You may try dfs instead.(Read my code for more info).

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

      I have used dfs but got TLE Here is the link: https://atcoder.jp/contests/abc165/submissions/12791770

      • »
        »
        »
        »
        6 months ago, # ^ |
        Rev. 2   Vote: I like it +3 Vote: I do not like it

        You shouldn't pass a "vector L" in a function.You know,vectors are like arrays,so they require time to pass between functions.Try changing it to" vector &L",which passes a "virtual" vector(like a pointer).That shall get an AC.

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

          Or you can make L an array out of the dfs functions.My code used just that.

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

            Ok thanks. But can you figure out complexity of that code

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

              O(n log n) for dp,plus a constant(of the vector).It's good enough.

        • »
          »
          »
          »
          »
          6 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Can you figure out the complexity of my above code?

          • »
            »
            »
            »
            »
            »
            6 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            O(n^2)(for passing the vector).

            • »
              »
              »
              »
              »
              »
              »
              6 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Thank you I got the concept. Whenever we pass a vector by value it copies the content rather than updating it which is costly

»
6 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Here is my list of submissions.You can use that as reference.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why are there different results when using GCC and Clang? There are 4 testcases that fail to pass, but my method has no problem. So I checked the official testcase and the input and output, and found that the final problem is that GCC and Clang have different results. I want to know why? ? ? ! ! ! here is my two submission:(the first is AC and the second is WA,but the code is exactly the same!) Your text to link here... Your text to link here...

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Wangxuelong, the defined arrays a,b,c,d should have length 51 if you intend to write into them at positions 1, ..., 50 — this causes your code to write outside of bounds of the arrays, causing undefined behavior (it can still theoretically work, but also the compilers decided to zero out all variables in your program, it would still be a valid thing to do according to C++ spec — the compiler is free to do anything it wants when you do out of bounds access).

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For E detail explanation with examples and code check here

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone suggest similar problems to C?

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anybody find me the bug with this solution for problem C? Since both n and m is very small, I literally checked all possible combinations of the first m numbers using bit masking, but for some weird reasons, the combinations are not being properly generated, please help me in finding the potential bug in this submission.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For E,can some one tell me why this is wrong: void solve() { cin>>n>>m; int now=1; for(int i=1;i<=m;i++) { cout<<now<<" "<<(n+now-i-1)%n+1<<endl; a[now]=1; a[(n+now-i-1)%n+1]=1; while(a[now])now=(n+now-1-1)%n+1; } return ; }