You are not logged in. Please login at www.codechef.com to post your questions!

×

MGAME - EDITORIAL

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 ;)

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 :D

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 :D

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. :)

This question is marked "community wiki".

asked 14 Jan, 15:59

taran_1407's gravatar image

6★taran_1407
4.0k31104
accept rate: 22%

edited 14 Jan, 21:42

l_returns's gravatar image

5★l_returns
1.6k211


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;
}
link

answered 15 Jan, 09:28

mcsinyx's gravatar image

3★mcsinyx
314
accept rate: 0%

wow... nice solution :)

(15 Jan, 13:11) l_returns5★

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

(21 Jan, 16:00) aashutosh0013★
#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";
        }



    }

}
link
This answer is marked "community wiki".

answered 17 Jan, 21:19

saumya_agni's gravatar image

2★saumya_agni
11
accept rate: 0%

edited 18 Jan, 16:24

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×3,820
×900
×728
×348
×112
×30

question asked: 14 Jan, 15:59

question was seen: 3,050 times

last updated: 31 Jan, 15:35