We will hold AtCoder Beginner Contest 261.
- Contest URL: https://atcoder.jp/contests/abc261
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20220723T2100&p1=248
- Duration: 100 minutes
- Number of Tasks: 8
- Writer: kyopro_friends, math957963, blackyuki, leaf1415, m_99, YoshikaMiyafuji
- Rated range: ~ 1999
The point values will be 100-200-300-400-500-500-600-600. We are looking forward to your participation!
Pretty bad difficulty distribution A-F too standard and complete piece of cake 1600 problems at best, while G-H have literally no solves. Honestly, didn't enjoy.
I don't get the downvotes, it was objectively a bad contest in terms of difficulties. None of the A-F required thinking, while being the problems for target audience.
can anyone tell me why my solution got tle in D https://atcoder.jp/contests/abc261/submissions/33473914
Your vectors x and c get copied a lot by using them as function arguments.
Thank You and lesson learned
Could anybody explain E solution please since the editorial is kind of lacking information?
The idea is to create foreach bit position a function that transforms the input bit at that position to the output bit at that position, then apply that function to each bit on each round.
Also we alter the function itself on each round, by applying the new input for that round.
Another idea for E would be to maintain (foreach bit) the last operation that set the bit to 1, or set the bit to 0, and the number of flip (xor) operation since the last setting of it.
Alright I see that, thank you
E was pretty cool. Tripped on A for a while thinking the range intervals were closed. My bad...
Can you please explain your solution for E? I stuck so hard at it. Can u please help me give some similar problems?
Observation 1: Notice each operation can be done for each bit independently.
So?: The problem is now reduced to "given just the 1st bit(0/1), find the value of the 1st bit after performing all operations". We can do this for all bits and join them later according to the first observation.
Observation 2: We should find a way to calculate $$$pref[i][j]$$$ = answer to reduced problem for the first $$$i$$$ operations such that the 1st bit is $$$j$$$.
So?: After doing so, the problem becomes given a starting bit $$$j$$$, apply $$$pref[i][k] (1<=i<=n)$$$ where $$$k$$$ is the current value of the bit after performing the previous operations. You should be able to use prefix sums logic to calculate the pref array.
Now, lets get back to the original problem. There are at most $$$30(\lceil log N \rceil)$$$ bits in C, so we do this for all 30 bits and now, the array becomes $$$pref[i][j][k]$$$ = answer to reduced problem for the first $$$i$$$ operations such that the $$$j$$$th bit is $$$k$$$.
Impl details: The values in the array can be calculated with just two variables, $$$A$$$ and $$$B$$$ to store $$$pref[i][j][0]$$$ and $$$pref[i][j][1]$$$ respectively. Initially all bits in $$$A$$$ are set to $$$0(A=0$$$), while all bits in $$$B$$$ are set to $$$1(B=2^{30}-1)$$$
Time complexity: $$$\mathcal{O}(NlogN)$$$
Submission
Can someone Explain E and can give similar problems like E ?? Thank you!!
So, we have to do perform $$$first$$$ $$$i$$$ $$$operations$$$ on certain $$$X$$$ for the $$$ith$$$ $$$operation$$$. so what we can do is, we can precompute the result for $$$first$$$ $$$(i - 1)$$$ $$$operations$$$ for $$$each$$$ $$$bits$$$ so that we can easily say that $$$jth$$$ $$$bit$$$ would be $$$set$$$ or $$$unset$$$ based on $$$jth$$$ $$$bit$$$ $$$state$$$ before $$$i$$$ $$$operations$$$.
So we can do that as follows:
If you have any doubt, you may feel free to ask. :)
My Submission
Can someone Explain the idea behind E ??
Thank you so much for your enlightening words about the idea behind reducing complexity. I didn't come up with the bitwise approach, but hope that I could keep this in mind next time.
my code for E : https://atcoder.jp/contests/abc261/submissions/33479324
it gets 8 ac and 14 wa , pls someone help me
Can the $$$O(n^2)$$$ dp solution for D be optimized?
[]
That's $$$\displaystyle \sum_{i=1}^N \sum_{j=0}^{i+1}1 = \sum_{i=1}^N(i+2) = \frac{N(N+1)}{2}+ 2N$$$ iterations, which is $$$O(N^2)$$$.
I guess I gotta learn TC estimations a bit more, thanks :)
However on this occasion would you mind to explain me when can we say that something is logN besides binary search?
I won't explain the big O notation. There are many resources where you can learn about it.
However $$$\log N$$$ time appears quite frequently, too frequently to give a good picture. I'll just mention the harmonic series, which is why I thought you got confused at first. If we have a first loop $$$i=1,\dots, N$$$ and a second one $$$j=1,i,2i\dots (j\leq N)$$$ then you end up with time complexity $$$O(N\log N)$$$ because the number of iterations is roughly $$$\displaystyle \sum_{i = 1} ^ N \left \lfloor \frac{N}{i}\right \rfloor \approx N\sum_{i = 1} ^ N \frac{1}{i} \approx N \log N$$$. There are many more examples.
Yeah that's what I meant, I messed up a question a bit.
Got you, thanks a lot for your time.
Can someone who did F using Segment Tree please explain it? I build 2 seg trees, I to find the of elements < x in a given range in the array. Another segment tree stored the elements grouped by their color. For answering queries, I was doing same as given in editorial. Was getting WA/TLE on most of the test cases.
For D, I tried to simulate the process with recursion like this:
It was wrong and had TLE verdict. Can anyone help me know whether I was on the right track?
TLE can be fixed by caching results(DP) .. WA is because ... solve(i,j) = max(heads + x[i] + c[j+1],solve(i+1,0))