We will hold NOMURA Programming Contest 2022（AtCoder Beginner Contest 253）.
- Contest URL: https://atcoder.jp/contests/abc253
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20220528T2100&p1=248
- Duration: 100 minutes
- Number of Tasks: 8
- Writer: nok0, Kodaman, PCTprobability, m_99
- Tester: leaf1415, physics0523
- Rated range: ~ 1999
The point values will be 100-200-300-400-500-500-600-600. We are looking forward to your participation!
Great round. Interesting problem F. Also, D and E might be educational for someone.
As someone who got WA on D and E, I can confirm.
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 :)
The corner case K=0 took me eight times of submissions to find:(
I find it hard to not get lost in details while implementing F.
Edit: Here is some (notworking) code to illustrate the problem:
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
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://codeforces.com/contest/484/problem/E)
Thank you for sharing your idea!
I believe that persistent segment tree CAN deal with interval updates.
I used the primer tree to solve F
submission
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://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 :)
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.
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!
Any hints for F ? I am clueless.
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.
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}]
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
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)
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.
Almost 50 minutes this time. I'll try to be better next time.
Wow, 50 minutes for A-F, amazing! I finished F after about 90 minutes. There is still a long way for me.
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.
It is not same but similar. Maybe you remember this.
I found F very similar to this problem
but F is 2D