Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

### chokudai's blog

By chokudai, history, 20 months ago,

We will hold AtCoder Beginner Contest 189.

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

We are looking forward to your participation!

• +59

 » 20 months ago, # |   +49 I'm planning to stream after (twitch.tv/AnandOza).
•  » » 20 months ago, # ^ |   -15 i will definetly watch
•  » » 20 months ago, # ^ | ← Rev. 2 →   +2 Yay, looking forward to watching it.
•  » » 20 months ago, # ^ |   +24 Going live in a minute!I also uploaded a screencast (no commentary) to YouTube: https://www.youtube.com/watch?v=SPvZ6R7KeHE
•  » » 20 months ago, # ^ |   +5 loved it
•  » » 20 months ago, # ^ |   +9 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
•  » » 20 months ago, # ^ |   0 Uploaded to YouTube with timestamps: https://youtu.be/s5gU2oW8hCk
•  » » 19 months ago, # ^ |   -49 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.
 » 20 months ago, # |   +2 Before there were any contests on Codeforces, this contest was my only hope. :')
 » 20 months ago, # | ← Rev. 2 →   +16 The ABC is the most suitable for me, a green hand.I'm so vegetable.
 » 20 months ago, # |   0 Best of Luck to Everyone !!
 » 20 months ago, # |   0 the abc is difficult for me because i am not able to understand the problems.my english is very poor.I used some translation software,but little effect.
 » 20 months ago, # | ← Rev. 2 →   +2 can someone explain what is meant by abc ? everyone is talking about it , they mean first 3 problems?
•  » » 20 months ago, # ^ |   +7 AtCoder Beginner Contest
•  » » » 20 months ago, # ^ |   0 Thanks
•  » » » 20 months ago, # ^ |   0 I am a newbie. Do you recommend me to do Atcoder also or should i focus more on codeforces alone?
•  » » » » 20 months ago, # ^ |   0 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.
•  » » » » » 20 months ago, # ^ |   0 ok thanks. I will enroll in Atcoder and attend contents from now on.
•  » » 20 months ago, # ^ |   +1 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).
•  » » » 20 months ago, # ^ |   0 Yea i know but i didn't realize it's atcoder beginner contest thanks <3
 » 20 months ago, # |   +11 If you're getting a WA in D : Logical Expression even with the correct logic, recall that(1 << i) != (1LL << i)
•  » » 20 months ago, # ^ |   0 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?
•  » » » 20 months ago, # ^ |   0
•  » » » » 20 months ago, # ^ |   0 Got it, thanks
•  » » » 19 months ago, # ^ | ← Rev. 2 →   0 what does it mean? 1LLupdate : googled just now and understood that it is just type conversion to long long
 » 20 months ago, # |   +16 How to solve E ?
•  » » 20 months ago, # ^ |   +15 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.
•  » » » 20 months ago, # ^ |   0 Wow, that's great. Can you share your implementation?
•  » » » » 20 months ago, # ^ |   0 Submission, probably some variables could be named better
•  » » » » » 20 months ago, # ^ |   0 Hey, I did something similar. Can you tell me whats wrong?
•  » » » 20 months ago, # ^ |   +8 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++).
•  » » » » 20 months ago, # ^ |   0 Here's my PyPy submission doing just that: https://atcoder.jp/contests/abc189/submissions/19729423
•  » » » 20 months ago, # ^ |   0 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?
•  » » » » 20 months ago, # ^ |   0 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.
•  » » » » » 20 months ago, # ^ |   0 understand the intuition better now, thanks! :)
•  » » » 20 months ago, # ^ |   0 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 :(
•  » » » » 20 months ago, # ^ |   0 Operations 3 and 4 are not linear transforms (they do not map 0 to 0, in general).
•  » » 20 months ago, # ^ | ← Rev. 2 →   +8 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: $(x,y) \rightarrow (y,-x)$ $(x,y) \rightarrow (-y,x)$ $(x,y) \rightarrow (2p-x,y)$ $(x,y) \rightarrow (x,2p-y)$ Here is a somewhat readable implementation of this.
•  » » » 20 months ago, # ^ |   0 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?
•  » » » » 20 months ago, # ^ |   0 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: Multiply $xpol$ by -1, exchange $ypol$ and $xpol$. Also swap the actual values of $x$ and $y$. Multiply $ypol$ by -1, exchange $ypol$ and $xpol$. Also swap the actual values of $x$ and $y$. $(a_t,b_t) \rightarrow (-a_t, 2p-b_t)$ $(c_t,d_t) \rightarrow (-c_t, 2p-d_t)$ Just keep a boolean to keep track of whether $x$ and $y$ should be swapped or not.
•  » » » 20 months ago, # ^ |   +3 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
•  » » 20 months ago, # ^ |   0 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$
 » 20 months ago, # |   0 How to solve D?
