CS academy Round 68

Finished another full contest set.

Problem link

B Integer Coords

Given ranges for $X$ and $Y$, choose two points so that the line segment connecting them contains exactly $K$ lattice points. Count the choices.

The number of lattice points on the segment between $(x1,y1)$ and $(x2,y2)$ is $gcd(abs(x1-x2),abs(y1-y2)) + 1$.

int n;
void solve()
{
	int n, m, k;
	cin >> n >> m >> k;
	int ans = 0;
	repp(i1, 0, n)
	{
		repp(j1, 0, m)
		{
			repp(i2, i1, n)
			{
				repp(j2, (i2==i1?j1:0), m)
				{
					int d1 = abs(i1 - i2);
					int d2 = abs(j1 - j2);
					int cnt = 0;
					if (d1 == 0)
					{
						cnt = d2 + 1;
					}
					else if (d2 == 0)
					{
						cnt = d1 + 1;
					}
					else
					{
						cnt = gcd(d1, d2) + 1;
					}
					if (cnt == k)
					{
						ans++;
					}
				}
			}
		}
	}
	cout << ans ;
}

C Right Triangles

Given $N$ points $(x,y)$, each point together with $(0,0)$ and $(x,0)$ forms a right triangle. For every such triangle, count how many points it contains.

Sort by x-coordinate, then count earlier points with a smaller slope.

int n;
struct no
{
    int le;
    int ri;
    int id;
}node[maxn];

bool cmp(no a,no b)
{
    return a.le<b.le;
}
ll num[maxn];
int lowbit(int x)
{
    return x&(-x);
}
ll getsum(ll x)
{
    ll ans = 0;
    while(x>0)
    {
        ans+=num[x];
        x-=lowbit(x);
    }
    return ans;
}
ll add(int x,int v)
{
    int up=maxn-1;
    while(x<=up)
    {
        num[x]+=v;
        x+=lowbit(x);
    }
    return x;
}

int ans[maxn];
void solve()
{
    sa(n);
    repp(i,1,n)
    {
        sa(node[i].le);
        sa(node[i].ri);
        node[i].id = i;
    }
    sort(node+1,node+n+1,cmp);

    repp(i,1,n)
    {
        int k = getsum(node[i].ri-1);
        ans[node[i].id] = k;
        add(node[i].ri,1);
    }
    repp(i,1,n)
    {
        printf("%d\n",ans[i]);
    }
}

D Triangular Updates

Given a rectangle, apply updates on right triangles and output the final values in the rectangle.

I could not figure it out. Ouch.

As shown in the diagram, this update is enough.

ll val[maxn][maxn];
ll val2[maxn][maxn];
ll ad[maxn][maxn],sub[maxn][maxn];

void solve()
{
    int n,q;
    sa(n),sa(q);
    repp(i,1,q)
    {
        int R,C,L,S;

        sa(R);
        sa(C);
        sa(L);
        sa(S);
        ad[R][C] += S;
        ad[R+L][C] -= S;
        sub[R+L][C+1] -= S;
        sub[R+L][L+C+1] += S;
//        DE(R)
//        DE(C)
//        DE(R+L)
//        DE(C)
//
//        DE(L+C+1)
//        rep(x,R,R+L)
//        {
//            repp(y,C,x-R+C)
//            {
//                val2[x][y] += S;
//            }
//        }
    }
    repp(i,1,n)
    {
        repp(j,1,n)
        {
            sub[i][j] += sub[i][j-1];
        }
    }
    repp(j,1,n)
    {
        repp(i,1,n)
        {
            ad[i][j] += ad[i-1][j];
        }
    }
    repp(i,1,n)
    {
        repp(j,1,n)
        {
            val[i][j] = ad[i][j] + sub[i][j];
            if(i>1&&j>1)val[i][j] += val[i-1][j-1];
            printf("%lld ",val[i][j]);

        }
        printf("\n");
    }
//    cout<<endl<<endl;
//    repp(i,1,n)
//    {
//        repp(j,1,n)
//        {
//            printf("%lld ",val2[i][j]);
//
//        }
//        printf("\n");
//    }
}

E Sliding Product Sum

There is an array from $1$ to $N$ $(N < 10^{18})$. Compute the sum of products of all contiguous subarrays with length at most $K$.

The sum of products of consecutive groups of $K$ numbers from $1$ to $n$ is
$$
\frac{(n-i+1)(n-i+2)…(n+1)}{(i+1)}
$$
For example 1*2 + 2*3 + 3*4 + 4*5 + … (n-1)*n = (n-1)*n*(n+1)/2

Then I used Python directly for this problem.

#import sys

def cal(n,x):
	ans = 1
	for i in range(x + 1):
		ans *= (n + 1 - i)
	return ans / (x + 1)

if __name__ == "__main__":
	n,m,k = map(int,raw_input().split())
	ans = 0
	for i in range(1,m+1):
		ans += cal(n,i)
		ans %= k
	print ans