Introduction

Yesterday, I participitated in 186th Atcoder beginners contest. I performed good on first 5 problems but then I on last problem I did something foolish and couldn’t complete it.

Now lets jump directly to Explations/Solutions

Solutions

Problem - A

Problem Link

if we put X boxes than W*X <= N

=> X <= (N/W);

=> Xmax = floor(N/W);

code

Atcoder solution Link

Problem - B

Problem Link

we need to decrease each cell to the minimum of whole matrix

code

Atcoder solution Link

Problem - C

Problem Link

we can simply interate from 1 to N and check does it check the given condition

code

Atcoder solution Link

Problem - D

Problem Link

we need to find $ \sum_{i=1}^n \sum_{j=i+1}^n abs(A[i]-A[j]) $

we can notice that absolute difference of every ordered pair (i,j) will be counted once.

As abs(A[i]-A[j]) == abs(A[j]-A[i]) and every ordered pair need to be counted hence array can be reordered as we wish.

So if we sort the array the we need to just $$ \sum_{i=1}^n ( i*A[i] - \sum_{j=1}^iA[j]) $$

which is equals to

$$ \sum_{i=1}^n i*A[i] - PF[i] $$ where PF = prefixSum array

code

Atcoder solution Link

Problem - E

Problem Link

We need to find (S+K*x)%N = 0

=> (K*x)%N = (-S)%N = A;

=> K*x = A mod N - eq1

As this can also be written as Kx = NI1 + A - eq2

let g = gcd(A,K,N)

we can divide eq2 by g

let K' = K/g , N' = N/g , A' = A/g

eq1 becomes K'*x = A' mod N'

$K^{-1}$ be the multiplicative modulus of K' under N',

multiply both side $K^{-1}$ it becomes

x = ($K^{-1}$*A')%N

Now only thing left is to check if multiplicative modulus of K' exist or not.

$K^{-1}$ under N' exist if K' and N' are co-prime ( gcd(K],N')==1 )

if $K^{-1}$ exist then modified equation for sure has exactly one solution but original equations will have exactly g solutions , see this ,

$$ x = (x' + i*N')%N for i = 0 to g-1 $$

if $K^{-1}$ does not exist then it can be proven that solution does not exist

code

Atcoder solution Link

Problem - F

Problem Link

000000X0X0

00X0000X0X

000XX0X000

0000000000

00000X0000

For each row find the first X and are the cell before it are visible. Same thing can be done for each column but there will be some double counting that can be handled using fenwick tree.

code

Atcoder solution Link