Yay, looking forward to watching it.

Going live in a minute!

I also uploaded a screencast (no commentary) to YouTube: https://www.youtube.com/watch?v=SPvZ6R7KeHE

loved it

These explanations are great! The only thing I have to add is that if you want a short editorial instead of a bit longer discussion then you can watch my video

Uploaded to YouTube with timestamps: https://youtu.be/s5gU2oW8hCk

AtCoder Beginner Contest

Atcoder is a competitive programming website just like codeforces. It holds a beginner level contest almost every week named Atcoder Beginner Contest(ABC in short).

One doubt, I used pow(2LL, i) in contest and I regularly got WA even though logic was correct. When I changed it to 1LL << i, I got AC. I can understand the reason behind (1 << i) != (1LL << i) but why does pow() behave in such a way?

Notice that if the points form a "picture", the picture will remain in shape, just rotated and flipped.

You just need to track three points (0,0), (0,1), (1,0) and where they go after each transformation. For each query, extrapolate from the three points.

At any point in time $$$t$$$, every point will be of the form $$$(a_tx+b_t, c_ty+d_t)$$$. Sort all the queries in increasing order of time, and simulate performing the operations, which would only affect the aforementioned coefficients.

Remember operations will do the following:

1. $$$(x,y) \rightarrow (y,-x)$$$
2. $$$(x,y) \rightarrow (-y,x)$$$
3. $$$(x,y) \rightarrow (2p-x,y)$$$
4. $$$(x,y) \rightarrow (x,2p-y)$$$

Here is a somewhat readable implementation of this.

extend point $$$(x, y)^T$$$ to $$$(x, y, 1)^T$$$ and then all 4 operations can be view as linear transformation on space. then we will get m + 1 matrix. and the answer is matrix * $$$(x, y, 1)^T$$$

using DP

dp[a][i]: the number of sequence $$$(x_0, \cdots, x_i)$$$ such that y_i = a. (a = 0, 1)

DP, I think the code is easy to understand.

note that if we traverse array of strings from last index to first index, in any time if we find "OR" then there are 2 cases: 1) it can be "True" in this index of our tuples (where "OR" is) and before it there can be any permutations of "True" and "False", but also here can be "False" and before it it should be "True", so if we continue and find "AND" there should be obviously "True" in our target tuple. So we can deduce that we just need to take care of "ORs" and any time we find it by traversing from last index (or now from first) we will add $$$2^{index}$$$ to our answer and also finally we should add 1 to resulted answer and get final answer (this because another case is that first "OR" index from last can be "False).

Define $$$dp_i$$$ as the answer for the first $$$i$$$ elements. Focus on the last element, if it is $$$AND$$$, then you have no choice for the last element. In other words, you have to se it to True. Hence $$$dp_i = dp_{i - 1}$$$.

On the other hand, if it is $$$OR$$$, then you have 2 choices for the last element. Suppose, you set it to True, then the equation would be true regardless of other values, hence $$$2^i$$$ possibilities. If you set it to False, the previous equation must evaluate to True, hence a reduced version of the problem. Therefore $$$dp_i = dp_{i - 1} + 2^i$$$

Code

Instead of dividing by 100 multiply m by 100 while comparing. It is possibly an precision error.

i also got WA about 30 times!! i have solved A and C !!

Instead of handling float/double multiply $$$x$$$ by $$$100$$$. Now you can freely use long long without any precision issue

I believe that constraint exists because of floating point imprecision. If $$$k$$$ is large enough you could make the $$$x$$$-coefficient very close to $$$1$$$, resulting in either a very large (and imprecise) answer or division by zero.

Instead of dividing (v*p) by 100, multiply drunk by 100. Check this out: https://atcoder.jp/contests/abc189/submissions/19648760

You can also use fractions provided by Python, that way you avoid using floating point arithmetic: https://atcoder.jp/contests/abc189/submissions/19594700

My solution doesn't involve binary search. Code I think there was a constraint on k so that the answer doesn't overflow.

Precision error was the reason. You could have added $$$v*p$$$ and compared it with $$$100*x$$$.

Add $$$v*p$$$ and compare with $$$100*x$$$

Multiply X with 100 , and then just check when sum of (v[i]*p[i]) becomes greater than that

Numbers are too large and decimal comparisons will give an equivalence when they should not, to avoid that, first multiply x by 100 and ignore dividing by 100 each time u read an input and u can just work with integers, this solves the decimals problem, and instead of adding all inputs and comparing to X, subtract from X each input u read and see if X reaches 0

multiply x by 100 instead of dividing p by 100

This might be some killer testcase:

Test 1:

2 1

1 100

1 1 



Test 2:

2 0

1 30

1 70

Best way is to avoid doubles and use modulo for computing.

Since 1/3=0.33333.. in doubles and 2/3=0.66666.. , so if you try to add 1/3 and 2/3 in doubles , it won't result in 1 rather it would be 0.999999...

https://atcoder.jp/contests/abc189/submissions/19627683 link to my submission , just tell if you need explanation

DFS? I'm not sure.

Well, I just solved it using two variables: $$$one$$$ and $$$zero$$$, where $$$one$$$ represents the number of sequences ending at the $$$i-th$$$ index and having the final result as $$$one$$$ or $$$zero$$$ at index $$$i$$$.

Initialize: $$$one=1$$$ and $$$zero=1$$$. Since $$$x_0$$$ can be 0 or 1.

Consider if $$$S[i]==AND$$$:

Initialize: $$$numzero = 0$$$, $$$numone = 0$$$.

If I choose to put $$$x_i$$$ as $$$0$$$, then: $$$numzero = zero + one$$$.

If I choose to put $$$x_i$$$ as $$$1$$$, then: $$$numzero += zero$$$, $$$numone = one$$$

if $$$S[i]==OR$$$:

Initialize: $$$numzero = 0$$$, $$$numone = 0$$$.

If I choose to put $$$x_i$$$ as $$$0$$$, then: $$$numzero = zero, numone=zero$$$.

If I choose to put $$$x_i$$$ as $$$1$$$, then: $$$numone += one$$$

$$$zero=numzero$$$ and $$$one=numone$$$

Hence final answer is $$$one$$$ after processing all the strings

EDIT: https://atcoder.jp/contests/abc189/submissions/19610002

What is possibility?

use long long

if (dp[i][y]) return dp[i][y] This wont return for 0

That's your fault if you cannot handle precision errors. Its a beginner contest and B couldn't be more simple.

Your power function is taking the answer mod 1e9+7, but the question does not ask for that.

Sameeeee. I did it in O(n) but it took quite a time to recall the stuff. It was similar to finding the maximum area of the histogram, which can be solved using stack in linear time. Do have a look at that!

Please share if you have a better solution than O(N^2).

I used transformation matrices.

Consider every every coordinate as a line segment from origin to the given point in the form mx+c and my+c. Then you will notice that only m and c are changing in each transformation. Just store the corresponding values and answer the each query in O(1).

Because you are iterating upto 1e5 in the outer loop

The complexity of your solution is not N^2. It is max(A) * N, which is 10^9. N^2 in this case is only 10 ^ 8.

EDIT: It was actually precision error only. The condition for "impossible" should have been $$$b > 1 - \epsilon$$$ instead of $$$b \geq 1$$$ in the code. Damn.

Nicely explained! Came here after failing to understand the editorial, you made it much easier.

A classical problem — Largest rectangle under histogram

n = 100000 m = 2 k = 10
99972 99975 99978 99981 99984 99987 99990 99993 99996 99999


answer ~ 52414818886.700114119797945