SPCP4 - Editorial

editorial
,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: kg_26, shanmukh29
Tester: raysh07
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

N students go on a trip. X of them are boys, and the remaining are girls.
Boys and girls will form groups of K among themselves for trekking.
Among the remaining people, one boy will pair up with one girl for a bonfire dance.
How many people will do neither activity?

EXPLANATION:

This is a fairly straightforward math task, only requiring you to parse the statement step-by-step.
Let’s go over all the details.

  • There are N students, and X of them are boys. This means N-X of them are girls.
    Let Y = N-X for convenience.
  • The boys will make groups of K till them can’t anymore — which can only happen when there are less than K boys remaining.
    So, we need to keep subtracting K from X till we reach something \lt K.
    The value we reach is exactly X\ \%\ K, the remainder when X is divided by K.
  • Similarly, there will be Y\ \% \ K girls remaining.
  • Now, one boy must pair up with one girl.
    It’s easy to see that the number of pairs created this way will be exactly \min(X\ \%\ K, Y\ \%\ K).
  • The answer is just the number of students remaining - which from above we know is just
(X\ \%\ K) + (Y\ \%\ K) - 2\cdot \min(X\ \%\ K, Y\ \%\ K)

Alternate formulas include |(X\ \%\ K) - (Y\ \%\ K)| and
\max(X\ \%\ K, Y\ \%\ K) - \min(X\ \%\ K, Y\ \%\ K), they all describe the same quantity.

TIME COMPLEXITY:

\mathcal{O}(1) per testcase.

CODE:

Author's code (C++) 
#include<iostream>
using namespace std;
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n,boys,k;
        cin>>n>>boys>>k;
        int girls=n-boys;
        boys%=k;
        girls%=k;
        cout<<max(boys,girls)-min(boys,girls)<<"\n";
    }
}
Editorialist's code (Python) 
for _ in range(int(input())):
    n, x, k = map(int, input().split())
    remb, remg = x%k, (n-x)%k
    dif = abs(remb - remg)
    print(dif)