Selamat petang!

The curtain has fallen on Codeforces Round #487 (Div. 2). Have you enjoyed the problems themselves? Or the stories? Or both? Neither?

I hadn't ever intended to create a hard contest, believe me... (╥﹏╥) The author will try to find ways to estimate the difficulty better in the future. Also, stronger pretests, notes taken.

Anyways, hope you've all enjoyed the challenges you've faced, and gained something from this round. Congratulations to those who performed well, and commiserations to those waiting for their next chance to shine (^_−)−☆

Below are the tutorials of all problems. Feel free to point out mistakes (if any) or share your ideas in the comments! I might be overcomplicating or confusing something > <

**Short Ruby solution**

```
puts gets.codepoints.each_cons(3).any?{|x,y,z|x*y*z==287430}?'Yes':'No'
```

**Noam's C++ solution**

```
#include <bits/stdc++.h>
#define endl '\n'
#define fast ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define finish(x) return cout << x << endl, 0
using namespace std;
string s, t;
int n, p;
bool isperiod() {
for (int i = p; i < n; i++)
if (t[i] != t[i - p]) return false;
return true;
}
int main() {
fast;
cin >> n >> p >> s;
// attempt 1
t = s;
for (auto &i : t)
if (i == '.') i = '0';
if (!isperiod()) finish(t);
// attempt 2
int i = 0;
while (i < n && s[i] != '.') i++;
if (i + p < n) {
t[i] = '1';
finish(t);
}
i = n - 1;
while (i >= 0 && s[i] != '.') i--;
if (i - p >= 0) {
t[i] = '1';
finish(t);
}
finish("No");
}
```

**Python solution for the original problem as well as for the last challenge**

```
n, p = map(int, input().split())
s = input()
t = s.replace('.', '0')
if all(t[i] == t[i + p] for i in range(n - p)):
rmost = -1
for r in range(p - 1, -1, -1):
x = s[r::p].rfind('.')
if x != -1 and s[r::p] != '.':
rmost = max(rmost, x * p + r)
if rmost == -1:
print('No')
else:
print(t[:rmost] + '1' + t[(rmost + 1):])
else:
print(t)
```

**C++ seemingly-brute-force solution**

```
#include <algorithm>
#include <cstdio>
static const int MAXN = 2005;
static int n, p;
static char s[MAXN];
static int dots_ct = 0, dots[MAXN];
int main()
{
scanf("%d%d%s", &n, &p, s);
for (int i = 0; i < n; ++i) if (s[i] == '.') {
dots[dots_ct++] = i;
s[i] = '0';
}
for (int i = 1; i <= (1 << std::min(dots_ct, 19)); ++i) {
bool is_period = true;
for (int j = 0; j < n - p; ++j)
if (s[j] != s[j + p]) { is_period = false; break; }
if (!is_period) {
puts(s);
return 0;
}
for (int j = 0; j <= __builtin_ctz(i); ++j)
s[dots[j]] ^= 1;
}
puts("No");
return 0;
}
```

**Model solution**

```
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <utility>
#include <vector>
static const int MAXM = 50;
int main()
{
srand(1);
int a[4];
scanf("%d%d%d%d", &a[0], &a[1], &a[2], &a[3]);
int M = std::max(2, std::min(MAXM, *std::max_element(a, a + 4)));
std::vector<std::string> g;
for (int k = 0; k < 4; ++k) {
int islands = a[(k + 1) % 4] - 1;
std::string s(M, 'A' + k);
std::vector<std::pair<int, int>> pos;
g.push_back(s);
for (int x = 0; x < (islands + (M - 2)) / (M - 1); ++x) {
for (int i = 0; i < 3; ++i) g.push_back(s);
for (int i = (x & 1); i < M - !(x & 1); ++i)
pos.push_back({(int)g.size() - 2 - ((i ^ x) & 1), i});
}
std::random_shuffle(pos.begin(), pos.end());
for (int i = 0; i < islands; ++i)
g[pos[i].first][pos[i].second] = 'A' + (k + 1) % 4;
}
if (g.size() <= M) {
printf("%lu %d\n", g.size(), M);
for (int i = 0; i < g.size(); ++i) puts(g[i].c_str());
} else {
printf("%d %lu\n", M, g.size());
for (int i = 0; i < M; ++i) {
for (int j = 0; j < g.size(); ++j) putchar(g[j][i]);
putchar('\n');
}
}
return 0;
}
```

