PROBLEM LINK: CDVB2022/CHEFKNIGHT
Author: madra
DIFFICULTY
Easy-Medium
PREREQUISITES
None
EXPLANATION
This problem can be solved in two ways. One is the iterative method by keeping two stacks and removing knights from them by iterating each move through a loop but this can be really slow for large stacks and is quite inefficient.
So, looking at the nature of this problem, one can easily come up with a simple logical method to remove knights from the stacks all at once and predict the outcome based on the result of that single operation. Firstly, we can ensure the second stack we’re dealing with is the bigger one so we can swap the two if it is not with a simple swap of variables. Now that, the second one is the larger one we can find if it is more than twice as big as the smaller stack because if it is we cannot empty it with the given procedure of steps.
Next, we can remove all the 3’s from both stacks by taking remainder as a simple alternation of 1 and 2 removal or 2 and 1 removal. Next, we again ensure the second stack is the larger one by performing a swap if it is not. Now, we can check for the remainder to see if both have a 0 or if first has a 1 and the second has a 2 to ensure that we can finally perform another step to empty them completely.
If none of the above conditions satisfy, we can say we were not able to empty down the stacks and that solves our problem.
Time Complexity:
O(1) per test.
SOLUTION
CPP : solution