Hi
I've just realised that there is no announcement for Atcoder Beginner contests.
Let's discuss problems after the contest here.
Hi
I've just realised that there is no announcement for Atcoder Beginner contests.
Let's discuss problems after the contest here.
# | User | Rating |
---|---|---|
1 | ecnerwala | 3649 |
2 | Benq | 3581 |
3 | orzdevinwang | 3570 |
4 | Geothermal | 3569 |
4 | cnnfls_csy | 3569 |
6 | tourist | 3565 |
7 | maroonrk | 3531 |
8 | Radewoosh | 3521 |
9 | Um_nik | 3482 |
10 | jiangly | 3468 |
# | User | Contrib. |
---|---|---|
1 | maomao90 | 174 |
2 | awoo | 164 |
3 | adamant | 162 |
4 | TheScrasse | 159 |
5 | nor | 158 |
6 | maroonrk | 156 |
7 | -is-this-fft- | 151 |
8 | SecondThread | 147 |
9 | orz | 146 |
10 | pajenegod | 145 |
Name |
---|
is D dp ?
My solution for D:
let's take first x elements from left and last y elements from right(x+y <=k and x<n-y+1).
we will look at negative elements in increasing order and if we have any operations left we'll put that negative element to it's own place.
my solution was dp and I think It could be solved with another ways but here's my explanation for my solution :
and state is dp[l][r][x] where l is the element we point at it in left , and r the element we point at it in r and x is number of remaining operations
every time we have 5 choices :
1 — pick element at l (decrease number of operations with 1) and add arr[l] to ans
2 — pick element at r (decrease number of operations with 1) and add arr[r] to ans
3 — pick element at l and leave it at end (decrease number of operations by 2)
4 — pick element at r and leave it at end (decrease number of operations by 2)
5 — don't pick or leave anything and answer for this choice is 0
dp[l][r][x] will be maximum of all this choices.
and here's my code : https://atcoder.jp/contests/abc128/submissions/5643132
Upd: removed comment
How to solve F?
Let C=A-B, iterate over all A. For a particular A we need C should divide n-1-A so try all possible divisors. For summing a particular pair A,C we need sum at gaps of C starting at 0 and A. To do fast sums observe C | n-1-A => A mod C = (n-1) mod C so for each C you need to store two cumulative sum vector (having starting position 0 and (n-1) mod C) at gap's of C which can be done in n log n.
Code for details : https://atcoder.jp/contests/abc128/submissions/5648719
For any $$$A$$$ and $$$B$$$ which reach $$$N - 1$$$, there is some $$$k$$$ such that $$$kA - (k - 1)B = N - 1$$$. Since $$$(k - 1)(A - B) < N$$$, we can iterate over all possible choices for $$$A - B$$$ and $$$k$$$ in $$$O(N log N)$$$.
For any choice of $$$A - B$$$ and $$$k$$$, we visit the spots $$$0, A - B, 2(A - B), \dots (k-1)(A - B)$$$ and the spots $$$A, (A-B) + A, 2(A - B) + A, \dots (k-1)(A - B) + A$$$. Since $$$(k-1)(A-B) + A = N - 1$$$, the second list may be rewritten backwards as $$$N - 1, N - 1 - (A - B), N - 1 - 2(A - B), \dots N - 1 - (k - 1)(A - B)$$$.
If we fix $$$A - B$$$ first and iterate over choices of $$$k$$$, the list of visited spots changes only by 2 elements each time we increment $$$k$$$. We can keep a record of visited spots and a total score and update them in constant time.
This is my solution that fails at E: https://atcoder.jp/contests/abc128/submissions/5652128
What I do is to keep a vector $$$(X, \; (S - X, \; T - X - 1))$$$ sorted by X and a set of people. Now for every segment of roadblocks, I delete the people who occur between that segment. Is that idea wrong, or my implementation has a bug ? Thank you !
I used the same idea and got AC. Code
I think your idea is right because my idea is same to yours and i got AC.I think your boundary is wrong.
Yea, the idea is correct. I had an issue with the right iterator, so now instead I move only the left iterator while it is $$$<=T$$$. Shit, another stupid mistake in atcoder contest. But still I really enjoy them. Nice problems !
For anyone who is interested here is the new source code that gets AC: https://atcoder.jp/contests/abc128/submissions/5653871
Here are my solutions to the problems of this contest.
I have noticed that the Beginner Contests have been getting harder over the last 3 contests. This is a good sign as it gives us good challenges to improve. The C problems are no longer solve-at-sight problems and require a few moments of thinking. Although they aren't too hard either. :)
The B was an interesting custom sorting question. The C was an interesting bitmask question. I solved D by fixing the prefix and suffix and then putting the deleted elements into a Priority Queue and then putting the smallest elements back into the array as long as the smallest elements are negative.
Whats about problem B ?
use pair ??
I wrote an English editorial (translated from original Japanese one.) https://codeforces.com/blog/entry/67243