Gaming Array
Andy wants to play a game with his little brother, Bob. The game starts with an array of distinct integers and the rules are as follows: Bob always plays first. In a single move, a player chooses the maximum element in the array. He removes it and all elements to its right. For example, if the starting array arr = [2,3,5,4,1], then it becomes arr' = [2,3] after removing [5,4,1]. The two players alternate turns. The last player who can make a move wins. Andy and Bob play g games. Given the
View Solution →New Year Chaos
It is New Year's Day and people are in line for the Wonderland rollercoaster ride. Each person wears a sticker indicating their initial position in the queue from 1 to n. Any person can bribe the person directly in front of them to swap positions, but they still wear their original sticker. One person can bribe at most two others. Determine the minimum number of bribes that took place to get to a given queue order. Print the number of bribes, or, if anyone has bribed more than two people, pri
View Solution →Bonetrousle
Here's a humerus joke: Why did Papyrus the skeleton go to the store by himself? Because he had no body to go with him! Did you like it? Don't worry, I've got a ton more. A skele-ton. Once upon a time, Papyrus the skeleton went to buy some pasta from the store. The store's inventory is bare-bones and they only sell one thing — boxes of uncooked spaghetti! The store always stocks exactly k boxes of pasta, and each box is numbered sequentially from 1 to k. This box number also corresponds
View Solution →Yet Another KMP Problem
This challenge uses the famous KMP algorithm. It isn't really important to understand how KMP works, but you should understand what it calculates. A KMP algorithm takes a string, S, of length N as input. Let's assume that the characters in S are indexed from 1 to N; for every prefix of S, the algorithm calculates the length of its longest valid border in linear complexity. In other words, for every i (where 1 <= i <= N) it calculates the largest l (where 0 <= l <= i-1) such that for every p (
View Solution →Beautiful 3 Set
You are given an integer n. A set, S, of triples (xi,yi,zi) is beautiful if and only if: 0 <= xi,yi,zi xi+yi+zi = n, for all i : 1 <= i <= |S| Let X be the set of different xi's in S, Y be the set of different yi's in S, and Z be the set of different zi in S. Then |X| = |Y| = |Z| = |S|. The third condition means that all xi's are pairwise distinct. The same goes for yi and zi. Given , find any beautiful set having a maximum number of elements. Then print the cardinality of (i.e., ) on a
View Solution →