chokudai's blog

AtCoder Beginner Contest 216 Announcement
By chokudai, history, 5 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?
»
5 years ago, hide # |
 
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
  • »
    »
    5 years ago, hide # ^ |
     
    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
  • »
    »
    5 years ago, hide # ^ |
     
    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
»
5 years ago, hide # |
 
Vote: I like it +8 Vote: I do not like it

E was pretty straighforward lol

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

how to solve F ? no editorial yet

→ Reply
  • »
    »
    5 years ago, hide # ^ |
     
    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
  • »
    »
    5 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    DP, something like Knapsack

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

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

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

Why is Bellman-Ford fast enough for G?

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

How to solve G?

→ Reply
  • »
    »
    5 years ago, hide # ^ |
     
    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
  • »
    »
    5 years ago, hide # ^ |
    ← 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
    • »
      »
      »
      5 years ago, hide # ^ |
      ← 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
»
5 years ago, hide # |
 
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
»
5 years ago, hide # |
 
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
»
5 years ago, hide # |
 
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
»
5 years ago, hide # |
 
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
»
5 years ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

How to solve H?

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

When will the editorial come ?

→ Reply
»
5 years ago, hide # |
← 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
»
5 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

When will be the editorial published ?sugarrr

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

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

→ Reply
»
5 years ago, hide # |
 
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
»
5 years ago, hide # |
 
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
  • »
    »
    5 years ago, hide # ^ |
     
    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