VCAKE - Editorial

PROBLEM LINK:

Contest
Practice

Author: Kevin Atienza
Testers: Sergey Kulik and Vasya Antoniuk
Translators: Vasya Antoniuk (Russian), Sergey Kulik (Russian), Team VNOI (Vietnamese) and Hu Zecong (Mandarin)
Editorialist: Kevin Atienza

DIFFICULTY:

Simple

PREREQUISITES:

Modulo operation

PROBLEM:

Is it possible to cut an R\times C rectangular cake into pieces with areas M, K and J? You are only allowed to cut parallel to the sides, and pieces must remain rectangular with integer sides.

QUICK EXPLANATION:

  • If RC \not= M + K + J, the answer is No,
  • else, if M, K and J are divisible by R, the answer is Yes,
  • else, if M, K and J are divisible by C, the answer is Yes,
  • else, if M is divisible by R and K is divisible by (C - M/R), the answer is Yes,
  • else, if K is divisible by R and J is divisible by (C - K/R), the answer is Yes,
  • else, if J is divisible by R and M is divisible by (C - J/R), the answer is Yes,
  • else, if M is divisible by C and K is divisible by (R - M/C), the answer is Yes,
  • else, if K is divisible by C and J is divisible by (R - K/C), the answer is Yes,
  • else, if J is divisible by C and M is divisible by (R - J/C), the answer is Yes,
  • otherwise, the answer is No.

The first line checks whether the area is exactly what’s needed.
The second and third line checks for two horizontal or two vertical cuts.
The fourth to ninth lines check for one horizontal and one vertical cut.

EXPLANATION

First, for a cut to be possible, it must be the case that M + K + J constitutes the total area of the rectangle. But the total area is RC, so if RC \not= M + K + J, then the answer is immediately No. Thus, in the following, we can assume that RC = M + K + J.

Each cut splits one piece into two pieces, so that means we must perform exactly two cuts. The first cut splits the whole cake into two pieces. The second cut splits one of the pieces into two again. This means that, after the first cut, one of the pieces must have an area of exactly M, K or J. In other words, it must split the whole cake into two pieces of areas (M,K+J), (K,J+M) or (J,M+K).

When is it possible to cut an R\times C piece into two pieces with areas (A,B)? Well, you can cut either horizontally or vertically.

  • If you cut horizontally, then the pieces will have dimensions r_1\times C and r_2\times C, where r_1 + r_2 = R. Thus, the following must be true: A = r_1C and B = r_2C. In other words, A and B must be divisible by C.
  • If you cut horizontally, then the pieces will have dimensions R\times c_1 and R\times c_2, where c_1 + c_2 = C. Thus, the following must be true: A = Rc_1 and B = Rc_2. In other words, A and B must be divisible by R.

After that, we must split one of the pieces into two parts again, with specific areas. But since we know the dimensions of the piece, this is basically the same problem as above! Therefore, we now have all the tools required to write a complete solution.

We’ll describe it with Python. First, let’s write a function that performs the procedure above:

def possible_splits(R,C,A,B):
    # returns all possible dimensions of the second piece if we split an
    # R*C rectangle into pieces with areas A and B

    dimensions = []
    if A % C == 0 and B % C == 0:
        r2 = B / C
        dimension = (r2,C)
        dimensions.append(dimension)

    if A % R == 0 and B % R == 0:
        c2 = B / R
        dimension = (R,c2)
        dimensions.append(dimension)

    return dimensions

With this function, we can now answer a query:

def query(R, C, M, K, J):
    if R*C != M + K + J:  # wrong area
        return False

    # try three possibilities

    for r, c in possible_splits(R, C, M, K+J):
        if possible_splits(r, c, K, J):
            return True

    for r, c in possible_splits(R, C, K, J+M):
        if possible_splits(r, c, J, M):
            return True

    for r, c in possible_splits(R, C, J, M+K):
        if possible_splits(r, c, M, K):
            return True

    # nothing worked
    return False

This first checks if RC = M + K + J, and if true, tries out all three possible initial splits: (M,K+J), (K,J+M) or (J,M+K). After that, we can simply call the query function to print the answers!

for cas in xrange(input()):
    R, C, M, K, J = map(int, raw_input().strip().split())
    print 'Yes' if query(R, C, M, K, J) else 'No'

Here is a more compact version:

def possible_splits(R,C,A):
    B = R*C - A
    if A % C == 0 and B % C == 0: yield B / C, C
    if A % R == 0 and B % R == 0: yield R, B / R

def query(R, C, M, K, J):
    if R*C != M + K + J:  # wrong area
        return False

    # try three possibilities
    for A, B in [(M, K), (K, J), (J, M)]:
        for r, c in possible_splits(R, C, A):
            if any(possible_splits(r, c, B)):
                return True

    # nothing worked
    return False

The changes here are:

  • We made use of Python’s yield statement to not have to collect the dimensions in a dimensions array.
  • We removed the B parameter in possible_splits, because it can be extracted from the other parameters from the equation RC = A + B.

Time Complexity:

O(1)

AUTHOR’S AND TESTER’S SOLUTIONS:

setter
tester 1
tester 2

Can someone have a look at my solution and point out the mistake.I have tried many times and probably i am missing out something silly… https://www.codechef.com/viewsolution/10558112

1 Like

Can someone have a look at my solution and point out the mistake. https://www.codechef.com/viewsolution/10559849

Solved by roughly 1400 out of 3500 teams. So around 2000 teams didn’t even solve it. 3 out of top 5 global teams have got 1 WA. Took the best teams around 15 minutes to solve. Cake walk ? Sure! I feel sometimes these tags are just set to patronize the contestants.

8 Likes

Suppose m is divisible by both r and c. Your code only considers first possibility i.e. m % r == 0. I suggest you form a test case around this.

1 Like

can some one help me with this code, it’s getting WA.i’m not able to find my problem.
https://www.codechef.com/viewsolution/10579652
please help.

Thanks for responding. I checked for some test cases. They were giving right answers. Can you provide any test case for which it may fail ?

I cant ask questions. I do not have enough karma points. Can someonne plz upvote my comment?

1 Like

@nsit.prashant

Try this case :

1

4 10 20 6 14

In this case, the output should be Yes,
because Michael’s piece would have the area of 10 * 2 square centimeters,
Kevin’s piece would have the area of 2 * 3 square centimeters
& Jake’s piece would have the area of 2 * 7 square centimeters.

But, the output of your solution is No.

@pankaj_chopra thanks…got it.