**Model solution**

```
#include <cstdio>
#include <algorithm>
#include <vector>
static const int MAXN = 1e5 + 3;
static const int INF32 = 0x7fffffff;
typedef long long int64;
static int n, l, w;
static int x[MAXN], v[MAXN];
static std::vector<int> pos, neg;
inline int div_floor(int64 a, int b)
{
if (b == 0) return (a > 0 ? +INF32 : -INF32);
if (a % b < 0) a -= (b + a % b);
return a / b;
}
int main()
{
scanf("%d%d%d", &n, &l, &w);
for (int i = 0; i < n; ++i) {
scanf("%d%d", &x[i], &v[i]);
(v[i] == +1 ? pos : neg).push_back(x[i]);
}
std::sort(pos.begin(), pos.end());
std::sort(neg.begin(), neg.end());
int64 ans = 0;
for (int v : neg) {
auto barrier = std::lower_bound(pos.begin(), pos.end(), -v - l);
int u_max_0 = div_floor((int64)(v + l) * (w + 1) - 1, w - 1),
u_max_1 = div_floor((int64)(v + l) * (w - 1) - 1, w + 1);
ans +=
(std::upper_bound(pos.begin(), barrier, u_max_0) - pos.begin()) +
(std::upper_bound(barrier, pos.end(), std::min(v, u_max_1)) - barrier);
}
printf("%lld\n", ans);
return 0;
}
```

**Model solution**

```
#include <cassert>
#include <cstdio>
#include <algorithm>
#include <utility>
#include <vector>
static const int MAXN = 202;
static const int LOGM = 15;
static int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
struct point {
int x, y;
point(int x = 0, int y = 0) : x(x), y(y) { }
};
struct line {
// ax + by + c = 0
int a, b, c;
line() : a(0), b(0), c(0) { }
line(const point &p, const point &q)
: a(p.y - q.y)
, b(q.x - p.x)
, c(q.y * p.x - q.x * p.y)
{
int g = gcd(gcd(a, b), c);
if (g != 1) { a /= g; b /= g; c /= g; }
if (a < 0) { a = -a; b = -b; c = -c; }
}
inline bool contains(const point &p) {
return a * p.x + b * p.y + c == 0;
}
// For sorting & duplicate removing
inline bool operator < (const line &other) const {
return a != other.a ? a < other.a :
b != other.b ? b < other.b : c < other.c;
}
inline bool operator == (const line &other) const {
return a == other.a && b == other.b && c == other.c;
}
};
struct mat {
static const int N = ::MAXN;
int sz;
double a[N][N];
mat(int sz = N, int id = 0) : sz(sz) {
for (int i = 0; i < N; ++i)
for (int j = 0; j < N; ++j)
a[i][j] = (i == j ? id : 0);
}
inline mat operator * (const mat &other) {
assert(other.sz == this->sz);
mat ret(sz, 0);
for (int i = 0; i < sz; ++i)
for (int k = 0; k < sz; ++k)
for (int j = 0; j < sz; ++j)
ret.a[i][j] += this->a[i][k] * other.a[k][j];
return ret;
}
inline std::vector<double> operator * (const std::vector<double> &u) {
assert(u.size() == this->sz);
std::vector<double> v(sz);
for (int i = 0; i < sz; ++i)
for (int j = 0; j < sz; ++j)
v[i] += a[i][j] * u[j];
return v;
}
};
static int n, q;
static point p[MAXN];
static line l[MAXN * MAXN / 2];
// Lists of lines that pass through points
static std::vector<int> pl[MAXN];
// Lists of points that lie on lines
static std::vector<int> lp[MAXN * MAXN / 2];
static mat A, Ap[LOGM];
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; ++i) scanf("%d%d", &p[i].x, &p[i].y);
int l_num = 0;
for (int i = 0; i < n; ++i)
for (int j = i + 1; j < n; ++j)
l[l_num++] = line(p[i], p[j]);
std::sort(l, l + l_num);
l_num = std::unique(l, l + l_num) - &l[0];
for (int i = 0; i < n; ++i)
for (int j = 0; j < l_num; ++j)
if (l[j].contains(p[i])) {
pl[i].push_back(j);
lp[j].push_back(i);
}
A = mat(n, 0);
for (int i = 0; i < n; ++i) {
for (int j : pl[i])
for (int k : lp[j])
A.a[i][k] += 1.0L / (pl[i].size() * lp[j].size());
}
Ap[0] = A;
for (int i = 1; i < LOGM; ++i) Ap[i] = Ap[i - 1] * Ap[i - 1];
scanf("%d", &q);
std::vector<double> u(n);
for (int i = 0, t, m; i < q; ++i) {
scanf("%d%d", &t, &m); --t;
std::fill(u.begin(), u.end(), 0);
u[t] = 1.0;
for (int j = 0; j < LOGM; ++j)
if ((m - 1) & (1 << j)) u = Ap[j] * u;
double max = -1.0;
for (int j = 0; j < l_num; ++j) {
double cur = 0.0;
for (int k : lp[j]) cur += u[k];
cur /= lp[j].size();
max = std::max(max, cur);
}
printf("%.12lf\n", (double)max);
}
return 0;
}
```

