We will hold AtCoder Beginner Contest 189.

- Contest URL: https://atcoder.jp/contests/abc189
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20210123T2100&p1=248
- Duration: 100 minutes
- Number of Tasks: 6
- Writer: kort0n, kyopro_friends, satashun, tatyam
- Rated range: ~ 1999

The point values will be 100-200-300-400-500-600.

We are looking forward to your participation!

I'm planning to stream after (twitch.tv/AnandOza).

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

Before there were any contests on Codeforces, this contest was my only hope. :')

The ABC is the most suitable for me, a green hand.I'm so vegetable.

can someone explain what is meant by abc ? everyone is talking about it , they mean first 3 problems?

AtCoder Beginner Contest

I am a newbie. Do you recommend me to do Atcoder also or should i focus more on codeforces alone?

Well, I think it's good to practice on multiple platforms (at least that's how I practiced in the beginning), especially since contests on CF are unfortunately not so frequent these days.

ok thanks. I will enroll in Atcoder and attend contents from now on.

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).

If you're getting a

WAin`D : Logical Expression`

even with the correct logic, recall that`(1 << i) != (1LL << i)`

One doubt, I used

`pow(2LL, i)`

in contest and I regularly gotWAeven 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?pow, powf, powl

Got it, thanks

what does it mean? 1LL

update : googled just now and understood that it is just type conversion to long long

How to solve E ?

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.

Wow, that's great. Can you share your implementation?

Submission, probably some variables could be named better

Hey, I did something similar. Can you tell me whats wrong?

Ah, nice. I represented the transformations as an affine transformation (i.e. a 3x3 matrix), but it was pretty verbose and was too slow in pypy (had to switch to C++).

Here's my PyPy submission doing just that: https://atcoder.jp/contests/abc189/submissions/19729423

Hi! I don't understand clearly why we need only 3 points and can extrapolate any query from the effect of op on these 3 points. Pls can someone help?

Two points which are next to each other stay next to each other. This means if you know where one point is, then you can more or less simply find where other points are.

You know how far away they are, and just need to find in which direction after all the operations. These directions can be derived from only three points.

But I still don't understand that specific three points.. why do we need to track those "specific" points: (0, 0), (0, 1), and (1, 0)? Why not two points (1, 0) and (0, 1)? Or maybe (-2,1) and (1,0)? Why "three" points, and why "those (including (0,0)" three points? My understanding is as follows: for the 2d plane, we have (1, 0) and (0, 1) as a basis, so we can express any linear transformation in those two basis vectors. But suddenly (0, 0) comes in and I got lost :(

Operations 3 and 4 are not linear transforms (they do not map 0 to 0, in general).

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:

Here is a somewhat readable implementation of this.

I figured out the four transitions but was unable to keep track of the coefficients as multiplication and sum were coalesced together. Can you write a bit more on how one would go about implementing it?

Well it's in my implementation, but maybe it's not readable. Let $$$xpol = (a_t,b_t)$$$ and $$$ypol = (c_t,d_t)$$$. So, we do the following:

Just keep a boolean to keep track of whether $$$x$$$ and $$$y$$$ should be swapped or not.

Did same like this, just instead of sorting the queries. I saved the values of at,bt,ct,dt and swap variable in vector with position corresponding to that time. Solution

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

How to solve D?

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

I kept getting wrong answer at 5 of the test cases on problem B which is kinda weird because it was an easy one, can someone please tell me what's wrong with that code? (https://ideone.com/wG8KxG)

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

But why is this error? is there ny problem with the compiler?

check language precision errors

In problem F, the Constraints $$$0 \leq k \leq 10$$$ can be remove~

submissions: 19630680

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.

B — Alcoholic

https://atcoder.jp/contests/abc189/tasks/abc189_b

This is one of the question in the contest, fairly easy one but I am not sure why I got wrong answer for some test cases. can someone help me with it.(Attached the question link and my python code)

My Python Code:

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

Thank you So Must, I did not even have an idea test case may fail due to precision error also. I will remember this point in all my upcoming contest.

## Learning: Always Try converting the logic from division to Multiplication to avoid floating point errors

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

Was binary search on answer the intended solution for F(as this works without the constraint on k)?

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

What was the problem at problem B? I'm using c++ and I declared the variables as floats and it wouldn't work. Can someone please explain why?

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

ok please tell me what is the mystery to get all AC on B

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:

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

How to solve D without DP?

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

YES.PLEASE EXPLAIN IN A BRIEF IF U CAN.

