### chokudai's blog

By chokudai, history, 15 months ago,

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!

• +62

 » 15 months ago, # |   +7 Something looks not right..
 » 15 months ago, # | ← Rev. 2 →   +11 How to solve E?
•  » » 15 months ago, # ^ | ← Rev. 3 →   0 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 solutionloop on i is for k(number of segments)loop on j to find out segment which is divisible by khttps://atcoder.jp/contests/abc207/submissions/23789423
 » 15 months ago, # |   0 How to solve D? Is it related to 1017E - The Supersonic Rocket, in some way?
•  » » 15 months ago, # ^ |   0 D was havoc!!!!!!!!
 » 15 months ago, # | ← Rev. 4 →   -18 why d my solution got wrong???? is it possible to rotate degree that isn't 0, 90, 180, 270? Spoiler# pragma GCC optimize ("O3") # pragma GCC optimize ("Ofast") # pragma GCC optimize ("unroll-loops") #define _CRT_SECURE_NO_WARNINGS #include #define rep(i,a,b) for(int i = (a); i < (b); i++) #define rep2(i,a,b) for(int i = (b) — 1; i >= (a); i--) #define all(x) (x).begin(), (x).end() #define sz(x) ((int)(x).size()) #define pb push_back #define eb emplace_back #define em emplace #define popcount __builtin_popcount #define popcountll __builtin_popcountll #define x first #define y second using namespace std; using ll = long long; using ld = long double; using pi = pair; using ti = tuple; using pl = pair; using tl = tuple; ll N, flag[4]; pl A[100], B[100], a, b; set S; pl rotate(pl a, int dir){ if(dir == 0) return a; if(dir == 1) return {-a.y, a.x}; if(dir == 2) return {-a.x, -a.y}; return {a.y, -a.x}; } int main() { cin.tie(0) -> sync_with_stdio(false); cout.tie(0); cin >> N; rep(i, 0, N) cin >> A[i].x >> A[i].y; rep(i, 0, N) cin >> B[i].x >> B[i].y; rep(i, 0, N) { a.x += A[i].x; a.y += A[i].y; b.x += B[i].x; b.y += B[i].y; } rep(i, 0, N){ A[i].x = N * A[i].x — a.x; A[i].y = N * A[i].y — a.y; B[i].x = N * B[i].x — b.x; B[i].y = N * B[i].y — b.y; S.insert(B[i]); } rep(i, 0, N){ rep(j, 0, 4) if(S.count(rotate(A[i], j)) == 0) flag[j] = 1; } rep(j, 0, 4) if(flag[j] == 0){ cout << "Yes\n"; return 0; } cout << "No\n"; } 
•  » » 15 months ago, # ^ | ← Rev. 3 →   0 Yes. Think this:20 01 20 02 1
•  » » » 15 months ago, # ^ |   -8 Is there such a case for three or more points? I am not able to find such a case. Thankss
•  » » » » 15 months ago, # ^ |   0 30 05 010 00 03 46 8
•  » » » » » 15 months ago, # ^ |   -8 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, # ^ |   +1 Here you go: full integer solution https://atcoder.jp/contests/abc207/submissions/23834422
•  » » » » » » » 15 months ago, # ^ | ← Rev. 2 →   +2 What is your normalize function doing actually Edit: Is it kind of very obvious, I didnt really understand
•  » » » » » » » » 15 months ago, # ^ |   0 It reduces every set of points that's equal under rotation/translation to the same set of points.
•  » » 15 months ago, # ^ |   0 Yeah, if S={(0, 0), (1, 2)}, T={(0, 0), (2, 1)} for example.
•  » » » 15 months ago, # ^ |   0 oh thanks
•  » » » 15 months ago, # ^ | ← Rev. 2 →   0 Is there such a case for three or more points?edit: ok I got one: 3 0 2 1 5 5 2 2 3 3 0 7 3 
•  » » 15 months ago, # ^ |   +3 Place your code in spoiler. It's eating up too much space.
•  » » » 15 months ago, # ^ |   0 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, # |   +7 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, # ^ |   +8 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, # ^ |   0 Yeah I too can't get that point. If anyone can explain that part.
 » 15 months ago, # |   0 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. Code#include using namespace std; #define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define ll long long #define all(v) v.begin(),v.end() #define F first #define S second #define pb push_back #define mp make_pair #define pi pair #define pii pair #define REP(i,n) for(int i=0;i> n; vector t(n),l(n),r(n); for(i=0;i> t[i] >> l[i] >> r[i]; if(t[i]==2) r[i]-=0.01; else if(t[i]==3) l[i]+=0.01; else if(t[i]==4){ l[i]+=0.01; r[i]-=0.01; } } int cnt=0; for(i=0;ir[j] || r[i] using namespace std; #define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define ll long long #define all(v) v.begin(),v.end() #define F first #define S second #define pb push_back #define mp make_pair #define pi pair #define REP(i,n) for(int i=0;i p1, pair p2){ if(p1.F < p2.F) return true; else if(p1.F > p2.F) return false; else{ return p1.S < p2.S; } } void run_case(){ int n,i; cin >> n; vector x(n),y(n),xx(n),yy(n); double pii = 2 * acos(0.0); for(i=0;i> x[i] >> y[i]; for(i=0;i> xx[i] >> yy[i]; double s1 = accumulate(all(x),0); double s2 = accumulate(all(y),0); s1 = 1.0*s1/n; s2 = 1.0*s2/n; double xa = 0 - s1; double ya = 0 - s2; for(i=0;i> p2; for(i=0;i> p1; double radi = (p*pii)/180; for(i=0;i
•  » » 15 months ago, # ^ |   0 Can you explain the equation , Y[I]= CY*cos(radi)-CX*sin(radi) , Same for X[I] , My geometry is weak
•  » » » 15 months ago, # ^ |   +3 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, # ^ |   0 Thanks for the idea and code of D.
•  » » » 15 months ago, # ^ |   0 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, # ^ |   0 How is it used here ? Can you elaborate . And how to calculate e^(i*theta)(X+iY)
•  » » » » » 15 months ago, # ^ |   +3 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, # |   +9 used too much time on D... wasnt able to do E which i think is easier
 » 15 months ago, # |   +2 my screencast with solutions for a-e
 » 15 months ago, # | ← Rev. 2 →   0 How to solve problem C when N <= 2*(10^5) ?
•  » » 15 months ago, # ^ |   0 Sort the pairs in order of their increasing $r_i$ then just binary search for the pair with $r_j > l_i$, \$(j
 » 15 months ago, # | ← Rev. 3 →   +17 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, # ^ |   -34 Competing since 10 years still a noob :')
•  » » » 15 months ago, # ^ |   +20 But I don't create alt accounts :)
•  » » » » 15 months ago, # ^ |   -32 You even can't use your brain. So should I also stop using my brain? >^<