See you next time! I hope I'll be welcomed. Cheers!

Editorial is cool like announcement!

A bit simpler C solution pictureIt is more difficult instead ...

Super fast editorial !

Everything in this contest is great !!

Can anyone please explain the solution for C in English?

Edit: I believe I understand now. Thanks!

Just replace the one-cell components with their surroundings. Sorry for not making this clear.

Can you please explain it a little more Thank you!!

Video solution with explanation: https://youtu.be/BLnY8UrSR_o

Thanks!

woah, rating change of 195 in just 30 hours for me.boss feeling

Really enjoyed today's contest, thank you cyand1317

(≧▽≦)

Found a smaller solution for A, simply changed product to XOR in your Ruby solution ^.^

67 charactersputs gets.codepoints.each_cons(3).any?{|x,y,z|x^y^z==64}?'Yes':'No'

I know that in problem C, number of components cannot exceed 100. But will your solution work for inputs like "1225 1225 1 1" if we remove that constraint?

no

It will work for large input, but the number of rows will exceed 50. The problem is designed so that there are a huge number of ways to construct an anwer.

For "1225 1225 1 1", we can do it 50x50 grid. But with your solution I don't think it's possible. Can you extend your solution to work for such inputs ?

I can add one special check and make a 50×51 grid just for this case (> <)

The best solution I can come up with so far is here. I have no idea how to extend it...

My solution to C:

Mine!

Mine for input 100 100 100 100

