MGAME - EDITORIAL

general
, , , , ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2

Setter: Smit mandavia
Tester: Xiuhan Wang
Editorialist: Taranpreet Singh

DIFFICULTY:

Easy

PREREQUISITES:

Modulo operator and Basic Combinatorics.

PROBLEM:

Given two integers N and P, suppose the maximum value of (((N \bmod i) \bmod j) \bmod k ) \bmod N be M where i, j, k \in [1, P], Find the number of ways to select i, j, k \in [1, P] such that (((N \bmod i) \bmod j) \bmod k ) \bmod N equals M.

SUPER QUICK EXPLANATION

  • The maximum value of N \bmod x where x \in [1,N], if N is odd, is (N-1)/2 when x = (N+1)/2, and if N is even, is N/2-1 when x = N/2+1.
  • We can achieve (((N \bmod i) \bmod j) \bmod k ) \bmod N = M in three ways. Let x = \lceil (N+1)/2 \rceil
    • i = x and j,k > M.
    • i > N, j = x and k > M.
    • i, j > N and k = x.
      Each of this case can be easily computed.

EXPLANATION

First of all, Let is find this value M. It has to be less than min(i,j,k,N) which implies, M < N. Hence, if we want M > 0, we need (((N \bmod i) \bmod j) \bmod k) < N. So, We know for sure, that to maximize M, min(i, j, k) \leq N. Hence, we need maximum (((N \bmod i) \bmod j) \bmod k) < N and now we can ignore the last \bmod N.

So, The maximum N \bmod x can attain is \lfloor (N-1)/2 \rfloor. This happens when x = \lceil (N+1)/2 \rceil. It can be easily verified either by checking by hand, or writing a simple program :wink:

Now, try finding out number of ways (((N \bmod i) \bmod j) \bmod k) equals M. It can be approached in Simple case base analysis.

We can try all possible triplets of (i,j,k) and generalize them into three cases.

  • When i = \lceil (N+1)/2 \rceil and j,k > M
  • When i > N, j = \lceil (N+1)/2 \rceil and k > M
  • When i,j > N and k = \lceil (N+1)/2 \rceil

In all three cases, we can simply count the number of triplets (i, j, k) satisfying any condition and print the answer.

Corner Case

When N \leq 2, M = \lfloor (N-1)/2 \rfloor = 0. This is because we cannot achieve (((N \bmod i) \bmod j) \bmod k ) \bmod N > 0. So, all triplets (i, j, k) are valid.

Alternate solution - read at your own risk, you have been warned :smiley:

For those curious enough not to be satisfied with such solutions, there also exists a pattern based solution too, using basic math. Just use brute solution to find the first terms of series and solve using the pattern formed. Number 6 is important. Enjoy :smiley:

Time Complexity

Time complexity is O(1) per test case.

AUTHOR’S AND TESTER’S SOLUTIONS:

Setter’s solution
Tester’s solution
Editorialist’s solution

Feel free to Share your approach, If it differs. Suggestions are always welcomed. :slight_smile:

3 Likes
2

About the alternate solution, since this contest has no restriction, one could reference OEIS and came up with something like this:

#include <stdio.h>
#define sqr(x) ((x) * (x))

int main() {
	long long t, n, p, diff, u, v;
	scanf("%lld", &t);
	while(t--) {
		scanf("%lld %lld", &n, &p);
		if (n < 3) {
			printf("%lld\n", p * p * p);
			continue;
		}

		diff = p - n;
		if (diff % 2) {
			u = n / 2, v = diff/2;
			printf("%lld\n", (u+v*3+2)*(u+v*3+3) + v*(v+1)*3 + 1);
		} else {
			printf("%lld\n", sqr(p/2 + diff + 1) + sqr(diff)*3/4);
		}
	}
	return 0;
}
2 Likes
3

#include <bits/stdc++.h>
#define int long long int
using namespace std;

int32_t main() {
    int t;
    cin>>t;
    while(t--)
    {
        int n,p;
	    cin>>n>>p;
	    if(n==1||n==2)
	    cout<<p*p*p<<"\n";
	    else{
	    int i = n/2 + 1;
	    int af , tf , mf;
	    tf = p-n;
	    af = (p-n)*2 + i;
	    mf = (p-n+i)*(p-n+i);
	    cout<<af*tf+mf<<"\n";
	    }
	    
	    
	    
    }
	
}
4

wow… nice solution :slight_smile:

5

I tried similar approach but failed to formulate it properly, can you share how you found patter in odd number greater than 3.

6

I think my algo is same as the editorialist but why am i getting wrong answer…