i will definetly watch

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

I really want to know what the LGMS GMS want to show by participating in Beginner contests! Just weird flex tbh.. Like seriously many of the Indian REDs(or outside of India too) don't even participate in Div.1 coz of fear of losing Red! And flex by solving all in div.3 and beginner contests at atcoder.

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

dp[i][0]=answer for prefix of length i if the expression results false for [0...i].

dp[i][1]=answer for prefix of length i if the expression results true for [0...i].

#include<bits/stdc++.h>
#define fast {ios_base::sync_with_stdio(false);cin.tie(NULL);}
using namespace std;	
typedef long long int ll;

int main(void){
	fast;
	int n,i;
	cin>>n;
	string s[n];
	for(i=0;i<n;i++)
		cin>>s[i];
	ll dp[n+2][2];
	dp[0][0]=1,dp[0][1]=1;
	for(i=0;i<n;i++){
		if(s[i]=="OR"){
			dp[i+1][0]=dp[i][0];
			dp[i+1][1]=dp[i][0]+2*dp[i][1];
		}
		else{
			dp[i+1][0]=2*dp[i][0]+dp[i][1];
			dp[i+1][1]=dp[i][1];		
		}
	}
	cout<<dp[n][1];

}

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

You are using doubles.. You cant skip that by initially multiplying the Limit x by 100 and just evaluating without the division by 100 at each step.

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

I can't believe that this was actually the error, AC now, thank you guys.

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.

Precision errors due to comparing doubles. Instead of dividing by 100, multiply the test condition by 100 and use integers.

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.

Because of precision errors, multiply X by 100 in the beginning to eliminate division.

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

Instead of dividing all V[i]*P[i]/100, multiply x by 100.

I also want to know!!!

instead of dividing by 100 multiply x by 100

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

after 17 wrong submissions on B... well idk im going to sleep good night yall

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

For D you can just use a simple loop:

ll sum = 0;
for (ll i = n - 1; i >= 0; i -= 1)
{
    if (lst[i] == true) // or
    {
        sum += ipow(2, i+1);
    }
}
sum += 1;

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.

I actually learnt the trick used to get AC on B from a previous ABC contest.

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

me too lol didnt notice the n <= 10^4

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.

BhaskarTM vongkh Thank you, guys. Fixed solution, it passed

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

check this sample case

6

6 6 4 4 4 4

correct ans is 24

i used segment tree but time limit again.

I didn't apply anything fancy, just good old Dynamic Programming. We basically need to find the min at every step and the observation is: Minimum(Array[i] -> Array[j]) equals Minimum(Array[i], Minimum(Array[i + 1] -> Array[j]))

import java.io.*;
import java.util.*;

class Main
{
  public static void main(String args[]) throws Exception
  {
    BufferedReader Rb = new BufferedReader(new InputStreamReader(System.in));
    int n = Integer.valueOf(Rb.readLine());
    int array[] = new int[n];
    String temp[] = Rb.readLine().split(" ");
    for(int i = 0; i < n; i++)
    {array[i] = Integer.valueOf(temp[i]);}
    int oranges = 0;
    for(int i = n - 1; i >= 0; i--)
    {
      int last = array[i];
      for(int j = i; j < n; j++)
      {
        last = Math.min(array[j], last);
        int o = last * (j - i + 1);
        if(o > oranges)
        {oranges = o;}
      }
    }
    System.out.println(oranges);
  }
}

We can also solve it using stack largest histogram area

6
6 5 4 3 2 1

Use PyPy unless you have a good reason not to.

After switching from Python3.8.2 to PyPy3.7.0 it passes: exactly the same code using PyPy3.7.0

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


answer ~ 52414818886.700114119797945