### 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!

• +86

 » 2 months ago, # |   0 Good luck to everybody!
 » 2 months ago, # |   0 Can someone give any corner case for E. Kept getting WA for 4 test cases.
•  » » 2 months ago, # ^ |   +3 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, # ^ |   +3 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, # ^ |   0 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, # ^ |   +3 Oh yeah that was an edge case. Glad I could help
•  » » 2 months ago, # ^ |   0 I am getting TLE!!
 » 2 months ago, # |   +8 E was pretty straighforward lol
 » 2 months ago, # |   +5 how to solve F ? no editorial yet
•  » » 2 months ago, # ^ |   +1 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 →   0 xtzic can you explain more why the order doesn't matter?
•  » » » » 2 months ago, # ^ |   0 sorry i thought you meant the order of A and B separately
•  » » 2 months ago, # ^ |   0
 » 2 months ago, # |   +1 what is the intended solution in D? I wrote something terrible:/
•  » » 2 months ago, # ^ |   0 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, # ^ |   0 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.
•  » » » 2 months ago, # ^ |   0 Can you share your solution?
•  » » » » 2 months ago, # ^ |   0 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
•  » » » » » 2 months ago, # ^ |   +1 Figured it out, thank you so much!
•  » » 2 months ago, # ^ |   +3 I used the topological sorting during the contest.
•  » » 2 months ago, # ^ |   +4 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 →   0 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, # ^ |   0 Can you explain how the topo sort ensures that the answer is yes? I am unable to grasp it
•  » » 2 months ago, # ^ |   0 thx for the answers, and no one solved it by recursive dp:)(as me)
•  » » 2 months ago, # ^ |   0 I use something like BFS. Here's my submission. https://atcoder.jp/contests/abc216/submissions/25437213
 » 2 months ago, # |   0 Why is Bellman-Ford fast enough for G?
 » 2 months ago, # |   0 How to solve G?
•  » » 2 months ago, # ^ |   +23 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, # ^ |   +10 Do you have any AtCoder stream planned ? It would be much appreciated.
•  » » 2 months ago, # ^ | ← Rev. 2 →   +6 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 →   +19 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, # ^ |   +11 Good one.Also, Guess My Age — Codechef is one problem that asks to solve these types of inequalities using bellman ford.
•  » » » » 4 weeks ago, # ^ |   0 Can you please share your submission?
 » 2 months ago, # |   0 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, # ^ |   0 Don't you know / in Python is float and // is integer?
 » 2 months ago, # |   +1 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, # |   0 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 →   +3 This approach will give TLE because K can be O(e9); your loop will run O(e9) times; use binary search MY SUBMISSION
•  » » » 2 months ago, # ^ |   0 Thanks!
 » 2 months ago, # |   0 Can anyone check my submisson for F? It gives WA on 10 test caseshttps://atcoder.jp/contests/abc216/submissions/25463852Thanks!
•  » » 2 months ago, # ^ |   0 Instead of if (diff > 0) , use if (diff >= 0).Accepted solution: link
•  » » » 2 months ago, # ^ |   0 Thanks!
 » 2 months ago, # |   +3 How to solve H?
 » 2 months ago, # |   +10 When will the editorial come ?
 » 2 months ago, # | ← Rev. 2 →   +3 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, # |   0 When will be the editorial published ?sugarrr
•  » » 2 months ago, # ^ |   0 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.
•  » » » 2 months ago, # ^ |   0 Can you link the Japanese Editorial here? This isn't available on Atcoder yet, or at least I can't see it.
•  » » » » 2 months ago, # ^ |   0
 » 2 months ago, # |   0 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
 » 2 months ago, # |   0 Can anyone tell me how to solve problem C — Many Balls?
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 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
•  » » » 2 months ago, # ^ |   0 thanks
 » 2 months ago, # |   0 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
 » 2 months ago, # |   0 Where could we find editorial for this round, cause they are not available on atcoder
•  » » 2 months ago, # ^ |   +3 change the language from English to Japanese then you can see the editorial and then use google language translator.
•  » » » 2 months ago, # ^ |   0 Thank you so much, this was really very helpful
 » 7 weeks ago, # |   0 Please publish english editorial
 » 6 weeks ago, # |   0 Please someone explain how to solve for H ?