I just did my first ABC in a while, so I decided to write up and share my solutions below. Feel free to leave questions in the comments!

There were several questions this round that had the potential to create precision issues; however, the solutions below give approaches that sidestep those errors altogether. Sadly, I think compiling and testing my A prevented me from winning the round :(

# A — Multiplication 1

Just multiply the numbers and print them out. It's not that hard.

Time Complexity: $$$O(1)$$$. Click here for my submission.

# B — Multiplication 2

This turns out not to be quite as easy as the last problem. Multiplying numbers this large is actually a challenge in C++ because the result is likely to be greater than $$$2^{63}$$$, and thus will cause long long overflow. Thus, in C++, we can't just multiply the numbers and check if the result is greater than $$$10^{18}$$$.

One possible approach is to switch to a different language in order to solve this problem. For example, Python integers seem like a natural choice given their ability to handle integers of arbitrary size. Java BigIntegers also seem workable for similar reasons. However, we have to be a little careful here: if you try to multiply all the integers together and then check whether they're greater than $$$10^{18}$$$, you might TLE: you're performing $$$O(N)$$$ multiplications using a number with $$$O(N)$$$ digits, so the time complexity could potentially be at least $$$O(N^2)$$$.

To get around this, we need a slightly smarter approach: multiply the numbers together, and print $$$-1$$$ as soon as our product exceeds $$$10^{18}$$$. Now, the number of digits we're working with is bounded, so this is safe time-wise. Note that you need to separately check if the input contains a $$$0$$$, since that's the only way the product can decrease: for example, on an input of $$$10^{10}$$$, $$$10^{10}$$$, $$$0$$$, you need to check for the $$$0$$$ separately because otherwise you'll stop as soon as you scan the first two numbers and reach a product of $$$10^{20}$$$.

But, what if you don't want to switch languages? It turns out that there's a pretty simple C++ solution. The key idea is that we can easily compute the base-10 logarithm of the answer, using the identity that $$$\log A_1 A_2 A_3 \cdots A_N = \log A_1 + \log A_2 + \log A_3 + \cdots + \log A_N$$$. Then, the product is greater than $$$18$$$ if and only if the logarithm is greater than $$$18$$$.

To avoid precision errors, though, my solution just checks that the logarithm is small enough that we can perform the computation without long long overflow. If the logarithm is smaller than some value slightly greater than $$$18$$$ (say, $$$18.1$$$), we perform the multiplication and print the result if it is less than $$$10^{18}$$$. Note that we also need to handle the $$$0$$$ case separately here because $$$\log 0$$$ is undefined.

Time Complexity: $$$O(N)$$$. Click here for my submission.

# C — Multiplication 3

One could perform the multiplication using doubles, but precision errors are always scary, so let's try a different approach. Let's read $$$A$$$ as a long long and $$$B$$$ as two integers: one representing its integer part and one representing its decimal part. Then, we can write the integer $$$100B$$$ as the sum of $$$100$$$ times $$$B$$$'s integer part plus the two digits representing $$$B$$$'s fractional part. For example, in the first sample, we read $$$1$$$ as $$$B$$$'s integer part and $$$10$$$ as its decimal part, so $$$100B = 110$$$.

Now that we have $$$A$$$ and $$$100B$$$ as integers, we can compute $$$100AB$$$ by taking their product. Then, we can compute the integer part of $$$AB$$$ by dividing this by $$$100$$$, noting that division in C++ drops the fractional part.

Time Complexity: $$$O(1).$$$ Click here for my submission.

# D — Div Game

First, let's factor $$$N$$$ in $$$O(\sqrt{N})$$$ time. This is doable by attempting trial divisions by all numbers up to $$$\sqrt{N}$$$. Then, if there's anything left over when all these factors are removed from $$$N$$$, what's left must be $$$N$$$'s last prime factor.

Realize that since each $$$z$$$ we select only affects one prime, we can just process each of $$$N$$$'s prime factors independently, compute the number of times we can apply the given operation to the power of that prime factor, and sum up the results.

So, we now only need to solve the problem for numbers equal to $$$p^k$$$ for some prime $$$p$$$. We first attempt a simple greedy algorithm: divide out $$$p$$$, then $$$p^2$$$, then $$$p^3$$$, and so on, until our input is no longer divisible by the next power of $$$p$$$; let the last power of $$$p$$$ we divided out be $$$p^x$$$. Then, we claim that $$$x$$$ is the maximum number of times we can apply this operation to this number.

First, we see that $$$x+1$$$ is impossible: since $$$p p^2 p^3 \cdots p^x p^{x+1}$$$ does not divide $$$p^k$$$, we know that the smallest $$$x+1$$$ operations are still too large, so we cannot have $$$x+1$$$ or more operations. Then, we see that $$$x$$$ is doable: apply the operations with $$$p$$$, $$$p^2$$$, and so on, up to $$$p^{x-1}$$$, then apply one last operation to whatever is left over. The remaining exponent must be at least $$$p^x$$$ because we know $$$p p^2 p^3 \cdots p^x$$$ divides $$$p^k$$$, so we don't repeat any values of $$$z$$$, so this is a valid series of operations. Thus, we can't do any better than $$$x$$$, but we can definitely achieve $$$x$$$ operations, so $$$x$$$ is our answer for $$$p^k$$$.

We thus compute the value of $$$x$$$ for each $$$p^k$$$ and sum up the results to get our answer. Though there are more efficient ways to compute $$$x$$$, you can just do it naively (by adding $$$1$$$, then $$$2$$$, then $$$3$$$, and so on, until the result exceeds $$$k$$$): $$$N$$$ can't have very many prime factors and none of them can be raised to especially large powers, so the $$$O(\sqrt{N})$$$ factor from factoring $$$N$$$ will dominate.

Time Complexity: $$$O(\sqrt{N}).$$$ Click here for my submission.

# E — Count Median

So that we can just deal with integers, rather than decimals, we redefine the definition of median for even numbers to refer to $$$x_{N/2} + x_{N/2 + 1}$$$. This is essentially twice the given median. We can see that this does not change the number of unique medians in the set because we're essentially doubling every number in the set of medians, which means that two equal medians will still be equal and two different medians will still be different after we double them.

We can easily compute the smallest and largest possible medians: take the medians of the arrays $$$A$$$ and $$$B$$$, respectively. Let these medians be $$$Y$$$ and $$$Z$$$. Then, we make a critical claim: the medians we can achieve are exactly the set of integers between $$$Y$$$ and $$$Z$$$. Thus, our answer is the number of integers from $$$Y$$$ to $$$Z$$$, which is $$$Z-Y+1$$$.

But, of course, we need to prove this claim. Obviously, we can't achieve a non-integer median, nor can we have a median lower than $$$Y$$$ or greater than $$$Z$$$, so there's no way to have any medians that aren't integers from $$$Y$$$ to $$$Z$$$.

Now, we just need to show that every median from $$$Y$$$ to $$$Z$$$ is achievable. Start with an array equal to $$$A$$$, which has median $$$Y$$$. Here's the key observation: whenever we increase an integer in the array by $$$1$$$, the median will either not change or will increase by $$$1$$$. This can be proven by fairly simple casework, but it's also pretty intuitive. Thus, as we increase the integers by $$$1$$$ in some arbitrary order until the array becomes $$$B$$$, our median never skips any integers, so it goes from $$$Y$$$ to $$$Z$$$ and, at some point, touches all the integers in between. This shows that any integer between $$$Y$$$ and $$$Z$$$ is a possible median, as desired.

Now, we can sort the arrays $$$A$$$ and $$$B$$$, compute their medians, and print $$$Z-Y+1$$$ as our answer.

Time Complexity: $$$O(N \log N).$$$ Click here for my submission.

# F — Knapsack for All Subsets

Consider a subset $$$x_1, x_2, x_3, \cdots, x_k$$$ summing to $$$K$$$. Then, notice that there are $$$2^{N-k}$$$ subsets of $$$A$$$ containing this subset, because for each element not in our set of $$$k$$$, we have two options: to include it or exclude it from our subset. So, for each subset containing $$$k$$$ integers, we want to add $$$2^{N-k}$$$ to our answer.

We compute this summation using DP. Let $$$dp[i][j]$$$ be the sum of $$$2^{N-k}$$$ over all subsets of the first $$$i$$$ elements of the array $$$A$$$ that sum to $$$j$$$. Initially, $$$dp[0][0] = 2^N$$$ and $$$dp[0][j] = 0$$$ for all other $$$j$$$, since there is one subset of the first $$$0$$$ elements, which has size $$$0$$$ and sums to $$$0$$$.

Then, to transition, we can either add the next element in the array to our subset or not add it. If we don't add it, the result is simple: we add $$$dp[i][j]$$$ to $$$dp[i+1][j]$$$, effectively skipping this element. Alternatively, though, we can add the array to the subset. However, this adds $$$1$$$ to $$$k$$$, effectively multiplying the sum of $$$2^{N-k}$$$ by one-half, so we add $$$\frac{dp[i][j]}{2}$$$ to $$$dp[i+1][j + A[i]]$$$. Since we're working with modular arithmetic, we can divide by $$$2$$$ by multiplying by the modular inverse of $$$2$$$.

Then, our answer is $$$dp[N][S]$$$. Since we have $$$O(NS)$$$ states and each state has $$$O(1)$$$ transitions, this easily passes in time.

Time Complexity: $$$O(NS).$$$ Click here for my submission.

Auto comment: topic has been updated by Geothermal (previous revision, new revision, compare).E can be solved in

O(N)Probably so, but doing so is unnecessary and the only difference between that and my solution is the runtime for computing the median. (By the way, I'm assuming you're referring to a solution other than the one you submitted--I just looked at your solution and it requires sorting the array, and is thus also $$$O(N \log N)$$$.)

I never said that I submitted

O(N), but using nth_element it is possible.I did nth_element(N/2) and got 1 wa. Any ideas? submission

Had almost forgotten the log-trick (not sure if it qualifies as trick) used in B. Thanks for the reminder.

Another way could be to check

`( cur_product > 10^18 / (arr[i]) )`

there is also additional condition to check whether arr[i] should not be zero before division takes place.

Thanks for this excellent blog!

A better solution to b is

CodeShorter : https://atcoder.jp/contests/abc169/submissions/13887530

I can't seem to understand what is wrong with my solution of B? I checked if zero is there and at every point if the product is greater than 10^18. For overflow, I checked if product/first number is equal to the second number. LInk

A very simple way is here. Just keep multiplying and checking. Instead of doing this

`if(prod*arr[i]>(ll)1e18)`

, do this`if(prod>(ll)1e18/arr[i])`

. That will do the trick! P.S. Check for arr[i]!=0. So better first sort the array and then check for all elements.Thank you, got accepted but I still don't understand the reason behind it. I mean why was my previous solution wrong.

suppose prod is 1e18 , and arr[i] is 1e17. Obviously the product of these two will be larger than the limit of long long. therefore it's better to calculate 1e18/arr[i] and check the condition as it will always lie inside the range. Both expressions are mathematically same, but the latter is better for c++ to execute.

Thanks a lot for this Geothermal

Thanks a lot Geothermal , this blog really helps a lot.

For multiplication 3

for B you can also hold 2 products. One a double and the other a long long. and then before multiplying the long long one confirm that it doesn't exceed 10^18 by too much with the double one

Example

geothermal please help me in D ( I solved exactly as your approach after 3 try )

Now i wanna ask where i m going wrong initially

https://atcoder.jp/contests/abc169/submissions/13850744

I m getting WA ...Please give me some test case where this approach give WA. Thanks

3rd Problem shocked me as I kept on multiplying and using different techniques to truncate the integer part. Just didn't think of precision (idk why) and submitted the right solution in the 9th try..(wth!)

Finally I was able to solve till E and ran out of time to write code for F.

Well, as far as I remember, simple multiplication worked just fine (in long doubles, then cast to long long)...

Idk why everyone had trouble with this...

I got the error when I used Python3 with normal multiplication, some sort of precision error. Then I resubmitted the same thing but using C++ and in the way u hv mentioned. Got AC. Idk the thing y that happened but it's termed as some floating point precision error on google.

Works for every case except the last one(hand_01.txt). :(

CodeGeothermal Did you post this while the round was still going on?

He had it drafted before/during the contest. Published it after. See history

I see. My bad.

Alternative Solution for F without division

CodeIn

F, i take input of the interval as pairs and sorted the vector of pairs ,then find the median of that interval. Then do the necessary arithmetic as pointed out by Geothermal in here. This approrach fails in few test cases. What's wrong with my approach with F? Can anyone point out what am i missing? Link of my submissionanother solution for C is to simply use long double instead of double

bro this is not getting accepted

it is in C++, here is the link https://atcoder.jp/contests/abc169/submissions/13898537

why have u converted ur final answer with (long) and not (long long)

i have submitted exactly same code of urs but it shows wrong submission I don't know why I think they have changed the test casesYour text to link here...

They added an after contest testcase.

I came up with

`O(N^3)`

idea for`F`

but couldn't squeeze it to $$$N^2$$$. I am unable to understand Editorial's idea of $$$F$$$ can someone please bother to explain?The problem is from the initial multiset, you choose a primary submultiset, and then you're counting the number of ways to choose a secondary submultiset of it which sums up to

`s`

.Now let's consider a fixed secondary multiset

`S`

. The possible choice of the primary multiset which could had yielded that set is`2^(N-|S|)`

total. So it's like choosing`2`

for each of the elements not picked and multiplying to the answer. This corresponds to the coefficient of`X^s`

of the polynomial`(2 + X^a_1)...(2 + X^a_n)`

. Calculating the coefficient is easy. Just multiply polynomial one by one, but throw away the terms with degree greater than`s`

. Since such polynomial has`s+1`

terms at max, and multiplying it by`(2 + X^a_i)`

takes`O(S)`

time, so we obtain the`O(NS)`

complexity.If you express this polynomial calculation part with dp, you obtain the exact formula in geo's editorial.

I understood most of what you said, but can you please explain the meaning of

(2 + X^a_i)if you choose the element you will add a_i in the sum, but if you don't it multiplies by 2 your choices of a_i's which makes the sum needed. For eg. let's assume we have 4 elements, and 1st 3rd and 4th make the sum we need. So 2nd element just gives us 2 subsets {a1, a2,a3,a4} and {a1,a3,a4} which add up to the needed sum. (X^a1)(2)(X^a2)(X^a3) = 2X^(sum_needed)

Nicely explained! Thanx

I think I got a beautiful solution for F: the answer is just the coefficient of x^s in polynominal (2 + x^a1)(2 + x^a2)...(2 + x^an) here '^' is for power. we can just ignore higher order coefficient than x^s.

https://atcoder.jp/contests/abc169/submissions/13847100

please ignore unremoved code for problem D, E.

FlowerOfSorrow had posted a detail explanation above, you can see my code if you need.

Can anyone please tell me why this solution is getting a TLE whereas I think it is a straightforward O($$$sqrt(n)$$$) solution that should easily pass given the constraints? https://atcoder.jp/contests/abc169/submissions/13833609

Please read the next comment (the issue is identical).

TL;DR — integer overflow.

Infinite thanks!

Why I'm getting TLE??****It's that your counter variable,

`i`

, is of type`int`

, and since $$$N$$$ can be as large as $$$10^{12}$$$ (if I am not mistaken),`i`

should loop up to $$$10^6$$$. However, $$$10^6 * 10^6$$$ is larger than`INT_MAX`

and so the result overflows. So your loop will never terminate since there is no int value that can equal to or exceed $$$10^{12}$$$.I adjusted your code a bit, changed

`int`

to`long long`

in the initialization of your loop counter and got AC. Also, there's a cool trick that I recommend, just put`#define int long long`

in the beginning of your program. Usually, it's never worse to use long longs instead of ints, and it's very easy to overlook the constraints (especially if it's not obvious what the max value of a particular variable is), so it's like a small mind hack that helps :)thanks mate, helpful suggestion

Can AnyBody please tell how can i reduce the submission time of my solution to the problem F?

https://atcoder.jp/contests/abc169/submissions/13920879

I have seen people getting AC in less than 100ms while mine is giving AC in 1000 ms.

thanks in advance. :-)

For problem D, Maybe this sounds stupid, But can someone please explain why is it optimal to compute for each prime and its powers first, then similarly with next prime and its powers, and so on instead of going from 2 onwards ?

What do you mean by "going from 2 onwards?" (Maybe providing specific example may help.)

Sure. I mean from what i understood from the editorials(which i think is wrong) is that we are doing is something like this if divisible by 2, keep dividing by 2,4,8,.. and so on if divisible by 3, keep dividing by 3,9,27,... and so on after using up all prime factors of N, see the maximum times we were able to divide and that would be the answer. If what I understood is correct , then my question is why are we not going ahead like this 2,3,4,5,8,9,16,25,27... because these numbers are expressible as a power of only one prime number?

I think that is also possible, but how are you going to generate that increasing sequence? I think the only way to do so is to generate all the primes first, then generate the powers of them, and finally sorting them. If so I think it's better to just directly try dividing the N itself.

I tried using sieve of eratosthenes for this. I took all primes upto 10^6; Then inserted the primes and its all powers upto 10^12 into a vector. I sorted it and started dividing.

Moreover can you please elaborate on what editorial is trying to say and how is it working. I would really appreciate your help.I am unable to fully understand the approach used in the editorial.

OK. Let's break it down: * Firstly, do you understand that your approach is almost correct, except that you also have to check if $$$N$$$ is a prime that is larger than $$$10^6$$$? * Secondly, at what point don't you understand of the editorial? And just for sure, which editorial are you talking about, the PDF on the AtCoder website or this blog post?

I am kinda talking about both of them.

But you could explain me about the approach used in either of the two editorials.

As far as primes greater than 10^6 are concerned, I had kept a check for that. If my N is not divisible by any number from the sequence, then it is obviously prime itself and ans would be 1 else ans is the one that I calculated. If it matters, Here is my submission Just simply tell me what my approach should have been in solving the problem and why?

Sorry for bothering you so much.

Seems that I found your error<- it's not an errorSorry, but I didn't understand where the error is.

You wanted to iterate all the prime up to $$$10^6$$$, but due to the condition of the for loop, the i reaches at most $$$10^3$$$.

But that's Sieve of eratosthenes to calculate primes upto 10^6 so we are supposed to go upto 10^3 only. thats's the procedure

I'm very sorry, I guess I was fool. Now I'm thinking why it doesn't work. Hold on a sec...

And here is the real mistake: when you check for the prime larger than $$$10^6$$$, note that it is not when given $$$N$$$ is the given prime itself.

For example, when you are given $$$N = 2 \times 1\,000\,003$$$, both of which are prime, your program will not check for 1000003 because it was once could divided by 2 and flag is true. This is wrong (I hope :P)

And here is a paraphrase of those two editorials. I wrote step-by-step, so if you don't understand, tell me which specific step don't you understand.

What is Ep in point 4?

It is a set defined by $$$\lbrace e_i \mid p_i = p \rbrace$$$. If you are not familiar with this set notation, you can read as "the set of $$$e_i$$$ for all $$$i$$$ such that $$$p_i = p$$$."

In other words, $$$E_p$$$ is the set of exponents of base $$$p$$$ such that contained in the sequence operations.

Can you explain why in point 7, sum of elements in Ep <= e? and why does it matter

Assume that $$$E_p = \lbrace e_1, e_2, \ldots, e_m \rbrace$$$. This means that the sequence of operations include dividing by $$$p^{e_1}$$$, dividing by $$$p^{e_2}$$$, ..., and dividing by $$$p^{e_m}$$$. After each operation, and therefore after all the operations, the $$$N$$$ still must be stayed integer. So, the product $$$p^{e_1} \times p^{e_2} \times \cdots \times p^{e_m}$$$ must divide $$$N$$$. The left hand side is $$$p^{\sum E_p}$$$, and the right hand side contains at most $$$e$$$ $$$p$$$'s. Therefore the inequality should hold.

Thanks a lot man. That is the most in depth analysis of a problem I have ever done . But I finally understood. Thank you for your time and patience.

Not at all. I love teaching what I understand, and breaking difficult logics into small steps. You too faced to the problem sincerely and also were so polite. I'm sure you'll do much better in the future. Keep it up :D

Is the precision issue on c because of older c++ version or we deal such problems in this manner only??

can anyone explain why this code does not work for Problem C

The conversion from b to b1 may not be sufficiently precise. Try

`b1 = b*100 + 0.5`

in order to guarantee that $$$b$$$ will be rounded correctly.but why is this a problem as it is already given in the question that the B is a number with two digits after the decimal point,hence it is always fixed that we are not losing any value for the above solution after multiplying by 100. So why is this so???

Essentially, there's some natural imprecision in the way decimal datatypes are stored in C++ (and in most other languages). C++ stores decimals, like all numbers, in binary, rather than base 10, and in binary, numbers like 0.1, 1.6, and 3.4 are actually repeating decimals. Because of that, when C++ tries to store that kind of number, it will actually store a value that's very close, but slightly higher or slightly lower.

The problem here, though, is that if you get a value slightly lower than, say, 1.01, then when you multiply it by 100, the result will be slightly lower than 101, and will thus get rounded down to 100, giving you an incorrect answer. To deal with this, we add some value (I used 0.5, but it could be much smaller and still work) to ensure that our result will be larger than 101, rather than smaller.

thanks so much its deep but i understood

very nice explanations and that to with proofs.

it would be great if you provide such editorials for further rounds Geothermal

yes nice work

Excellent Editorials!

Here is my code for B-Multiplication, two of the test cases aren't giving AC, could not identify the bug. Can anyone help me?

I saw a solution of ashishgup, here at line 30 I could not figure out, why a comparison with 1e18 + 5 is done, instead of 1e18?

Geothermal thanks for the nice solution to problem $$$F$$$, but there's a small typo.

In the second last line of the third para, it should be $$$dp[i+1][j+A[i]]$$$. There should be $$$A[i]$$$ instead of $$$A[j]$$$.

Fixed, thanks!