chokudai's blog

AtCoder Beginner Contest 216 Announcement
By chokudai, history, 3 years ago, In English

We will hold AtCoder Beginner Contest 216.

The point values will be 100-200-300-400-500-500-600-600.

We are looking forward to your participation!

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

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

Can someone give any corner case for E. Kept getting WA for 4 test cases.

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

    try to check short test cases one by one, for example, n=2, k=1, 3 3, then increase k by one and so on. I found all my bugs in this way

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

    I don't know about your implementation, but I used

    $$$n * ( n+1 ) / 2$$$

    and reduce with n-curK using the same formula. Submission

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

      I was not handling the situation after all elements become equal to a[n-1] properly. I used your method of taking a[n]=0 and it worked. Thank you:)

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

        Oh yeah that was an edge case. Glad I could help

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

E was pretty straighforward lol

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

how to solve F ? no editorial yet

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

    Obviously, the order of the pairs $$$(A,B)$$$ makes no difference to the answer, so first sort the pairs so that $$$A$$$ is monotonously increasing.

    Let $$$f(x)$$$ be the number of the subsets $$$S$$$ that satisfy the condition in the problem statement, and the maximum element in $$$S$$$ is $$$x$$$.

    To calculate $$$f$$$, let $$$g(x,v)$$$ be the number of the subsets $$$S$$$ that the sum of $$$B_i$$$ for $$$i \in S$$$ is not greater than $$$v$$$, and the maximum element in $$$S$$$ is not greater than $$$x$$$.

    Through the definitions of $$$f$$$ and $$$g$$$, we can see that $$$f(x)=g(x,A_x)-g(x-1,A_x)$$$.

    We can do simple DP to calculate $$$g(1,\cdots),g(2,\cdots),\cdots,g(N,\cdots)$$$ in $$$O(N\max\{A\})$$$ time and the answer to this problem is $$$f(1)+f(2)+\cdots+f(N)$$$.

    So we can solve this problem in $$$O(N\log{N}+N\max\{A\})$$$ time.

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

    DP, something like Knapsack

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

what is the intended solution in D? I wrote something terrible:/

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

    The simulation should take care for the position of the balls per color (vector<set>). Additionally we need a set of colors with at least two positions.

    Then remove one removable color after the other, until the set of colors is empty. If that removes all balls then ans=Yes.

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

    I used the topological sorting during the contest.

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

    I did it with graphs. Before removing any ball we have to remove the balls above it. So we can consider that for a ball x, there is a directed edge towards the ball directly above it. If a topological sorting exists then we can remove all the balls. Hence, you just have to find whether there is a cycle in this directed graph

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

      Did with a simple simulation using stacks and a queue. Just pop two same colors on top and then check if the topmost in those stacks have their 2 instances on top. if yes then push them into the queue.

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

      Can you explain how the topo sort ensures that the answer is yes? I am unable to grasp it

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

    thx for the answers, and no one solved it by recursive dp:)(as me)

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

    I use something like BFS. Here's my submission. https://atcoder.jp/contests/abc216/submissions/25437213

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

Why is Bellman-Ford fast enough for G?

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

How to solve G?

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

    A simple greedy algorithm works. Sort the ranges in increasing order by their right endpoint. Then, for each range, while its condition is not satisfied, turn the rightmost zero within the given range into a one. We can implement this approach by using a segtree to determine whether each range's condition is satisfied and a stack maintaining the zeroes to the left of our current endpoint.

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

      Do you have any AtCoder stream planned ? It would be much appreciated.

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

    Another way that works (but I can't prove why it is not $$$O(n^2)$$$) is framing the problem with inequalities. Let $$$B_i = \sum_{j=0}^i A_i$$$, the prefix sum. Then, we have the following inequalities:

    1. $$$B_{R_j} - B_{L_j-1} \geq X_j$$$, for all $$$j$$$

    2. $$$B_i - B_{i-1} \geq 0$$$

    3. $$$B_{i} - B_{i-1} \leq 1$$$

    You can solve a system of linear inequalities with Bellman Ford like here. Submission

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

      I didn't get Bellman Ford to pass, but alternatively you can do Dijkstra instead by grounding your constraints on 0s instead of 1s, i.e.

      • If 1s must satisfy $$$B_{R_j} - B_{L_j - 1} \le X_j$$$, then 0s must satisfy $$$B_{R_j} - B_{L_j - 1} \le R_j - L_j + 1 - X_j$$$

      The other two constraints must be satisfied as well:

      • If there are $$$B_i$$$ 0s, then there's at least that many 0s in $$$B_{i + 1}$$$, i.e. $$$B_i \le B_{i + 1} \Leftrightarrow B_i - B_{i + 1} \le 0$$$

      • There can be at most one extra zero added from $$$B_{i}$$$ to $$$B_{i + 1}$$$, i.e. $$$B_{i + 1} \le B_i + 1 \Leftrightarrow B_{i + 1} - B_i \le 1$$$.

      Constructing a constraint graph (see link provided by Lain) and running Dijkstra (OK as there are no negative edges) leads to its distance array $$$dist$$$ being equal to $$$B$$$ (which is now a prefix sum array on the number of 0s) from which is easy to derive an answer. Also, $$$dist$$$ has the property that $$$B[n] - B[0]$$$ is maximized, and so the number of 0s is as big as possible.

      Apparently this technique is well-known in Japan as 牛ゲー. Also for anyone reading this and wanting to learn more, you can also look up chapter 24.4 in CLRS.

      My submission: https://atcoder.jp/contests/abc216/submissions/25456483

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

Hey all, can anyone help me debug this for Q3(C). I kept getting WA. Thank You !

N = int(sys.stdin.readline().split()[0])

s = ""
while( N > 0):
	if N % 2 == 0:
		s += 'B'
		N /= 2
	else:
		s += 'A'
		N -= 1
print(s[::-1])
→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Don't you know / in Python is float and // is integer?

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

Will there be any editorial for ABC216 in English? I believe there are many people who need it.

P.S. There have been editorials in Japanese already.

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

How to efficiently solve E ? I used priority queue but the method used by me gave TLE as expected. I was thinking of avoiding popping maximum and pushing max-1 to priority queue unless it becomes equal to the 2nd max. but could not implement it.

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

Can anyone check my submisson for F? It gives WA on 10 test cases

https://atcoder.jp/contests/abc216/submissions/25463852

Thanks!

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

How to solve H?

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

When will the editorial come ?

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

Hello, can some help me debug this for question D. I am getting WA for one test case and AC on all the others. Thanks! (I am using the topological sorting algorithm from Wikipedia).

https://atcoder.jp/contests/abc216/submissions/25474361

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

When will be the editorial published ?sugarrr

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

Can anyone tell me how to solve problem C — Many Balls?

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

    Start with N and an empty answer string. Divide by 2 if N is even and add B to the answer string, else if N is odd, add A instead. In the end, reverse the answer string and print it.

    Submission

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

Wow, only now that I notice problem H of this contest is rated 3295 on kenkoooo.com. Idk but that seems quite high for a contest for beginners :v

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

Where could we find editorial for this round, cause they are not available on atcoder

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

    change the language from English to Japanese then you can see the editorial and then use google language translator.

    → Reply