for p==n in Problem B there was no way to conclude answer is No as only about positive p the condition was mentioned. This cost me whole problem. sad wordings :(

Yes it kind of amazes me that the setter penalizes for such a case which is ambigous.I was on the verge of solving C and then my solution got hacked due to this thing n==p and it never came to my mind that this could be the error.Really disgusting from a contestant point of view.That was shit of a testcase.

ever heard of the word "edge case"?

Yes it had been a edge case had the answer been Yes because there existed no "i" for which the constraint was valid.

There is no valid i so yes it is a period. but the question asked whether it is not a period. so the answer is the opposite that is No.

I got that already.Peace.

This is known as a vacuous truth.

Please explain C, can't really seem to get the editorialist's code also to mention the picture too!! :P

Ques C was Interesting.Good Contest this. cyand1317.

It is easier to solve D (in linear time for sorted input) if u divide points on basis of sign of x and v and u won't have to worry about fractions. http://codeforces.com/contest/989/submission/39163175

Actually dividing them into two sets according to the sign of

vis enough: 39187157.I think it should be *it > x in this line. while (it != minus.end() && (*it < x || wmax * (long long)(*it — x + l) <= abs(*it + x + l)))

No, it shouldn't.

@Jakube how did you derive the formula you used to check for valid pairs?

To be honest, only by reading the editorial. I used the same formula: .

But I don't see why the editoral then goes further distinguishing cases. From the sketch, (and the fact that the slope is less or equal than 45˚) is it really obvious that it isn't necessary. For each

x_{u}just find the firstx_{v}that satisfies the condition, and then allx_{w}>x_{v}automatically satisfy the condition.@Jakube can you explain how you derive that then? I'm confused about why it is not x_v-x_u+l on the left side, since x_v > x_u...

Sorry, it should be .

I just copied it from the editorial, and it seems like they have it wrong too.

Fixed now, thanks for pointing out.

my solution for CMy solution on C with input

100 100 100 100

not fine,but can accepted! :)

picthe prettiest one so far

My C solution's pictureThanks for your efforts :)

My picture for C (test 100 100 100 100):

PictureThis is pretty compact!

Thanks for this super-ultra-hyper-mega-meta-great-delicious-wonderful contest cyand1317 !

hope every time editorial is this quick

IN EDITORIAL OF E -> can you please explain this line "For each l, we should calculate the average of f(m−1)u such that the u-th point lies on l"

1 more ques.. IN the code of E what have u used GCD function for in struct line?

GCD is used to normalize the equation of the line in order to remove duplicates. This is not the only way, though.

The sentence above means, for example, if points

A,B,Clie on a certain linel, then the final probability is iflis chosen.thanks man.. :)0

My code runs perfectly okay on test 18 of B but it is giving an WA on test case 18. I am using g++ compiler on my pc. Can't understand why, since the output it produces in the test case should not be produced by program logic.Submission link : My Submission

Any insight would be helpful.

Thanks!!!

To explain why:

diff = n — p => 1 (for n = 3 & p = 2) for (int i = 0; i < diff; ++i) runs only once flag == false (since v[0] = 1 and v[2] = 0 output is "No" which is produced by my compiler but WA on codeforces. Can't understand...

PLEASE HELP!try debugging in custom invocation.

actually No is the wrong answer correct answer in 100.

Here's my C for input

`100 60 13 1`

Very fun question, good job cyand1317 :)

(My solution handles 1 ≤

a,b,c,d≤ 145.)This is the simplest to understand of all solutions but maximum number of components can only be 145 :)

With a pattern like this you can handle cases with a,b,c,d <= 385.

Nice insight! This can be modified to achieve 577.

Hope this makes sense...↑ Maximum

↓ "Eating" strategy

Does this eating strategy really work? Because you eat almost the same number of two colors.

In the top-left area we have only eaten blue ones. It should be easy to eat yellow and pink ones then.

We can do this for each area separately, eating an arbitrary number of each colour, so I think it does work.

We also ate yellow ones.

Oh wait, i missed something.

You can also use the middle vertical strip. Then you can do a,b,c,d<=600

Oh great!

()

problem D 2 10 100 2 1 1 -1 answer should be 1 but the standard puts 0 it shouldn't be xu<xv but xu<xv+l(?)

In the problem, no clouds should intersect at the beginning. The model solution doesn't handle cases where they initially intersect.

Mine is

a little bittoo complicated.A = 100, B = 90, C = 70, D = 50criesmy solution

You are so strong!

For those looking for an idea to solve problem C, this is a really simple solution. Feel free to check my submission if you want. The code works fine even for a,b,c,d <= 300. This is the case where A = B = C = D = 100 :)

Thanks to the writer! I love this contest!

My solution to E is actually in

O(n^{4}+ 30n^{3}+qn^{3})-time, where 30 is the laziness cutoff mentioned in the editorial. It passed the system test just because I was lucky :) http://codeforces.com/contest/989/submission/39167167I enjoyed this contest very much. Thanks!

