Блог пользователя chokudai

Автор chokudai, история, 4 года назад, По-английски

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
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +49 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

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

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +16 Проголосовать: не нравится

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

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +2 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +7 Проголосовать: не нравится

    AtCoder Beginner Contest

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 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.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +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).

»
4 года назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

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

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

»
4 года назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

How to solve E ?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +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.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +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++).

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 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?

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 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.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 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 :(

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
    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:

    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.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 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?

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 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:

        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.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 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$$$

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve D?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    using DP

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    DP, I think the code is easy to understand.

  • »
    »
    4 года назад, # ^ |
    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).

  • »
    »
    4 года назад, # ^ |
    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

»
4 года назад, # |
  Проголосовать: нравится +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)

»
4 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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

submissions: 19630680

  • »
    »
    4 года назад, # ^ |
    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.

»
4 года назад, # |
Rev. 4   Проголосовать: нравится -18 Проголосовать: не нравится

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)
»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
    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.

»
4 года назад, # |
  Проголосовать: нравится 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?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
    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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    multiply x by 100 instead of dividing p by 100

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +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...

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve D without DP?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      YES.PLEASE EXPLAIN IN A BRIEF IF U CAN.

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 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)

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    DFS? I'm not sure.

  • »
    »
    4 года назад, # ^ |
    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

    EDIT: https://atcoder.jp/contests/abc189/submissions/19610002

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve F?

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

Help!

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится


Problem D: Whats wrong with this DP ?

spoiler
»
4 года назад, # |
  Проголосовать: нравится -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.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +12 Проголосовать: не нравится

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

»
4 года назад, # |
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:

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.

»
4 года назад, # |
  Проголосовать: нравится +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!

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can someone tell me how to solve E

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Because you are iterating upto 1e5 in the outer loop

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 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.

»
4 года назад, # |
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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 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.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

Can someone explain this bound?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    n = 100000 m = 2 k = 10
    99972 99975 99978 99981 99984 99987 99990 99993 99996 99999
    
    
    answer ~ 52414818886.700114119797945
    
»
4 года назад, # |
  Проголосовать: нравится +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