wish ,i had visited this comment before the contest ended ...

Binary search (from -1e18 to 1e18). Then, once you set the guess for K, do another binary search to find out how many pairs are less than the guess.

Final runtime: O(N * (logN)^2)

It must be:

We can do E without using BigInt too.

E doesn't need BigInt. In fact, I recommend you solve the problem by turning the String into an array of integers, then doing an O(N) sweep from right to left).

I didn't find the bug but I have some suggestions.

• You don't need long doubles. If a is a integer, a <= x is the same as a <= floor(x) and a >= x is the same as a >= ceil(x). You just have to be careful with negative values.
• I found it easier to compute 2*(the number of pairs) and then divide it by 2 instead of just compute it directly.
• I didn't understand why you count the number pairs with equal and smaller products in two different variables and use them differently. Shouldn't you always use their sum?

I coded the same solution. https://atcoder.jp/contests/abc155/submissions/10145988

The solution for E is greedy.

Technically you could use DP, but there is no point. At every state there is only one move you should do.

Hint:"Simulate the subtraction process"

Yes, a simple N*2 digit dp would do

dp[idx][carry] is the minimum number of banknotes we (you and the cashier) used after processing all numbers starting from 0 to idx-1, such that we have carry = 1 or 0

So, we start from the right, and decrease the idx as we go through the number N, the transition will look like this:

dp[idx][carry] = min( dp[idx-1][0] + N[idx] , dp[idx-1][1] + (10 — N[idx]) )

corner case: the first option can't be done when N[idx]==9 and carry==1

in the base case we should return carry value

submission: https://atcoder.jp/contests/abc155/submissions/10167311

Binary search from -1e18 to +1e18. Then you take a guess of k and perform binary search for the number of numbers below that number. I would say this question was harder than E. ;_;

Same here

use this insteadgoole canlendar link

I suggest you use clist

Try 5.

Sort the A_i, so every operation concerns a subsegment of indices. Let D_i be the xor between B_i and B_{i-1}, where we consider that B_0 = 0. Our objective is to make D[] = 0. Notice that now every operation amounts to flipping the state of at most two elements of D.

Build a graph on 1..n where indices i and j have an edge between them if an operation affects both. Notice that if we have a simple cycle x_1, x_2, ..., x_k then flipping the edge from x_1 to x_k has the same effect as flipping the other k-1 edges, so it's enough to take a spanning tree of each component. Now we can root each tree arbitrarily and greedily go from leaf to root, doing the correct operations to do everything except possibly the root equal to 0. If at the end the root is 0 we have to flip a single element in the tree in order to fix it. If no operation does that then it is impossible.

maybe the majority of the problem writers are japanese

In the case 955 I believe the answer is 10(955, 956, 957, 958, 959, 960, 970, 980, 990, 1000, 0) but your code outputs 11.

Count the occurrence of each string then output all those strings which have highest number of occurrences. For counting I used map, and in order to output in lexicographical order I sort them using vector of string.

Here is my solution

Your solution for test '555' gives answer 15 instead of 14 (1000 — 400 — 40 — 5)

Greedy approach does not work for this problem, for example if N=555, your program outputs 15, but you can obtain 14 (1*1000 — 4*100 — 4*10 -5*1) wish comments would auto refresh, so this does not happen when I try to answer someone.

"For International Readers: English editorial will be published in a few days" They're doing a great work, give them some time. Also often you can understand the solution if you copy-paste the editorial into an automatic translator and read that.

You can use google translate