chokudai's blog

By chokudai, history, 15 months ago, In English

We will hold AtCoder Beginner Contest 207.

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

We are looking forward to your participation!

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

»
15 months ago, # |
  Vote: I like it +7 Vote: I do not like it

hmm

Something looks not right..

»
15 months ago, # |
Rev. 2   Vote: I like it +11 Vote: I do not like it

How to solve E?

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

    I solved it with DP.

    suppose you are dividing Array into k segments then to follow problem condition there must be k-1 subsegment following the condition and 1 segment after k-1 which is divisible by k.

    you can see my solution

    loop on i is for k(number of segments)

    loop on j to find out segment which is divisible by k

    https://atcoder.jp/contests/abc207/submissions/23789423

»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve D? Is it related to 1017E - The Supersonic Rocket, in some way?

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

why d my solution got wrong???? is it possible to rotate degree that isn't 0, 90, 180, 270?

Spoiler
  • »
    »
    15 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    Yes. Think this:
    2
    0 0
    1 2
    0 0
    2 1

    • »
      »
      »
      15 months ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      Is there such a case for three or more points? I am not able to find such a case. Thankss

      • »
        »
        »
        »
        15 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        3
        0 0
        5 0
        10 0
        0 0
        3 4
        6 8

        • »
          »
          »
          »
          »
          15 months ago, # ^ |
            Vote: I like it -8 Vote: I do not like it

          Yeah I also got one just now!

          3
          0 2
          1 5
          5 2
          2 3
          3 0
          7 3
          

          Seems like it is difficult to avoid double based solution

  • »
    »
    15 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yeah, if S={(0, 0), (1, 2)}, T={(0, 0), (2, 1)} for example.

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

    Place your code in spoiler. It's eating up too much space.

    • »
      »
      »
      15 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      thanks for advice. nobody told me there's 'spoiler' section, and downvoted my comment without any words why they are downvoting my comment. what a harsh world..

»
15 months ago, # |
  Vote: I like it +7 Vote: I do not like it

Tutorial E I did not understood the trick to go from O(n^3) to O(n^2). Can somebody explain with more words?

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

    The naive DP is dp[i][k] := # collections of k subsequences with i being the last element of the kth subseq. To calculate it, you iterate over the interval of the kth subseq. [i-x, i], and if a_{i-x}+...+a_i is divisible by k, then you add dp[i-x-1][k-1] to dp[i][k].

    However, we only need to care about x such that a_1+...a_{i-x-1} == a_1+...+a_i mod k. So let's just compute the sum of all dp[i][k]s such that [the prefix sum up to i] == M mod k+1 as sum[k][M] after each iteration of i. Then our transition is just dp[i][k] = sum[k-1][(a_1+...+a_i)%k]. We can make this O(1) if we change our dp[i][k] to dp[k], representing the sum of all dp[i][k] computed so far.

  • »
    »
    15 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yeah I too can't get that point. If anyone can explain that part.

»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for the good contest. Was able to solve till D and got that E was dp but could not optimize it from O(n^3) to O(n^2). Here are the ideas for C,D,E :

C:

Idea
Code

D :

Idea
Code

E:

Unoptimized idea
  • »
    »
    15 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you explain the equation , Y[I]= CY*cos(radi)-CX*sin(radi) , Same for X[I] , My geometry is weak

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

      Yes, sure. When you rotate some point relative to the origin, it is the same as rotating the origin relative to that point which is the same as rotating axes by some angle theta.

      Now from linear algebra there is this matrix called the rotation matrix which when multiplied with the current {x,y} column vector gives the coordinate of the new rotated point about the origin. (You can try deriving it by using polar coordinates and some trigonometry). Note that this matrix works when rotation is CCW. In our case for CW rotation replace theta with 360-theta.

      You can have a look at this matrix here :

      https://en.wikipedia.org/wiki/Rotation_matrix

    • »
      »
      »
      15 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      In the complex plane, the rotation of $$$x+iy$$$ around the origin by an angle $$$\theta$$$ is just the product $$$e^{i\theta}(x+iy)$$$.

      • »
        »
        »
        »
        15 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        How is it used here ? Can you elaborate . And how to calculate e^(i*theta)(X+iY)

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

          Let's note $$$(x′, y′)$$$ the new coordinates of the point $$$(x, y)$$$ after the rotation by an angle $$$\theta$$$.
          We have $$$x'+iy' = e^{i\theta}(x+iy)$$$.
          Then as $$$e^{i\theta} = \cos(\theta) + i \sin(\theta)$$$ and $$$i^2 = -1$$$, we can compute the product $$$x'+iy' = (\cos(\theta) + i \sin(\theta))(x+iy) = (x \cos(\theta) - y \sin(\theta)) + i (x \sin(\theta) + y \cos(\theta))$$$.
          After identification, we obtain : $$$x'= x \cos(\theta) - y \sin(\theta)$$$ and $$$y'=x \sin(\theta) + y \cos(\theta)$$$.
          So it's just a simple way to obtain the rotation matrix as in https://en.wikipedia.org/wiki/Rotation_matrix.

»
15 months ago, # |
  Vote: I like it +9 Vote: I do not like it

used too much time on D... wasnt able to do E which i think is easier

»
15 months ago, # |
  Vote: I like it +2 Vote: I do not like it

my screencast with solutions for a-e

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

How to solve problem C when N <= 2*(10^5) ?

  • »
    »
    15 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Sort the pairs in order of their increasing $$$r_i$$$ then just binary search for the pair with $$$r_j > l_i$$$, $$$(j<i)$$$ there are some corner cases which you need to check for type 1,2 and 3.

»
15 months ago, # |
Rev. 3   Vote: I like it +17 Vote: I do not like it

maroonrk chokudai

Please implement feature that allow see solution by clicking user solution in standing as codeforces. Currently it's not comfortable, user should click user submissions and find solution.

UPD : This functionality implemented in clist.by , for example last contest result

  • »
    »
    15 months ago, # ^ |
      Vote: I like it -34 Vote: I do not like it

    Competing since 10 years still a noob :')

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

      But I don't create alt accounts :)

      • »
        »
        »
        »
        15 months ago, # ^ |
          Vote: I like it -32 Vote: I do not like it

        You even can't use your brain. So should I also stop using my brain? >^<