Comments

In editorial C, What d(C) means?

i'm struggling with problem C.

here is my approach.

[solve for N]

if N <= 1: return 0

if LCM(A[1] ~ A[N]) overflow A[N]: return N

if LCM(A[1] ~ A[N — 1]) == A[N]: find maximum length subsequence its LCM is not A[N] <- brute force

if LCM(A[1] ~ A[N — 1]) < A[N]: [solve for N — 1]

https://mirror.codeforces.com/contest/1977/submission/263102096

what is wrong with my code

thank's for your reply.

i proved this by different way!

we can generalize "non stripe pattern" as a "(stripe pattern) — (hole)" when hole is not stripe.

and there is a two case.

  1. holes appear in first column.

  2. no hole appears in first column.

1st case ex)

xxxxxx

001000 <- 1 in this column is bad

010000

110011

010001

(x is color which is not 1 (possibly 0))

then

-> there exists always bad color 1 in column which color 1 is appear for the first time.

2nd case ex)

xxxxxx

111111

111111

010000 <- some 0 in this column is bad

110011

010001

then

-> there exists always bad color 0 in column which color 0 is appear for the first time.

and this model include all possible region -> proved!

I get stuck proving only stripe pattern make all cell to have at least 3 neighbors. (Div.2 C)

Is there a easy way to prove it?