--Someone--'s blog

By --Someone--, history, 5 months ago, ,

Hi

I've just realised that there is no announcement for Atcoder Beginner contests.
Let's discuss problems after the contest here.

• +22

 » 5 months ago, # |   0 is D dp ?
•  » » 5 months ago, # ^ | ← Rev. 2 →   +4 My solution for D: let's take first x elements from left and last y elements from right(x+y <=k and x
•  » » 5 months ago, # ^ | ← Rev. 3 →   +16 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 operationsevery time we have 5 choices :1 — pick element at l (decrease number of operations with 1) and add arr[l] to ans2 — pick element at r (decrease number of operations with 1) and add arr[r] to ans3 — 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 0dp[l][r][x] will be maximum of all this choices.and here's my code : https://atcoder.jp/contests/abc128/submissions/5643132
•  » » » 5 months ago, # ^ | ← Rev. 2 →   0 Upd: removed comment
•  » » » 5 months ago, # ^ |   0 Thanks.. Could you help me solve the difficult version of same problem D.. I am not able to get state transitions..https://www.codechef.com/CW2018/problems/COW18_7
 » 5 months ago, # |   +4 How to solve F?
•  » » 5 months ago, # ^ | ← Rev. 2 →   +19 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
•  » » 5 months ago, # ^ |   +19 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.
 » 5 months ago, # | ← Rev. 3 →   +11 This is my solution that fails at E: https://atcoder.jp/contests/abc128/submissions/5652128What 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 !
•  » » 5 months ago, # ^ |   +6 I used the same idea and got AC. Code
•  » » 5 months ago, # ^ |   +6 I think your idea is right because my idea is same to yours and i got AC.I think your boundary is wrong.
•  » » » 5 months ago, # ^ | ← Rev. 3 →   +3 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
 » 5 months ago, # |   +8 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.
 » 5 months ago, # |   0 Whats about problem B ? use pair ??
 » 5 months ago, # |   +9 I wrote an English editorial (translated from original Japanese one.) https://codeforces.com/blog/entry/67243