chokudai's blog

By chokudai, history, 2 months 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

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Good luck to everybody!

»
2 months 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.

  • »
    »
    2 months 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

  • »
    »
    2 months 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

    • »
      »
      »
      2 months 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:)

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

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

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I am getting TLE!!

»
2 months ago, # |
  Vote: I like it +8 Vote: I do not like it

E was pretty straighforward lol

»
2 months ago, # |
  Vote: I like it +5 Vote: I do not like it

how to solve F ? no editorial yet

  • »
    »
    2 months 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.

    • »
      »
      »
      2 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      xtzic can you explain more why the order doesn't matter?

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        sorry i thought you meant the order of A and B separately

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
»
2 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    D can be simulated as per the problem statement. But we should take care of the case that a cylinder having 2 balls of the same color.

  • »
    »
    2 months 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.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    I used the topological sorting during the contest.

  • »
    »
    2 months 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

    • »
      »
      »
      2 months 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.

    • »
      »
      »
      2 months 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

  • »
    »
    2 months 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)

  • »
    »
    2 months 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

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why is Bellman-Ford fast enough for G?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve G?

  • »
    »
    2 months 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.

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

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

  • »
    »
    2 months 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

    • »
      »
      »
      2 months 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

»
2 months 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])
»
2 months 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.

»
2 months 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.

»
2 months 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!

»
2 months ago, # |
  Vote: I like it +3 Vote: I do not like it

How to solve H?

»
2 months ago, # |
  Vote: I like it +10 Vote: I do not like it

When will the editorial come ?

»
2 months 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

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

When will be the editorial published ?sugarrr

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone please have a look at my solution for problem D and tell me where did I go wrong? I have compared my solution to a correct solution comparing multiple test cases but every one of them gives the same answer on both the solutions. The logic was also a lot similar to the successful submission but I'm not able to spot the error in my code. I have commented the code to explain my logic as well as I can.

My solution link: https://atcoder.jp/contests/abc216/submissions/25492717

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    7 weeks 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

»
7 weeks 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

»
7 weeks 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

  • »
    »
    7 weeks 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.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Please publish english editorial

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Please someone explain how to solve for H ?