Notice that the last AND's in the array need to be True to get True as the output so you cant just ignore them, But if all of the strings are AND then you need to add 1 as they will yield 1 if all are true. If the last strings are OR'S then you need to have one true in them to get ans as true , and the remaning no. will be true so you will add (1<<(no.of or's ) -1)*(1<<(no. of string remaining)). continue this until i becomes -1. If all the strings are OR than you need to add (1<<(no. of or's+1))-1, (-1 is for removing the permutation where all no. are false)

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 stringsEDIT: https://atcoder.jp/contests/abc189/submissions/19610002

How to solve F?

I am bad at possiblility, I even felt exhaust reading the problem statment.

Help!

What is possibility?

It means a sort of problems which calculating possiblity is needed.

Problem D: Whats wrong with this DP ?

spoileruse long long

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

Problems like B make me quit CP. such a shit problem, learned nothing and wasted my time. Don't know it was a beginner contest or what. Absolutely frustrated.

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

Cleared 22 out of 23 tests in D(C++). Applied same logic in Python after contest but only got 8 correct. What's more interesting is Python code cleared the test case on which I was getting WA in C++.

Here are links:

C++ code: https://atcoder.jp/contests/abc189/submissions/19639089

Python Code: https://atcoder.jp/contests/abc189/submissions/19647081

Can somebody please tell me my mistake.

Logic Used: Grouped consecutive And's and Or's Number of ways to get 1 from 1 through n Or's = pow(2,n) Number of ways to get 1 from 0 through n Or's = pow(2,n)-1 Number of ways to get 0 from 1 through n Or's = 0 Number of ways to get 0 from 0 through n Or's = 1 Similarly did for And Gate.

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

I know, thats why I increased the value of mod to 1e8 but still got the same result. https://atcoder.jp/contests/abc189/submissions/19639952

$$$1e18$$$ does not fit into an

`int`

datatype, so you need to change the line`const int mod = 1e18`

. Although I'm not sure if that'd still pass.Yeah...got it. Thanks.

The maximum answer is $$$2^{60}-1=1.15e18$$$ so you would need to set a slightly higher mod, or get rid of the mod.

I did not even think that O(N^2) is an accepted solution for problem C. I wasted my time implement a O(max(A)logn)solution... Hmmm, what a bad day!

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!

Was O(N^2) accepted? I did using combination of sparsh tables and binary search. O(nlog(n)) Solution

Your submission link please.

Here is my submission.

I guess you would know Hindi. If you do, I watched this video on youtube for the maximum area of the histogram.

My code resembles a lot with the one in the video; do watch it to understand my code much better. Happy coding :)

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

check this out, https://www.geeksforgeeks.org/largest-rectangle-under-histogram/

Search for the classical "max area histogram" problem. This was just a direct spinoff of that problem.

Can someone tell me how to solve E

I used transformation matrices.

Can you link your code and the article for transformation matrices which contains Code in C++ as well

My submission: https://atcoder.jp/contests/abc189/submissions/19628802

Implementation in C++ shouldn't be too hard as the only thing you do is multiply matrices (it's my

`multiply`

function).Ok thanks

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).

Ok , can you link your submission , and Thanks in Advanced

I think my solution uses the same idea, so you can see mine:Solution

Thanks Man it helped

Can you explain to me please why my N ^ 2 solution not passed?

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.

Can someone help me in identifying why the following approach to problem F is wrong? I think that there are some precision issues maybe.

My approach was somewhat elementary. I supposed let the expected number of turns in the game be $$$x$$$. Now, denote by $$$Expected[i]$$$ the expected number of turns in the game if we were to start at cell $$$i$$$. Then we can determine $$$Expected[i]$$$ for $$$i = 0 \ldots n+m$$$ by the following recurrence.

We can solve the recurrence by maintaining a running sum in $$$O(n+m)$$$ time. So suppose after solving this recurrence we get $$$Expected[0] = a + bx$$$ but by assumption we have $$$Expected[0] = x$$$ so we have $$$x = a/(1-b)$$$ as the answer to the problem.

My code is getting WA on 3 test cases for some reason. https://atcoder.jp/contests/abc189/submissions/19648029

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.

can anybody suggest a solution of o(n) or o(nlog(n)) for the c problem(if it exist)?

A classical problem — Largest rectangle under histogram

If somebody's interested in video solutions (A to E) and screencast for this contest: https://www.youtube.com/watch?v=jJw0BFDOHAE

From the editorial for F: $$$f(0)$$$ can be up to $$$N * 4^K / 2$$$

Can someone explain this bound?

A slightly different approach to C (apologies if someone has already said this — couldn't find it in the editorial or other comments).

You can solve it using DSU. Iterate over K from the maximum value of Ai to the minimum with an array of booleans Bi, setting Bi = True when Ai >= K. Each time two neighbouring elements are both True, join their sets in the DSU, and maintain a max_size variable which represents the longest contiguous subsequence of elements >= K. At each possible value of K, update ans = max(ans,K*max_size).

Solution here: https://paste2.org/kAZGNWJU