### chokudai's blog

By chokudai, history, 2 months ago, 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! Comments (59)
 » Good luck to everybody!
 » Can someone give any corner case for E. Kept getting WA for 4 test cases.
•  » » 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
•  » » I don't know about your implementation, but I used $n * ( n+1 ) / 2$and reduce with n-curK using the same formula. Submission
•  » » » 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:)
•  » » » » Oh yeah that was an edge case. Glad I could help
•  » » I am getting TLE!!
 » E was pretty straighforward lol
 » how to solve F ? no editorial yet
•  » » 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 →   xtzic can you explain more why the order doesn't matter?
•  » » » » sorry i thought you meant the order of A and B separately
•  » »
 » what is the intended solution in D? I wrote something terrible:/
•  » » 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.
•  » » The simulation should take care for the position of the balls per color (vector). 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.
•  » » » Can you share your solution?
•  » » » » If you still need here is mine. Just store which colors you have already seen and then when you see it for the second time, you can remove both balls. Then check if the total number of balls you have removed is 2*n https://atcoder.jp/contests/abc216/submissions/25424905
•  » » » » » Figured it out, thank you so much!
•  » » I used the topological sorting during the contest.
•  » » 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 →   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.
•  » » » Can you explain how the topo sort ensures that the answer is yes? I am unable to grasp it
•  » » thx for the answers, and no one solved it by recursive dp:)(as me)
•  » » I use something like BFS. Here's my submission. https://atcoder.jp/contests/abc216/submissions/25437213
 » Why is Bellman-Ford fast enough for G?
 » How to solve G?
•  » » 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.
•  » » » Do you have any AtCoder stream planned ? It would be much appreciated.
•  » » 2 months ago, # ^ | ← Rev. 2 →   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: $B_{R_j} - B_{L_j-1} \geq X_j$, for all $j$ $B_i - B_{i-1} \geq 0$ $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 →   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$ 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
•  » » » » Good one.Also, Guess My Age — Codechef is one problem that asks to solve these types of inequalities using bellman ford.
 » Hey all, can anyone help me debug this for Q3(C). I kept getting WA. Thank You ! N = int(sys.stdin.readline().split()) s = "" while( N > 0): if N % 2 == 0: s += 'B' N /= 2 else: s += 'A' N -= 1 print(s[::-1]) 
•  » » Don't you know / in Python is float and // is integer?
 » 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.
 » 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, # ^ | ← Rev. 2 →   This approach will give TLE because K can be O(e9); your loop will run O(e9) times; use binary search MY SUBMISSION
•  » » » Thanks!
 » Can anyone check my submisson for F? It gives WA on 10 test caseshttps://atcoder.jp/contests/abc216/submissions/25463852Thanks!
•  » » Instead of if (diff > 0) , use if (diff >= 0).Accepted solution: link
•  » » » Thanks!
 » How to solve H?
 » When will the editorial come ?
 » 2 months ago, # | ← Rev. 2 →   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
 » When will be the editorial published ?sugarrr
•  » » I'm sorry, but the English editorial will be completed later. If you want to read editorial immediately, please read the Japanese version by using translation software.
•  » » » Can you link the Japanese Editorial here? This isn't available on Atcoder yet, or at least I can't see 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
 » Can anyone tell me how to solve problem C — Many Balls?
•  » » 2 months ago, # ^ | ← Rev. 2 →   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
•  » » » thanks
 » 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
 » Where could we find editorial for this round, cause they are not available on atcoder
•  » » change the language from English to Japanese then you can see the editorial and then use google language translator.
•  » » » Thank you so much, this was really very helpful