Editorial for Victor's Various Adventures - Victor Counts Marbles

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Prerequisites: Recursion, Simple Reasoning & Math

Observation

While this problem may be solved with combinatorics, it can also be simply brute forced. Since there are at most 16 slots, we can try all 2^{16} possibilities with recursion. For each of the outcomes (We can think of this as a tree-diagram), we simply have to check whether there is a contiguous sequence of more than R of the same marbles.

Solution

We can define the recursive function F(i, l, c) where i is the current slot, l is the number of marbles that repeat starting from the current one, and c is the color of the marbles.

From here, we can consider 2 base cases for recursion:

  1. If l > R we know that the current outcome will always result in an invalid answer, thus we can ignore it.
  2. If i is at the end of the slots, we know that the current arrangement is valid. (We know this because we have already ignored the invalid arrangements from case 1.)

Additionally, for each slot, we have two choices to select our marble.

  1. We can choose the current marble to be White, and if c \neq \text{White}, we reset the repeat counter l.
  2. We can choose the current marble to be Black, and if c \neq \text{Black}, we reset the repeat counter l.

Then we can recursively call function F with our updated parameters to find all of the choices.

import java.text.DecimalFormat;
import java.util.Scanner;

/**
 * @author Encodeous
 * Solution to https://tssoj.ca/problem/victor2
 */
public class Victor2 {
    private static int numberOfArrangements = 0;
    private static int totalSlots;
     private static int repeatCondition;
    /**
     * Recursively solve the problem
     * @param slot The current slot
     * @param count The number of marbles that are currently the same, and are in a row
     * @param isWhite The color of the marbles that are currently in a row
     */
    public static void solve(int slot, int count, boolean isWhite) {
        if (count > repeatCondition)
            return;
        if (slot == totalSlots) {
            numberOfArrangements++;
            return;
        }
        // white marble
        solve(slot + 1, isWhite ? count + 1 : 1, true);
        // black marble
        solve(slot + 1, isWhite ? 1 : count + 1, false);
    }
    public static void main(String[] args) {
        // Read Input
        Scanner sc = new Scanner(System.in);
        // Read M and R
        totalSlots = sc.nextInt();
        repeatCondition = sc.nextInt();
        // call the recursive function
        // first marble is white
        solve(1, 1, true);
        // first marble is black
        solve(1, 1, false);
        System.out.println(numberOfArrangements);
    }
}

Comments

There are no comments at the moment.