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 | tourist | 3557 |

2 | Radewoosh | 3468 |

3 | Um_nik | 3429 |

4 | Petr | 3354 |

5 | Benq | 3286 |

6 | mnbvmar | 3280 |

7 | wxhtxdy | 3276 |

7 | LHiC | 3276 |

9 | ecnerwala | 3214 |

10 | yutaka1999 | 3190 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 191 |

2 | Radewoosh | 180 |

3 | tourist | 173 |

4 | Vovuh | 165 |

4 | antontrygubO_o | 165 |

6 | PikMike | 164 |

7 | rng_58 | 160 |

8 | Um_nik | 156 |

8 | majk | 156 |

10 | 300iq | 154 |

Hi

I've just realised that there is no announcement for Atcoder Beginner contests.

Let's discuss problems after the contest here.

↑

↓

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/20/2019 02:59:57 (h2).

Desktop version, switch to mobile version.

Supported by

User lists

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

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

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