chokudai's blog

AtCoder Beginner Contest 189 Announcement
By chokudai, history, 4 years 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

Comments Comments (111)
| Write comment?
»
4 years ago, # |
  Vote: I like it +49 Vote: I do not like it

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

→ Reply
»
4 years 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. :')

→ Reply
»
4 years 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.

→ Reply
»
4 years 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?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    AtCoder Beginner Contest

    → Reply
    • »
      »
      »
      4 years 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?

      → Reply
      • »
        »
        »
        »
        4 years 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.

        → Reply
        • »
          »
          »
          »
          »
          4 years 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.

          → Reply
  • »
    »
    4 years 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).

    → Reply
»
4 years 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)

→ Reply
  • »
    »
    4 years 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?

    → Reply
»
4 years ago, # |
  Vote: I like it +16 Vote: I do not like it

How to solve E ?

→ Reply
  • »
    »
    4 years 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.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
    • »
      »
      »
      4 years 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++).

      → Reply
    • »
      »
      »
      4 years 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?

      → Reply
      • »
        »
        »
        »
        4 years 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.

        → Reply
    • »
      »
      »
      4 years 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 :(

      → Reply
      • »
        »
        »
        »
        4 years 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).

        → Reply
  • »
    »
    4 years 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.

    → Reply
    • »
      »
      »
      4 years 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?

      → Reply
      • »
        »
        »
        »
        4 years 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.

        → Reply
    • »
      »
      »
      4 years 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

      → Reply
  • »
    »
    4 years 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$$$

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve D?

→ Reply
  • »
    »
    4 years 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)

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    DP, I think the code is easy to understand.

    → Reply
  • »
    »
    4 years 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).

    → Reply
  • »
    »
    4 years 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

    → Reply
»
4 years 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)

→ Reply
  • »
    »
    4 years 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.

    → Reply
  • »
    »
    4 years 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 !!

    → Reply
  • »
    »
    4 years 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

    → Reply
»
4 years 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

→ Reply
  • »
    »
    4 years 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.

    → Reply
»
4 years 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)
→ Reply
»
4 years 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)?

→ Reply
  • »
    »
    4 years 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.

    → Reply
»
4 years 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?

→ Reply
  • »
    »
    4 years 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$$$.

    → Reply
»
4 years 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

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

    → Reply
  • »
    »
    4 years 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

    → Reply
  • »
    »
    4 years 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

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    multiply x by 100 instead of dividing p by 100

    → Reply
  • »
    »
    4 years 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...

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve D without DP?

→ Reply
  • »
    »
    4 years 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

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      YES.PLEASE EXPLAIN IN A BRIEF IF U CAN.

      → Reply
      • »
        »
        »
        »
        4 years 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)

        → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    DFS? I'm not sure.

    → Reply
  • »
    »
    4 years 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

    → Reply
»
4 years 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!

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it


Problem D: Whats wrong with this DP ?

spoiler
→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    use long long

    → Reply
  • »
    »
    4 years 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

    → Reply
»
4 years 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.

→ Reply
  • »
    »
    4 years 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.

    → Reply
»
4 years 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.

→ Reply
»
4 years 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!

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone tell me how to solve E

→ Reply
»
4 years 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?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Because you are iterating upto 1e5 in the outer loop

    → Reply
  • »
    »
    4 years 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.

    → Reply
»
4 years 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

→ Reply
  • »
    »
    4 years 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.

    → Reply
  • »
    »
    4 years 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.

    → Reply
»
4 years 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)?

→ Reply
»
4 years 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

→ Reply
»
4 years 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?

→ Reply
  • »
    »
    4 years 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
    → Reply
»
4 years 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

→ Reply