You are excellent!! I also know a strange solution..

Because of the convergence of probability , we can make the

mino more than 60 .So we can get the probability by dp and brute force. And it can also pass the system test with high speed.

Forgive my poor English...

http://codeforces.com/contest/989/submission/39180094 This is my solution for Div 2-B , I think it will also work for bonus-3(n<=10^5), but I am not sure,please correct me if i am wrong .

Thanks in advance :)

You need, in bonus.3, to cope also with bonus.2.

Okay , I didn't know that , thanks

Sorry if I misunderstood you ^_^. I meant by my reply that not just the constraint on range of

nwas added in bonus.3, but also they added that you need to print the lexicographically minimum string if the answer is notNO.And as I saw from your code, it doesn't cope with bonus.3, because it doesn't print the "lexico. mini."

And for solving this, I suggest to replace each '.' with '0' (after making sure that the answer is not

NO) then iterate over the string from index 0 ton-p- 1 (inclusive) (indexing from 0) to see if there is an indexithat setisfys[i]! =s[i+p].If there is, then this is the answer, because we shouldn't change any character other than the dots

andthis string isnotp-periodic.If no, we should iterate over the string from right to left, and the first index we see and it was a dot before replacing dots with zeros, we should change it to '1', and the resulting string is the answer.

Hode my answer is correct :)

Please cyand1317, judge this solution for bonus.3 in problem B ^_^.

thanks for the solution :)

Quite close — try this :)

True. I need when I iterate from right to left to check for the first index

ithat setisfies both following two condition:1)

iin [0,n-p- 1]or[p,n- 1].2)

s[i] = '.' before the replacement.True?

Thank you very much :)

True ^ ^

Problem E turns out to be an exact Markov chain problem xD

plz explain the problem

let

each entry represent the probability (ex : 1 → 2 is the probability of going from 1 to 2)

Then,

A^{2}=(this one is bit hard to recognize, by the way.)

By generalization,

where ... can be any sequence of

n- 1 verticesThe answer is

MAX_{line}(sum-of-the- (row,column)[M_{line}*A^{m - 1}]) whereM_{line}is initial state of for each line and (row=index of vertices belongs to initial line), (column=vertex index of destination) (i'm sorry this must be hard to understand, but this is my best explanation) (and with some optimizations originally written in editorial)You can google 'markov chain' for much more elegant explains.

nice,thanks

Can someone please explain the solution (visualization) of problem D.

Think x axis as position and y axis as time. then,

For moon,

x=ywFor cloud with speed

s,x=sy+x_{o}andx=sy+x_{o}+lwheresis 1 or -1The idea is simple:

Implementation is here: http://codeforces.com/contest/989/submission/39190964

how did you created the above image?

I used below link but it is giving me boundaries and grid borders

https://golovanov399.github.io/grid/rect_grid_draw.htm

Read editorial solution for problem C :)

solution for (100 100 100 100) Full code at — http://codeforces.com/contest/989/submission/39193422 Interesting problem!! :)

http://codeforces.com/contest/989/submission/39194022

With a slight change, up to 183 zones of each color will work, giving out a table of 50 * 48

My solution for "100 100 100 100":

Output33 44