•  » » 20 months ago, # ^ |   +6 using DPdp[a][i]: the number of sequence $(x_0, \cdots, x_i)$ such that y_i = a. (a = 0, 1)
•  » » 20 months ago, # ^ |   0 DP, I think the code is easy to understand.
•  » » 20 months ago, # ^ | ← Rev. 3 →   +3 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).
•  » » 20 months ago, # ^ | ← Rev. 4 →   +1 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
•  » » 20 months ago, # ^ |   0 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]. Code#include #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>s[i]; ll dp[n+2][2]; dp[0][0]=1,dp[0][1]=1; for(i=0;i
 » 20 months ago, # |   +1 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)
•  » » 20 months ago, # ^ |   +10 Instead of dividing by 100 multiply m by 100 while comparing. It is possibly an precision error.
•  » » 20 months ago, # ^ |   +2 i also got WA about 30 times!! i have solved A and C !!
•  » » 20 months ago, # ^ |   0 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.
•  » » 20 months ago, # ^ |   0 Instead of handling float/double multiply $x$ by $100$. Now you can freely use long long without any precision issue
•  » » » 20 months ago, # ^ |   0 But why is this error? is there ny problem with the compiler?
•  » » » » 20 months ago, # ^ |   0 check language precision errors
•  » » » » 20 months ago, # ^ |   0 Precision Error. Click
•  » » 20 months ago, # ^ |   0 I can't believe that this was actually the error, AC now, thank you guys.
 » 20 months ago, # |   +8 In problem F, the Constraints $0 \leq k \leq 10$ can be remove~submissions: 19630680
•  » » 20 months ago, # ^ | ← Rev. 3 →   +8 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.
 » 20 months ago, # | ← Rev. 4 →   -18 B — Alcoholichttps://atcoder.jp/contests/abc189/tasks/abc189_bThis 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: n,drunk=list(map(int,input().split())) curDrunk=0 for i in range(1,n+1): v,p=list(map(int,input().split())) curDrunk+=(v*(p/100)) if drunk
•  » » 20 months ago, # ^ |   0 Precision errors due to comparing doubles. Instead of dividing by 100, multiply the test condition by 100 and use integers.
•  » » » 20 months ago, # ^ |   0 Thank You
•  » » 20 months ago, # ^ |   0 Instead of dividing (v*p) by 100, multiply drunk by 100. Check this out: https://atcoder.jp/contests/abc189/submissions/19648760
• »
»
»
20 months ago, # ^ |
Rev. 2   +4

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

•  » » 20 months ago, # ^ | ← Rev. 2 →   0 You can also use fractions provided by Python, that way you avoid using floating point arithmetic: https://atcoder.jp/contests/abc189/submissions/19594700
 » 20 months ago, # |   0 Was binary search on answer the intended solution for F(as this works without the constraint on k)?
•  » » 20 months ago, # ^ | ← Rev. 2 →   0 My solution doesn't involve binary search. Code I think there was a constraint on k so that the answer doesn't overflow.
 » 20 months ago, # |   0 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?
•  » » 20 months ago, # ^ | ← Rev. 2 →   0 Because of precision errors, multiply X by 100 in the beginning to eliminate division.
•  » » 20 months ago, # ^ |   0 Precision error was the reason. You could have added $v*p$ and compared it with $100*x$.
•  » » 20 months ago, # ^ |   0 Instead of dividing all V[i]*P[i]/100, multiply x by 100.
 » 20 months ago, # |   0 ok please tell me what is the mystery to get all AC on B
•  » » 20 months ago, # ^ |   0 I also want to know!!!
•  » » 20 months ago, # ^ | ← Rev. 2 →   0 instead of dividing by 100 multiply x by 100
•  » » » 20 months ago, # ^ |   0 Thank you. I see
•  » » 20 months ago, # ^ |   +3 Add $v*p$ and compare with $100*x$
•  » » 20 months ago, # ^ |   0 Multiply X with 100 , and then just check when sum of (v[i]*p[i]) becomes greater than that
•  » » 20 months ago, # ^ | ← Rev. 2 →   +1 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
•  » » 20 months ago, # ^ |   +3 multiply x by 100 instead of dividing p by 100
•  » » 20 months ago, # ^ |   0 after 17 wrong submissions on B... well idk im going to sleep good night yall
•  » » » 20 months ago, # ^ | ← Rev. 3 →   0 Lol. Happened to me as well (9 unsuccessful submissions). Seems to be an issue with floating point variables. My submission was accepted when I changed double to long and chose not to divide by 100. Eg: V1 = 10 P1 = 20% Then instead of calculating V1 * P1 / 100, I calculated V1 * P1. I also multiplied the Alcohol_Limit variable by 100 to cancel everything out when initializing it.
•  » » 20 months ago, # ^ |   +1 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...
 » 20 months ago, # |   0 How to solve D without DP?
