ALTER - Editorial

editorial
, ,
1

Problem Link:

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

Author: Soumyadeep Pal
Tester: Danny Mittal
Editorialist: Ritesh Gupta

DIFFICULTY:

Simple

PREREQUISITES:

Math

PROBLEM:

Alice and Bob are two friends. Initially, the skill levels of them are zero. They work on alternative days, i.e one of Alice and Bob works on the odd-numbered days (1, 3, 5, \dots) and the other works on the even-numbered days (2, 4, 6, \dots). The skill levels of Alice and Bob increase by A, B respectively on the days they work.

Determine if it is possible that the skill levels of Alice and Bob become exactly P, Q respectively on some day.

QUICK EXPLANATION:

As both Alice and Bob will get same A and B skill points for working on any day. So, they can achieve only multiple of A and B respectively at any day. Now, either their score will become P and Q on any odd day or even day. If their skill level become as given on even day then both works for same number of days which implies that P/A = Q/B else the person who start the work on odd day, will contribute one more day then other which implies that P/A = Q/B + 1 if Alice start working on odd day or P/A = Q/B - 1 if Bob start working on odd day .

EXPLANATION:

We can solve the problem with these observations :

  • As each person will gain same amount of skill set after working for a day that means the skill set values achieved at any day should be multiple of their respective increase value (A in case of Alice and B in case of Bob).
    • P should be the multiple of A or P\%A == 0
    • Q should be the multiple of B or Q\%B == 0
  • If their skill level become the desired ones on even day that means both of them worked for same amount of days irrespective of who started working first or mathematically P/A == Q/B
  • If their skill level become the desired ones on odd day that means the person who started working first will be a day ahead compare to the other person.
    • If Alice started working first then P/A == Q/B + 1
    • If Bob started working first then P/A == Q/B - 1

TIME COMPLEXITY:

O(1) per testcase

CODE:

Setter (C++) 
#include
using namespace std;

void solve(int tc) {
  int a, b, p, q;
  cin >> a >> b >> p >> q;
  if (p % a == 0 && q % b == 0 && abs(p / a - q / b) <= 1) {
    cout << "YES\n";
  } else {
    cout <> t;
  for (int i = 1; i <= t; i++) solve(i);
  return 0;
}
Tester (Kotlin) 
import java.io.BufferedInputStream
import kotlin.math.abs

const val BILLION = 1000000000

fun main(omkar: Array) {
    val jin = FastScanner()
    repeat(jin.nextInt(1000)) {
        val a = jin.nextInt(BILLION, false)
        val b = jin.nextInt(BILLION, false)
        val p = jin.nextInt(BILLION, false)
        val q = jin.nextInt(BILLION)
        println(if (p % a == 0 && q % b == 0 && abs((p / a) - (q / b)) <= 1) "yEs" else "nO")
    }
    jin.endOfInput()
}

class InvalidInputException(message: String): Exception(message)

class FastScanner {
    private val BS = 1 shl 16
    private val NC = 0.toChar()
    private val buf = ByteArray(BS)
    private var bId = 0
    private var size = 0
    private var c = NC
    private var `in`: BufferedInputStream? = null
    private val validation: Boolean

    constructor(validation: Boolean) {
        this.validation = validation
        `in` = BufferedInputStream(System.`in`, BS)
    }

    constructor() : this(true)

    private val char: Char
        private get() {
            while (bId == size) {
                size = try {
                    `in`!!.read(buf)
                } catch (e: Exception) {
                    return NC
                }
                if (size == -1) return NC
                bId = 0
            }
            return buf[bId++].toChar()
        }

    fun validationFail(message: String) {
        if (validation) {
            throw InvalidInputException(message)
        }
    }

    fun endOfInput() {
        if (char != NC) {
            validationFail("excessive input")
        }
        if (validation) {
            System.err.println("input validated")
        }
    }

    fun nextInt(from: Int, to: Int, endsLine: Boolean = true) = nextLong(from.toLong(), to.toLong(), endsLine).toInt()

    fun nextInt(to: Int, endsLine: Boolean = true) = nextInt(1, to, endsLine)

    fun nextLong(endsLine: Boolean): Long {
        var neg = false
        c = char
        if (c !in '0'..'9' && c != '-' && c != ' ' && c != '\n') {
            validationFail("found character other than digit, negative sign, space, and newline, character code = ${c.toInt()}")
        }
        if (c == '-') {
            neg = true
            c = char
        }
        var res = 0L
        while (c in '0'..'9') {
            res = (res shl 3) + (res shl 1) + (c - '0').toLong()
            c = char
        }
        if (endsLine) {
            if (c != '\n') {
                validationFail("found character other than newline, character code = ${c.toInt()}")
            }
        } else {
            if (c != ' ') {
                validationFail("found character other than space, character code = ${c.toInt()}")
            }
        }
        return if (neg) -res else res
    }

    fun nextLong(from: Long, to: Long, endsLine: Boolean = true): Long {
        val res = nextLong(endsLine)
        if (res !in from..to) {
            validationFail("$res not in range $from..$to")
        }
        return res
    }

    fun nextLong(to: Long, endsLine: Boolean = true) = nextLong(1L, to, endsLine)
}
Editorialist (C++) 
#include 
using namespace std;

int main() {
	int t;
	cin >> t;
	
	while(t--) {
	   int a,b,p,q;
	   cin >> a >> b >> p >> q;
	   
	   if (p%a != 0 || q%b != 0) {
	      cout << "NO\n";
	   } else if (p/a == q/b || p/a == q/b - 1 || p/a == q/b + 1) {
	      cout << "YES\n";
	   } else {
	      cout << "NO\n";
	   }
	}
	return 0;
}