maroonrk's blog

By maroonrk, history, 12 days ago, In English

We will hold AtCoder Regular Contest 123.

The point values will be 300-400-600-700-700-1000.

We are looking forward to your participation!

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

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

Hope for a good contest!

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

Front seat!

»
11 days ago, # |
  Vote: I like it +2 Vote: I do not like it

Ah, It's too hard! :(

»
11 days ago, # |
  Vote: I like it -7 Vote: I do not like it

For the first time I solve three problems in ARC.

I'm so happy :)

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

    How did yo solve it? Can you explain your idea?

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

      I think my solution is not so good.

      You can read the official editorial now.

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

    How did you solve $$$C$$$? Please tell.

»
11 days ago, # |
  Vote: I like it +10 Vote: I do not like it

»
11 days ago, # |
  Vote: I like it +1 Vote: I do not like it

How to solve C?

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

    Indeed how to solve $$$C$$$. Greedy algorithms like taking largest possible number fail. I felt it was kind of similar to yesterday's A

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

    Digit dp-esque dp worked for me

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

      colud you elaborate ?

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

        First, use the fact that the answer should be maximum 10 (or even lower couldn't bother to prove a tighter bound), and then we should think about how each of $$$a_i$$$ contributes to each digit of n. A length k number will contribute k digits of n from the first digit to the kth digit once, so instead of figuring out what the individual $$$a_i$$$ could be, we could shift our focus to how many numbers focus on a specific digit of n. Let $$$b_i$$$ denote the number of $$$a_i$$$ that contributes to the ith lowest digit. Then, it should be clear that $$$b_i$$$ is non_increasing similar to a cumulative frequency. Now, we just want to know if it is possible to create n from a sequence of $$$b_i$$$ that is where digit dp comes in. The first parameter of the dp is the current position starting from the lowest digit, and the second is $$$b_i$$$ at that position and finally, the last parameter is how much we carried over from the last digit.

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

          Amazing use of digit dp!

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

          I didn't understand why you use array f in your solution you did not update array f.

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

            I mean I did use the array to store the dp results in the line int &res = f[pos][choice][up]? Next time when you comment please read the code carefully and then comment.

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

    dp digit

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

      I have a greedy solution, but I can't prove it :

      https://atcoder.jp/contests/arc123/submissions/24372393

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

        me too but i can't solve the num like 91 ```

        include

        include

        using namespace std;

        typedef long long ll;

        int main() { int t; cin >> t; while (t--) { ll n; cin >> n; int a[20] = { 0 }, pos = 0; while (n) { a[++pos] = n % 10; n /= 10; } int ans = 0; for (int i = 1; i <= pos; i++) { if (a[i] == 0)ans = max(ans, 4),a[i+1]--; ans = max(ans, a[i] / 3 + (a[i] % 3 ? 1 : 0)); } cout << ans << "\n"; }

        return 0;
        

        } ```

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

      How did you learn digit DP? I have tried learning it a couple of times already but have never been able to understand it. What kind of prerequisite/background does one need for really understanding it? I currently can only solve classic DP problems.

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

        I had to learn after I couldn't solve this question, yet I couldn't solve C

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

        I learned it from this blog post Link:. The explanation is great and also has a handful of problems which you can solve to practice digit dp.

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

    for a given k can we do it? if we can answer this then its easy just do k++ until we get one. It will never go too far. Now lets try to answer the first part that for a given k can we do it? Try to think of a dp state. run a loop from right to left digits one by one in n. ( i=1 to len(n)) i=1 corresponding to the rightmost digit.

    we will pass three variables after every iteration i. lowest and highest carry, and mx_k that is the maximum no. of i-1 digit numbers possible up to this point. and lowest and highest carry should correspond to mx_k.

    tough to explain the mx_k part. Give a good read and think you will get what I meant to say.

    my solution

  • »
    »
    11 days ago, # ^ |
    Rev. 2   Vote: I like it +16 Vote: I do not like it

    Another solution with dfs: The restriction that no digit can be 0 is troublesome, so I considered to clear out this. We minus n with numbers like 111111, 1111 first, and then the digits can be 0,1,2, which is a greedy problem similar to 1530A. Thus it can be proved that the answer is not greater than 5, and we are able to solve it by dfs. For each number, we only need to fix its length, and minus n with 11..1 with the same length. In the end check whether n (after minus) can be constructed by numbers which digits are 0 or 1 or 2. With a little amount of optimization, the solution was accepted.

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

how to solve D? there's no editorial for it

  • »
    »
    11 days ago, # ^ |
    Rev. 3   Vote: I like it +5 Vote: I do not like it

    If $$$a_i > a_{i+1}$$$, it's optimal to choose $$$b_i = b_{i+1}$$$, else it's optimal to choose $$$c_i = c_{i+1}$$$.
    Then, the $$$b_i$$$ and the $$$c_i$$$ can be uniquely determined for a fixed $$$b_1$$$ and they have the form $$$\mid b_1 - k \mid$$$ ($$$k$$$ is different for each $$$b_i$$$ and $$$c_i$$$).
    The optimal $$$b_1$$$ is the median of the $$$2n$$$ values of $$$k$$$.

  • »
    »
    11 days ago, # ^ |
    Rev. 2   Vote: I like it +10 Vote: I do not like it

    ternary search on the value of $$$B_1$$$, knowing that $$$B_i=B_{i-1}+max(A_i-A_{i-1},0)$$$ and C as the complement of B

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

      Can you share your submission? My ternary search fails for some reason. Submission

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

        I think you make an overflow in Calc, sum can be up to 1e15*2e5 which is to big

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

          Thanks. The actual bug was that minimum sum can be over 1e18. So I have to take initial value as LLONG_MAX. Also as you pointed out in the ternary search, 1e15 will overflow. So taking low as -1e13 and high as 1e13 now worked for me. Even 1e12 is bad.

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

    It's the first editorial in E. Seem like the author put it in the wrong place.

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

    One of the (almost) middle elements can be 0

    After fix we do simple greedy to left and right

    arc123/submissions/24365978

»
11 days ago, # |
  Vote: I like it +58 Vote: I do not like it

Err......Starting from C, the problems are too hard for me:(

I have to say, contests in AtCoder are becoming more and more challanging. Is that because the problem setters are stronger and stronger or I'm weaker and weaker?

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

    I think AtCoder is turning harder and harder.

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

    All the latest ARCs are mostly hard, you also need to get used to the ARC problems, on my first ARCs I always had a bad performance and the problems seem quite difficult, however after some contests, you will find the problems more accessible (excluding all F's, and some E's, and the other problems are still hard, but at least you can elaborate more on how to solve them). They are really fun and you can learn and enjoy a lot. I am really grateful to all atcoder writers, coordinators, and staff, the contests are great.

»
11 days ago, # |
  Vote: I like it +8 Vote: I do not like it

Why number of contestant is so small than number of contestant at any begginer contest !!

»
11 days ago, # |
  Vote: I like it +31 Vote: I do not like it

The approach of problem D is similar with 1406D - Three Sequences, 1442A - Extreme Subtraction.

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

How large could the answer be for problem D? I thought the answer could go up to $$$10^{18}$$$ which was a terrible mistake as I got 7 WA because of it and changing the limit to LLONG_MAX just solved the issue.

»
11 days ago, # |
Rev. 5   Vote: I like it +1 Vote: I do not like it

For A the approach I followed is,

Let mean of consecutive differences in the array be dd;

So I iterated on differences from (dd — epsilon) to (dd + epsilon) (epsilon can be anything I considered 2) and checked all possible arrays for a particular difference and took the array with minimum operations. It got accepted but I cannot prove it.

Can anyone help me with the proof?

Here's my submission Task A

Thanks in advance :)

»
11 days ago, # |
  Vote: I like it +54 Vote: I do not like it
Spoiler
»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone help me with understanding the editorial of problem A.i am having difficulty in understanding the answer part "Let k be the number of times we add 2 to X. Then, it is necessary that k≧0 and X+2k≧0, which can be represented as k≧k0 where k0=max(0,⌈(−X)/2⌉) If we fix k≧k0 , we need to do X+2k additions of −1, for a total of X+3k operations. In order to minimize this number, we should minimize k, which means the answer is X+3k0. The time complexity of our approach is Θ(1)." Here what's the need of taking k0... why do we need to do x+2k additions of -1, and how did the total operations became as x+3k...and should i have prerequisite of any topic to understand this editorial!!

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

    the sequence [a,b,c] is an arithmetic one if a-b == c-b so 2b — a — c must equal 0 let x = 2b — a — c and we will make x equal to 0 by two operations : 1. increase x by 2 (same to add 1 to b in the original problem) 2. decrease x by 1 (same to add 1 to a or c ) now there are 2 cases : x > 0 then the only way to make it 0 is decreasing it by one x times (so we need x operations). x < 0 then we will keep adding 2 until x becomes positive then back to the case 1 this case requires Ceil( x / 2 ) operations.

    `

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

      You didn't explain $$$x+3k$$$ logic.

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

        Let's explain two examples here- $$$a={4 ,8 ,10}$$$

        $$$x = 2*a[1]-a[0]-a[2] = 2.$$$

        So we need to increase either $a[0]$ or $$$a[2]$$$ total of $$$2$$$. Here $$$x$$$ is the answer cause both odd and even number can be formed with $$$a[0]$$$ and $$$a[2]$$$.

        But when $$$a={10 ,3 ,5}$$$

        $$$x = 2*a[1]-a[0]-a[2] = 6-15=-9.$$$

        $As$ $$$x$$$ is odd we can not increase $$$a[1]$$$ to any odd number (as it's a multiple of $$$2$$$).So we need to increase $$$min(a[0],a[2])$$$ and $$$a[1]$$$ by $$$1$$$ after adding the $$$x/2$$$.

        For the above example array would become

        $$$a={10,7,5}$$$

        $after$ adding $$$x/2$$$ to the $$$a[1]$$$ and Finally the answer array would be

        $$$a={10,8,6}$$$
        code
      • »
        »
        »
        »
        10 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Let us suppose that we had done k operation to make X positive by adding -2 to X i.e X+2k >= 0 now X-2k is either 0 or become some positive integer(let's say z = X+2k) which we need to minimize to 0 by adding -1 . To make z to zero we had to add add -z which is equal to additional z operations(i.e we had to do X-2k operations) and we had already done k operations in beginning so k + X + 2k = X+3k. For example X = -9 . First we add 5 operations each adding -2 to X, then X becomes 1 (i.e X+2k = 1) to make now we need to do (x+2k operations each adding -1 to it) i.e 1 operation. So total operation is 5+1 = 6

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

      thanks for the explaination..it was really helpful

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve B?

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

    First sort all the three input arrays(A,B,C) and then count for valid triplets such that the upper bound of first element from the first array A uniquely exists in second array B and upper bound of that element from second array B uniquely exists in third array C.

    Code
    • »
      »
      »
      10 days ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      thanks nice explanation :)

      • »
        »
        »
        »
        10 days ago, # ^ |
        Rev. 4   Vote: I like it 0 Vote: I do not like it

        It's surely TLE.How can you expect erase function to work in $$$log(n)$$$ complexity. I used ordered set to erase the elements whose complexity is $$$log(n)$$$ unlike vectors.

        code
        • »
          »
          »
          »
          »
          10 days ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

          I mean all self-balancing binary search trees, such as the std::(multi)set (red-black tree) or avl trees, allow deletion in $$$O(log(n))$$$ complexity due to its self balancing nature. For this specific problem, I used std::multiset which worked under 150ms.

        • »
          »
          »
          »
          »
          10 days ago, # ^ |
          Rev. 4   Vote: I like it 0 Vote: I do not like it

          yeah you are absolutely correct , i also got tle but then i use unordered_map

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

    I used 3 pointers approach.

    Sort all the three arrays, start from the beginning. If x[i] < x[j], then there are two possibilities i.e x[j] < x[k] then we get the valid triplet so increment the answer and all the pointers by 1, otherwise if x[j] > x[k], then we'll have to pickup a bigger element from the 3rd array so we increment k by 1. Similarly if x[i] > x[j], we'll have to pickup a bigger element from the 2nd array so we increment j by 1.

    Time Complexity of this method will be O(n*logn + n) = O(n*log(n)) as we are doing this in a single iteration after sorting all three arrays.

    Code
»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Could someone find my mistake in Problem B. I sorted all the input array A,B and C and then finding index in C using upper bound. If found then I store it in variable named k and start searching again for other possible index starting from k index. 13 test cases were passed but other failed. Please help My code link

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Is the question level as same in ARC as DIV2 codeforces.

Is it true that ARC(a<b<c<d.......)?

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

Atcoder solution B RE

Why I am getting runtime error can anyone explain?

Spoiler
»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks a lot for a detailed editorial like this.

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

A very good contest! But now Atcoder is being maintained so that I can't see the editorial for problem E, can anyone explain how to solve problem E? Thanks a lot!

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Will you provide the code for F?

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

In Problem C Can Anyone Explain

  • A number can be written as the sum of K good numbers if and only if it can be written as the sum of the following:
  1. An integer between K and 3K;
  2. The sum of at most K good numbers, multiplied by 10.

The above statement in Editorial. It would be a Great Help