chokudai's blog

NOMURA Programming Contest 2022（AtCoder Beginner Contest 253） Announcement
By chokudai, history, 3 years ago, In English

We will hold NOMURA Programming Contest 2022（AtCoder Beginner Contest 253）.

The point values will be 100-200-300-400-500-500-600-600. We are looking forward to your participation!

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

Comments Comments (23)
| Write comment?
»
3 years ago, # |
  Vote: I like it +31 Vote: I do not like it

Great round. Interesting problem F. Also, D and E might be educational for someone.

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

    As someone who got WA on D and E, I can confirm.

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

    logic for E was quite simple,tho i got two WA in it bcz i didnt consider case k=0. Can u plz explain F and intuition behind , i was not able to think much in that :( overall awesome contest :)

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

    The corner case K=0 took me eight times of submissions to find:(

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

I find it hard to not get lost in details while implementing F.

Edit: Here is some (notworking) code to illustrate the problem:

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

    I used a persistent segment tree (range update, point query) which helped me avoid a lot of implementation. I did however take a while to understand how to use the persistent segment tree template I found :P

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

      Persistent segment tree! Wonderful idea!

      In fact I have also considered it during contest but finally give up this idea for two reasons. Reason 1, I remember that persistent segment tree can not deal with interval updating (now I understand that we could use single-element updating instead, and thus this will not be a problem). Reason 2, I can't write it fast and correctly (I only wrote it once when I was trying this problem https://mirror.codeforces.com/contest/484/problem/E)

      Thank you for sharing your idea!

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

        I believe that persistent segment tree CAN deal with interval updates.

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

          I used the primer tree to solve F

          submission

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

          Thank you for pointing out my mistake. I think I really don't fully understand this technique. I just learned it from this problem https://mirror.codeforces.com/contest/484/problem/E, where only single-element updating is involved.

          Would you like to recommend any good tutorials about this :D

          UPD: I mean, how to implement interval updating in persistent segment tree :)

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

            If you're asking about how to perform range updates and point queries (as opposed to the usual point update, range query) without the use of lazy propagation, here's how to do it:

            Let's say you want to increment the interval $$$[L, R]$$$ by some amount $$$x$$$. Let's increment the value at index $$$L$$$ by $$$x$$$ and increment the value at index $$$R + 1$$$ by $$$-x$$$. Now, if at any time you want to query the value at index $$$i$$$, the answer is the sum of the interval $$$[0, i]$$$ (assuming you index from $$$0$$$). Essentially, if $$$L \le i \le R$$$, then the update at $$$L$$$ also adds to $$$i$$$'s value. If $$$R < i$$$, then both $$$x$$$ and $$$-x$$$ get added to the effective value at $$$i$$$, resulting in a change of $$$0$$$. If $$$i < L$$$, the update on the interval $$$[L, R]$$$ doesn't affect $$$i$$$.

            You can also use this idea to perform range updates and point queries with a Fenwick Tree.

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

              Thank you for your detailed and clear explanation! This is such a nice trick to transform between single-element and interval updating.

              Although my question is in fact to ask how to implement interval updating in persistent segment tree, still thanks a lot!

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

Any hints for F ? I am clueless.

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

    Foreach query of type 3 we can more or less simply find the time when the row was last set to X. If we know the sum of col-updates at that point of time, we can calculate ans=sum2-sum1+x

    Where sum2 is sum of col updates at time query type 3, sum1 is sum of col updates at last update of row, and x the value that row was set to.

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

    I did it in offline mode.

    Firstly stored all queries in one vector For each query of type 3 find index j such that this will follow the conditions :
    (i) j < i
    (ii) query type of j is 2 ( row update query )
    (iii) Row value for both queries are same

    and store the index i to one vector (lets say previous_needed) so previous_needed[j].push_back(i)

    basically value at point (i,j) depends on the the following values :

    (i) last row update with row number i
    (ii) value added to column j before last row updation
    (iii) value added to column j from starting

    answer = (i) + (iii) — (ii)

    we can find the value of any column at any moment by using segment tree in O(logN)

    for each type of query 2 at index i: we store the value for all query of type 3 depend on i th query ( basically i th query is the last row updation for such queries ) into map of pair -> int

    for each col in previous_needed[query[i].row]
    store {query[i].row , col} = column value for col (using seg tree) to prev_value

    then for each query of type 3 :
    answer = last_updation_on_row[query.row] + total_added_value_in_column[query.col] — prev_value[{query.row , query.col}]

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

    You can use sqrt decomposition to solve this problem.

    Naive approach is to maintain $$$prefix$$$_$$$sum$$$, where $$$prefix$$$_$$$sum[i][j]$$$ gives sum of $$$x$$$ added to column $$$j$$$ after first $$$i$$$ queries.

    Suppose in $$$i_{th}$$$ query, you want answer for cell $$$(l,r)$$$ from , answer is $$$prefix$$$_$$$sum[i][r]-prefix$$$_$$$sum[j-1][r]+x[j]$$$, where row $$$l$$$ was last updated in $$$j_{th}$$$ query. Note that this solves our problem, but we can't store $$$prefix$$$_$$$sum$$$ after all queries.

    So, if you store the $$$prefix$$$_$$$sum$$$ after $$$i_{th}$$$ query iif $$$i$$$ is a multiple of $$$1000$$$, you end up storing sum for atmost $$$200$$$ queries.

    So time complexity is $$$O(\frac{m^2}{b} + q \cdot (\frac{m}{b}+ b))$$$, where $$$b=1000$$$.

    My submission

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

Nice problems and thanks to writers and testers :)

Problem D is about application of inclusion-exclusion principle, and maybe good practice for learning how to compute gcd and lcm as well.

E is a classic dp problem, which also includes a classic optimization in order to reduce the complexity, and it costs me 2 WAs before I realized the tricky case k=0. Nice trap!

For F, I couldn't believe that I got AC before the contest ends, what a miracle! My idea is similar to the editorial, but I think the calculation of S(k,j) is not an easy task. Except for the segment tree part, one should also be very careful of, when and how, to compute S(q,j) and S(q',j). At least, I think my implementation is somehow a little complicated.

I read problem G during the last 10 minutes. I think I have got close to the idea mentioned in the editorial, although some part is not correct. Hope that someday, I could solve G and have time to read problem Ex (Yeah, I have never got a chance to read Ex before contest ends :D)

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

    You can simply use Fenwick Tree instead of segment tree in Problem F. That will be a lot easier.

    ABC253G is the easiest problem to get the correct idea of all Problem G-s I have ever solved in ABC. But it took me 30mins and a wrong answer attempt to get accepted. I missed many implementation details and took a long time debugging my code.

    Hope that someday we could solve A-F within 20 minutes as well :)

    Almost 50 minutes this time. I'll try to be better next time.

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

      Wow, 50 minutes for A-F, amazing! I finished F after about 90 minutes. There is still a long way for me.

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

Am I the only person who thinks that have seen problem F before on codeforces or somewhere? If anyone know the source of the problem please put the link here thanks in advance.

→ Reply