•  » » 20 months ago, # ^ |   0 https://atcoder.jp/contests/abc189/submissions/19627683 link to my submission , just tell if you need explanation
•  » » » 20 months ago, # ^ |   0 YES.PLEASE EXPLAIN IN A BRIEF IF U CAN.
•  » » » » 20 months ago, # ^ |   0 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)
•  » » » » 20 months ago, # ^ |   0 A simpler variation (subjective!) based on what dhruv7888 said... Iterate from the last operator to the first, and if the current operator is OR, add pow(2, numbers_before_operator) to a total variable (make it long, not double/float). If the current operator is AND, do nothing. numbers_before_operator == operators before operator + 1 After exiting the loop, print total + 1, as we never processed the first element inside the loop. Link to my submission: https://atcoder.jp/contests/abc189/submissions/19655914 P.S: The Program is in Java.
•  » » 20 months ago, # ^ |   0 DFS? I'm not sure.
•  » » 20 months ago, # ^ | ← Rev. 2 →   0 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
•  » » 20 months ago, # ^ | ← Rev. 3 →   0 For D you can just use a simple loop: Spoilerll sum = 0; for (ll i = n - 1; i >= 0; i -= 1) { if (lst[i] == true) // or { sum += ipow(2, i+1); } } sum += 1;
 » 20 months ago, # |   0 How to solve F? I am bad at possiblility, I even felt exhaust reading the problem statment.Help!
•  » » 20 months ago, # ^ |   +13 What is possibility?
•  » » » 20 months ago, # ^ |   0 It means a sort of problems which calculating possiblity is needed.
 » 20 months ago, # |   0 Problem D: Whats wrong with this DP ? spoilerconst int mxn = 65; int n; int a[mxn], dp[mxn][2]; //and -> 0, or-> 1 //dp(i, y) no of ways till ith index such yn is true int solve(int i, bool y) { if(i == n+1) { return y; } if(dp[i][y]) return dp[i][y]; if(a[i]) { dp[i][y] += solve(i+1, y | 0); return dp[i][y] += solve(i+1, y | 1); } else { dp[i][y] += solve(i+1, y & 0); return dp[i][y] += solve(i+1, y & 1); } return 0; } int32_t main() { FIO; #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif cin >> n; string x; for (int i = 1; i <= n; ++i) { cin >> x; if(x == "OR") a[i] = 1; } cout << solve(1, 1) << endl; return 0; } 
•  » » 20 months ago, # ^ |   +12 use long long
•  » » » 20 months ago, # ^ |   0 I am using [ #define int long long ] in my template
•  » » 20 months ago, # ^ |   0 if (dp[i][y]) return dp[i][y] This wont return for 0
 » 20 months ago, # |   -31 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.
•  » » 20 months ago, # ^ |   +12 That's your fault if you cannot handle precision errors. Its a beginner contest and B couldn't be more simple.
•  » » 20 months ago, # ^ |   0 I actually learnt the trick used to get AC on B from a previous ABC contest.
 » 20 months ago, # | ← Rev. 2 →   +3 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: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.
•  » » 20 months ago, # ^ |   +11 Your power function is taking the answer mod 1e9+7, but the question does not ask for that.
•  » » » 20 months ago, # ^ |   +3 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
•  » » » » 20 months ago, # ^ | ← Rev. 2 →   -7 $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.
•  » » » » » 20 months ago, # ^ |   +3 Yeah...got it. Thanks.
•  » » » » 20 months ago, # ^ |   +1 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.
 » 20 months ago, # |   +8 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!
•  » » 20 months ago, # ^ |   0 me too lol didnt notice the n <= 10^4
•  » » 20 months ago, # ^ |   +11 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!
•  » » » 20 months ago, # ^ | ← Rev. 5 →   0 Was O(N^2) accepted? I did using combination of sparsh tables and binary search. O(nlog(n)) Solution
•  » » » » 20 months ago, # ^ |   +3 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 :)
•  » » 20 months ago, # ^ |   0 Please share if you have a better solution than O(N^2).
•  » » » 20 months ago, # ^ |   +2
•  » » » 20 months ago, # ^ |   0 Search for the classical "max area histogram" problem. This was just a direct spinoff of that problem.
 » 20 months ago, # |   0 Can someone tell me how to solve E