CACACACACACDBDBDBDBDBDACACACACACABDBDBDBDBDB AAAAAAAAAAABBBBBBBBBBBCCCCCCCCCCCDDDDDDDDDDD CACACACACACDBDBDBDBDBDACACACACACABDBDBDBDBDB AAAAAAAAAAABBBBBBBBBBBCCCCCCCCCCCDDDDDDDDDDD CACACACACACDBDBDBDBDBDACACACACACABDBDBDBDBDB AAAAAAAAAAABBBBBBBBBBBCCCCCCCCCCCDDDDDDDDDDD CACACACACACDBDBDBDBDBDACACACACACABDBDBDBDBDB AAAAAAAAAAABBBBBBBBBBBCCCCCCCCCCCDDDDDDDDDDD CACACACACACDBDBDBDBDBDACACACACACABDBDBDBDBDB AAAAAAAAAAABBBBBBBBBBBCCCCCCCCCCCDDDDDDDDDDD CACACACACACDBDBDBDBDBDACACACACACABDBDBDBDBDB AAAAAAAAAAABBBBBBBBBBBCCCCCCCCCCCDDDDDDDDDDD CACACACACACDBDBDBDBDBDACACACACACABDBDBDBDBDB AAAAAAAAAAABBBBBBBBBBBCCCCCCCCCCCDDDDDDDDDDD CACACACACACDBDBDBDBDBDACACACACACABDBDBDBDBDB AAAAAAAAAAABBBBBBBBBBBCCCCCCCCCCCDDDDDDDDDDD CACACACACACDBDBDBDBDBDACACACACACABDBDBDBDBDB AAAAAAAAAAABBBBBBBBBBBCCCCCCCCCCCDDDDDDDDDDD CACACACACACDBDBDBDBDBDACACACACACABDBDBDBDBDB AAAAAAAAAAABBBBBBBBBBBCCCCCCCCCCCDDDDDDDDDDD CACACACACACDBDBDBDBDBDACACACACACABDBDBDBDBDB AAAAAAAAAAABBBBBBBBBBBCCCCCCCCCCCDDDDDDDDDDD CACACACACACDBDBDBDBDBDACACACACACABDBDBDBDBDB AAAAAAAAAAABBBBBBBBBBBCCCCCCCCCCCDDDDDDDDDDD CACACACACACDBDBDBDBDBDACACACACACABDBDBDBDBDB AAAAAAAAAAABBBBBBBBBBBCCCCCCCCCCCDDDDDDDDDDD CACACACACACDBDBDBDBDBDACACACACACABDBDBDBDBDB AAAAAAAAAAABBBBBBBBBBBCCCCCCCCCCCDDDDDDDDDDD CACACACACAADBDBDBDBDBBACACACACACCBDBDBDBDBDD AAAAAAAAAAABBBBBBBBBBBCCCCCCCCCCCDDDDDDDDDDD CACACACACAADBDBDBDBDBBACACACACACCBDBDBDBDBDD AAAAAAAAAAABBBBBBBBBBBCCCCCCCCCCCDDDDDDDDDDD CACACACACAADBDBDBDBDBBACACACACACCBDBDBDBDBDD

My solution for "50 30 25 10":

Output33 44

