We will hold AtCoder Beginner Contest 207.

- Contest URL: https://atcoder.jp/contests/abc207
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20210626T2100&p1=248
- Duration: 100 minutes
- Number of Tasks: 6
- Writer: penguinman, ynymxiaolongbao
- Rated range: ~ 1999

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

We are looking forward to your participation!

Something looks not right..

How to solve E?

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

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

D was havoc!!!!!!!!

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

SpoilerYes. Think this:

2

0 0

1 2

0 0

2 1

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

3

0 0

5 0

10 0

0 0

3 4

6 8

Yeah I also got one just now!

Seems like it is difficult to avoid double based solution

Here you go: full integer solution https://atcoder.jp/contests/abc207/submissions/23834422

What is your normalize function doing actually Edit: Is it kind of very obvious, I didnt really understand

It reduces every set of points that's equal under rotation/translation to the same set of points.

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

oh thanks

Is there such a case for three or more points?

edit: ok I got one:

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

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

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

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.

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

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:

IdeaWe consider intervals of all types in shift them by some small value in or out according to their types. Finally we bruteforce all pairs to check intersection (O(1)) and return the count.

CodeD :

IdeaBring both the configurations of points to the origin.(You can do this by translating all points by adding shifts in x and y needed to bring centroid to origin). Next we can rotate one configuration keeping other fixed in intervals of 0.001 degrees(Basically bruteforce). And after every such rotation check if the 2 systems match or not. One such way to check is to sort both the configurations first by x then by y.

. It barely passed.

CodeE:

Unoptimized ideaP is prefix sum.

dp[i][j] denotes number of subsequences uptil index i such that we can split it into j blocks.

Then this transition is straightforward but sadly its O(n^3) so I didnt bother to code and was thinking of optimizing it the whole time.

dp[i][j] += ((P[i] — P[x])%j == 0 ? dp[x][j-1] : 0) over all x from 1 to i-1

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

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

Thanks for the idea and code of D.

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

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

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.

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

my screencast with solutions for a-e

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

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.

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 resultCompeting since 10 years still a noob :')

But I don't create alt accounts :)

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