chokudai's blog

By chokudai, history, 5 weeks ago, In English

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!

 
 
 
 
  • Vote: I like it
  • +59
  • Vote: I do not like it

»
5 weeks ago, # |
  Vote: I like it +49 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

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

»
5 weeks ago, # |
Rev. 2   Vote: I like it +16 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Best of Luck to Everyone !!

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
5 weeks ago, # |
Rev. 2   Vote: I like it +2 Vote: I do not like it

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

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    AtCoder Beginner Contest

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yea i know but i didn't realize it's atcoder beginner contest thanks <3

»
5 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

If you're getting a WA in D : Logical Expression even with the correct logic, recall that

(1 << i) != (1LL << i)

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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?

»
5 weeks ago, # |
  Vote: I like it +16 Vote: I do not like it

How to solve E ?

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    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.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

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

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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?

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          understand the intuition better now, thanks! :)

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 :(

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it +8 Vote: I do not like it

    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.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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?

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like 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:

        1. Multiply $$$xpol$$$ by -1, exchange $$$ypol$$$ and $$$xpol$$$. Also swap the actual values of $$$x$$$ and $$$y$$$.
        2. Multiply $$$ypol$$$ by -1, exchange $$$ypol$$$ and $$$xpol$$$. Also swap the actual values of $$$x$$$ and $$$y$$$.
        3. $$$(a_t,b_t) \rightarrow (-a_t, 2p-b_t)$$$
        4. $$$(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.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      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

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve D?

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    using DP

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

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    DP, I think the code is easy to understand.

  • »
    »
    5 weeks ago, # ^ |
    Rev. 3   Vote: I like it +3 Vote: I do not like it

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

  • »
    »
    5 weeks ago, # ^ |
    Rev. 4   Vote: I like it +1 Vote: I do not like it

    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

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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
»
5 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

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)

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

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

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

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

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

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

submissions: 19630680

  • »
    »
    5 weeks ago, # ^ |
    Rev. 3   Vote: I like it +8 Vote: I do not like it

    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.

»
5 weeks ago, # |
Rev. 4   Vote: I like it -18 Vote: I do not like it

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:


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<curDrunk: print(i) break else: print(-1)
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I also want to know!!!

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    instead of dividing by 100 multiply x by 100

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    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

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    multiply x by 100 instead of dividing p by 100

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      5 weeks ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      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.

      Link: https://atcoder.jp/contests/abc189/submissions/19632194

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve D without DP?

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      YES.PLEASE EXPLAIN IN A BRIEF IF U CAN.

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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)

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    DFS? I'm not sure.

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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

  • »
    »
    5 weeks ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    For D you can just use a simple loop:

    Spoiler
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve F?

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

Help!

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it


Problem D: Whats wrong with this DP ?

spoiler
  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    use long long

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I am using [ #define int long long ] in my template

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it -31 Vote: I do not like it

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.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

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

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
5 weeks ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

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.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

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!

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone tell me how to solve E

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Because you are iterating upto 1e5 in the outer loop

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

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

»
5 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
5 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

Spoiler
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

HOW TO SOLVE C?

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i used segment tree but time limit again.

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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);
      }
    }
    
    
  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    We can also solve it using stack largest histogram area

»
5 weeks ago, # |
  Vote: I like it -16 Vote: I do not like it

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.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem B getting wrong in just 1 case. Tried with double also but not finding the bug.

My approach

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone tell me why I am getting WA for my code ? Code Link https://atcoder.jp/contests/abc189/submissions/19656755

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    6
    6 5 4 3 2 1
    
    Spoiler
    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you sir for looking into problem and providing with the testcase

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve F i think it is a dp question , but couldn't get the idea how to approach

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain how to solve E? or any resources?

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it -16 Vote: I do not like it

int main() { CR7; ll n,x;cin>>n>>x; double sum=0; double v,p; ll ans=-1; for(ll i=0;i<n;i++) { cin>>v>>p; sum+= (v*(p/100)); if(sum>x && ans==-1) { ans=i+1; } } cout<<ans; return 0; } can any one tell me, why my code was giving WA on question B although the logic was absolutely correct?

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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]<ele:
            ele=arr[i+j-1]
        val=max((j)*ele,val)
print(val)

submission link: atcoder abc 189 c code in py

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

Can someone explain this bound?

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    n = 100000 m = 2 k = 10
    99972 99975 99978 99981 99984 99987 99990 99993 99996 99999
    
    
    answer ~ 52414818886.700114119797945
    
»
5 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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)