CACAAAAAAAADBBBBBBBBBBACACACCCCCCBDBDDDDDDDD AAAAAAAAAAABBBBBBBBBBBCCCCCCCCCCCDDDDDDDDDDD CACAAAAAAAADBBBBBBBBBBACACACCCCCCBDBDDDDDDDD AAAAAAAAAAABBBBBBBBBBBCCCCCCCCCCCDDDDDDDDDDD CACAAAAAAAADBBBBBBBBBBACACACCCCCCBDBDDDDDDDD AAAAAAAAAAABBBBBBBBBBBCCCCCCCCCCCDDDDDDDDDDD CACAAAAAAAADBBBBBBBBBBACACACCCCCCBDBDDDDDDDD AAAAAAAAAAABBBBBBBBBBBCCCCCCCCCCCDDDDDDDDDDD CACAAAAAAAADBBBBBBBBBBACACACCCCCCBDBDDDDDDDD AAAAAAAAAAABBBBBBBBBBBCCCCCCCCCCCDDDDDDDDDDD CACAAAAAAAADBBBBBBBBBBACACACCCCCCBDBDDDDDDDD AAAAAAAAAAABBBBBBBBBBBCCCCCCCCCCCDDDDDDDDDDD CACAAAAAAAADBBBBBBBBBBACACACCCCCCBDBDDDDDDDD AAAAAAAAAAABBBBBBBBBBBCCCCCCCCCCCDDDDDDDDDDD CAAAAAAAAAADBBBBBBBBBBACACACCCCCCBDBDDDDDDDD AAAAAAAAAAABBBBBBBBBBBCCCCCCCCCCCDDDDDDDDDDD CAAAAAAAAAADBBBBBBBBBBACACACCCCCCBDBDDDDDDDD AAAAAAAAAAABBBBBBBBBBBCCCCCCCCCCCDDDDDDDDDDD CAAAAAAAAAABBBBBBBBBBBACACACCCCCCBDBDDDDDDDD AAAAAAAAAAABBBBBBBBBBBCCCCCCCCCCCDDDDDDDDDDD CAAAAAAAAAABBBBBBBBBBBACACACCCCCCBDBDDDDDDDD AAAAAAAAAAABBBBBBBBBBBCCCCCCCCCCCDDDDDDDDDDD CAAAAAAAAAABBBBBBBBBBBACACACCCCCCBDBDDDDDDDD AAAAAAAAAAABBBBBBBBBBBCCCCCCCCCCCDDDDDDDDDDD CAAAAAAAAAABBBBBBBBBBBACACACCCCCCBDDDDDDDDDD AAAAAAAAAAABBBBBBBBBBBCCCCCCCCCCCDDDDDDDDDDD CAAAAAAAAAABBBBBBBBBBBACACACCCCCCBDDDDDDDDDD AAAAAAAAAAABBBBBBBBBBBCCCCCCCCCCCDDDDDDDDDDD CAAAAAAAAAABBBBBBBBBBBACACACCCCCCBDDDDDDDDDD AAAAAAAAAAABBBBBBBBBBBCCCCCCCCCCCDDDDDDDDDDD CAAAAAAAAAABBBBBBBBBBBACACCCCCCCCBDDDDDDDDDD AAAAAAAAAAABBBBBBBBBBBCCCCCCCCCCCDDDDDDDDDDD CAAAAAAAAAABBBBBBBBBBBACACCCCCCCCBDDDDDDDDDD

Maybe in future I make it in images, but now it only text(

In problem D editorial: "For a pair of rightwards-moving cloud u and leftwards-moving cloud v, their intersection in the diagram has a top corner of ... ", is y coordinate correct? I think it should be (x_v + l — x_u) / 2 instead of (x_u — x_v + l) / 2 (x_u < x_v, right?)

Yes, I think it's a typo.

Fixed, thanks!

My sol for C 100 100 100 100

Spoilersol for 1 1 1 1

Spoilercyand1317 Sir, I know basic programming like i am able to solve Div2 A,B, C(sometimes)...... Can you tell me what all topics(and from where) i should do to improve so that i will be able to solve div2 C and Div2 D much easily....... Thankyou...

Personally I would suggest this blog (see bold text at the end). Also FYI there is this blog.

I love your D, such a cuuuuuuute and beeeeeeeeeautiful idea!

Rua~ cyand1317

Thaaaaaaank yooooooooou!

It's not duliu! Not ever! > <

Surely not DuLiu, it's kinda standard of neat and fresh problems.

My simple solution! INPUT: 77 33 22 144

no time to read the story...

Super cool contest.!! This contest helped a lot of participants to improve their ratings as the questions were well-framed and logical.

Bonus. DSolve for intervals ofvariouslengths, with possible intersection at the beginning.The only difference is we have

l_{u}andl_{v}in the inequality instead of a unifiedl, right?UPD:got itVideo solution for Problem C: https://youtu.be/BLnY8UrSR_o

989C - Флуоресцентный туман

Codeforces Round #487 (Div. 2)

I get wrong answer in Pro E for Error of accuracy, and my 1.5 hours run out. Maybe we should pay more attention to the calculation of plane geometry...

For problem E instead of taking average I did

cases:

1) M turns starting from point in S 2) First turn from point not in S + M-1 turns starting from point in S

and I took max of resulting vector

It seems precision is worse, and it failed seventh test case by 7*10^-6 (error margin is 10^-6). Now is it just precision problem or is there some logical error. And how to improve the accuracy?