Original Problem



  • Given and which are the width and height of a rectangle. We want to check is it possible to form a new rectangle after making a straight cut parallel of one side of the given rectangle
  • There are a few constraints here
    1. The new sides after cutting should still be Integer (整数)
    2. The area should remain unchanged
    3. The new sides should not be the given and , if the same, we aren’t creating a new rectangle


  • Given and , we can conclude that the area of the rectangle is
  • When we cut, we can choose to cut from one side, either cut (cut parallel to the side) or (cut parallel to the side)
  • The position of cutting a side is also fixed - right in the middle of the side we are cutting, so it is either or , because if we don’t cut in the middle, there is no way for us to have a chance to form a rectangle. When we cut, we must make sure the side we cut is placed in parallel in the new rectangle, or we will get back the same rectangle. An example is shown below
  • Since the new side is either or , and we need to make sure the area of the new rectangle remains unchanged . If the side isn’t even, we are sure we can’t cut it
  • Let be even, when we cut it into half, we obtain , the another side will be with basic algebraic operations.

One Catch!

If , then . We are basically getting back the same rectangle!


  • We can obtain a new rectangle by making a straight line cut parallel to one side of the rectangle if and only if it meets the following 2 conditions
    1. We need to make sure we cut the side in two equal size to have a valid rectangle. Thus, the side we are cutting is even, since we want the side of the rectangle to be integer
    2. After cutting the side, the side that is cut can’t have the same value as the side that we didn’t cut

Space & Time Analysis

The analysis method we are using is Algorithm Complexity Analysis

Space - O(1)

  • Ignore input size & language dependent space
  • We just keeping track a boolean value for the answer

Time - O(1)

  • We are only making use a few arithmetic operations and boolean checking here


1st Attempt (Java)

import java.util.*;
import java.io.*;
public class Solution {
  static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 // Write your solution here
  public static void solve() throws IOException {
    StringTokenizer st = new StringTokenizer(br.readLine());
    int a = Integer.parseInt(st.nextToken());
    int b = Integer.parseInt(st.nextToken());
    boolean isThereNew = false;
    if (a%2 == 0 && a/2!=b) isThereNew = true;
    if (b%2 == 0 && b/2!=a) isThereNew = true;
    System.out.println(isThereNew ? "YES" : "NO");
  public static void main(String[] args) throws IOException {
    int t = Integer.parseInt(br.readLine());
    while(t-- > 0) {

Personal Reflection

  • Why it takes so long to solve: Overwhelmed by matrix, not sure where to start
  • What you could have done better: Visualisation of the cutting we can perform on the rectangle in the brain, and abstract problems into math symbols
  • What you missed: NIL
  • Ideas you’ve seen before: number theory
  • Ideas you found here that could help you later: number theory, the visualisation of matrix operation in the brain and abstract problems into math symbols
  • Ideas that didn’t work and why: Finding all the possible Factor of the area, and check if the is a factor that isn’t or , if yes then we can create a new rectangle. Otherwise, no. This doesn’t work, because it takes to find all factors and it will TLE