•  » » 20 months ago, # ^ |   0 I used transformation matrices.
•  » » » 20 months ago, # ^ |   0 Can you link your code and the article for transformation matrices which contains Code in C++ as well
•  » » » » 20 months ago, # ^ |   0 My submission: https://atcoder.jp/contests/abc189/submissions/19628802Implementation in C++ shouldn't be too hard as the only thing you do is multiply matrices (it's my multiply function).
•  » » » » » 20 months ago, # ^ |   0 Ok thanks
•  » » 20 months ago, # ^ |   0 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).
•  » » » 20 months ago, # ^ |   0 Ok , can you link your submission , and Thanks in Advanced
•  » » » » 20 months ago, # ^ |   +1 I think my solution uses the same idea, so you can see mine:Solution
•  » » » » » 20 months ago, # ^ |   0 Thanks Man it helped
 » 20 months ago, # |   0 Can you explain to me please why my N ^ 2 solution not passed?
•  » » 20 months ago, # ^ |   0 Because you are iterating upto 1e5 in the outer loop
•  » » 20 months ago, # ^ |   0 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.
•  » » 20 months ago, # ^ | ← Rev. 2 →   0 BhaskarTM vongkh Thank you, guys. Fixed solution, it passed
 » 20 months ago, # | ← Rev. 2 →   0 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. $Expected[i] = \begin{cases} 0 + 1 \cdot x & \text{i is a trap} \\ 0 & i \geq n \\ \sum_{j=i+1}^{i+m}(1 + Expected[j])/m & \text{otherwise} \end{cases}$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
•  » » 20 months ago, # ^ |   0 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.
•  » » 20 months ago, # ^ |   0 Nicely explained! Came here after failing to understand the editorial, you made it much easier.
 » 20 months ago, # |   0 can anybody suggest a solution of o(n) or o(nlog(n)) for the c problem(if it exist)?
•  » » 20 months ago, # ^ |   +1 A classical problem — Largest rectangle under histogram
»
20 months ago, # |
Rev. 2   0

In c, what's wrong with my code ..any sample testcase

Spoiler
•  » » 20 months ago, # ^ | ← Rev. 2 →   0 check this sample case66 6 4 4 4 4 correct ans is 24
 » 20 months ago, # |   0 HOW TO SOLVE C?
•  » » 20 months ago, # ^ |   0 i used segment tree but time limit again.
•  » » 20 months ago, # ^ | ← Rev. 2 →   0 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); } } 
•  » » » 20 months ago, # ^ |   0 thanks i'll look into it
•  » » 20 months ago, # ^ |   0 We can also solve it using stack largest histogram area
 » 20 months ago, # |   -16 In C if we skip this condition for every integer i between l and r (inclusive), x≤ A[i] IMHO It would be a more interesting problem.
 » 20 months ago, # |   0 In problem B getting wrong in just 1 case. Tried with double also but not finding the bug.My approach
 » 20 months ago, # |   0 in problems like B can somebody explain how sum/100 has precisional errors? and how often do we need to avoid divisions for such errors?
 » 20 months ago, # |   0 Can someone tell me why I am getting WA for my code ? Code Link https://atcoder.jp/contests/abc189/submissions/19656755
•  » » 20 months ago, # ^ |   0 6 6 5 4 3 2 1  Spoilerfor this case your output is 6 but correct output should be 12
•  » » » 20 months ago, # ^ |   0 Thank you sir for looking into problem and providing with the testcase
 » 20 months ago, # |   0 how to solve F i think it is a dp question , but couldn't get the idea how to approach
 » 20 months ago, # |   0 Can someone explain how to solve E? or any resources?
 » 20 months ago, # |   0 If somebody's interested in video solutions (A to E) and screencast for this contest: https://www.youtube.com/watch?v=jJw0BFDOHAE
 » 20 months ago, # |   -16 int main() { CR7; ll n,x;cin>>n>>x; double sum=0; double v,p; ll ans=-1; for(ll i=0;i>v>>p; sum+= (v*(p/100)); if(sum>x && ans==-1) { ans=i+1; } } cout<
 » 20 months ago, # |   0 Why does the correct logic of C in python give a TLE while it gets an AC in cpp?py code: n=int(input()) arr=list(map(int,input().split())) val=0 for i in range(n): ele=arr[i] for j in range(1,n-i+1): if arr[i+j-1]
•  » » 20 months ago, # ^ | ← Rev. 2 →   0 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
 » 20 months ago, # |   0 From the editorial for F: $f(0)$ can be up to $N * 4^K / 2$Can someone explain this bound?
•  » » 20 months ago, # ^ |   0 n = 100000 m = 2 k = 10 99972 99975 99978 99981 99984 99987 99990 99993 99996 99999 answer ~ 52414818886.700114119797945 
 » 20 months ago, # |   +11 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
 » 20 months ago, # |   0 in the editorial right here https://atcoder.jp/contests/abc189/editorial/591 shouldn't it be f(S1,...,SN)=2^(N-1)+f(S1,...,SN−1) instead of f(S1,...,SN)=2^N+f(S1,...,SN−1)