Блог пользователя solvemproblr

Автор solvemproblr, история, 5 лет назад, По-английски

Hi

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

  • Проголосовать: нравится
  • +22
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

is D dp ?

  • »
    »
    5 лет назад, # ^ |
    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<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.

  • »
    »
    5 лет назад, # ^ |
    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 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

»
5 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

How to solve F?

  • »
    »
    5 лет назад, # ^ |
    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 лет назад, # ^ |
      Проголосовать: нравится +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 лет назад, # |
Rev. 3   Проголосовать: нравится +11 Проголосовать: не нравится

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 !

»
5 лет назад, # |
  Проголосовать: нравится +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 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Whats about problem B ?

use pair ??

»
5 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

I wrote an English editorial (translated from original Japanese one.) https://codeforces.com/blog/entry/67243