chokudai's blog

By chokudai, history, 3 years 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

| Write comment?
»
3 years ago, # |
  Vote: I like it +7 Vote: I do not like it

hmm

Something looks not right..

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

How to solve E?

  • »
    »
    3 years 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

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve D? Is it related to 1017E - Сверхзвуковая ракета, in some way?

»
3 years 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
  • »
    »
    3 years 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

    • »
      »
      »
      3 years 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

  • »
    »
    3 years 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.

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

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

    • »
      »
      »
      3 years 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..

»
3 years 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?

  • »
    »
    3 years 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.

»
3 years 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
  • »
    »
    3 years 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

    • »
      »
      »
      3 years 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

    • »
      »
      »
      3 years 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)$$$.

      • »
        »
        »
        »
        3 years 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)

        • »
          »
          »
          »
          »
          3 years 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.

»
3 years 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

»
3 years ago, # |
  Vote: I like it +2 Vote: I do not like it

my screencast with solutions for a-e

»
3 years 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

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

    Competing since 10 years still a noob :')