solvemproblr's blog

AtCoder Beginner Contest 128
By solvemproblr, history, 6 years ago, In English

Hi

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

  • Vote: I like it
  • +22
  • Vote: I do not like it

Comments Comments (14)
| Write comment?
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

is D dp ?

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it +4 Vote: I do not like it

    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.

    → Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 3   Vote: I like it +16 Vote: I do not like it

    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

    → Reply
»
6 years ago, # |
  Vote: I like it +4 Vote: I do not like it

How to solve F?

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it +19 Vote: I do not like it

    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

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    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.

    → Reply
»
6 years ago, # |
← Rev. 3   Vote: I like it +11 Vote: I do not like it

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 !

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    I used the same idea and got AC. Code

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    I think your idea is right because my idea is same to yours and i got AC.I think your boundary is wrong.

    → Reply
»
6 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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.

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Whats about problem B ?

use pair ??

→ Reply
»
6 years ago, # |
  Vote: I like it +9 Vote: I do not like it

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

→ Reply