Hi Brilliant!

I've been missing the programming section and I thought we could create a thread where we post challenging programming problems. This is your opportunity to suggest perplexing problems and a chance to parade your programming skills! I'm looking for elegant problems and solutions.

Programming is an art! Don't just write a solution that works, but aim to write an algorithm that is concise so that if you give it to another programmer, they can understand it with ease.

Post your programming problems and challenge the Brilliant community to solve them!

Vote up if you have a passion for programming!

## Comments

Sort by:

TopNewestThis is a somewhat tough problem from the world of numerical analysis and matrix theory:

In scientific computing, a useful metric for the "size" of a matrix is its infinity norm, which is a total function on the space \(\|\cdot\|_\infty : \mathbb{R}^{n \times m} \to \mathbb{R}\) that gives the maximum row sum of the absolute value of its input (i.e. you take the absolute value of a matrix and sum all of its rows, then you return the largest of those sums).

A matrix is lower bidiagonal if it looks like \[\left(\begin{array}{cccc}l_1 \\ r_2 & l_2 \\ & r_3 & l_3 \\ && r_4 & l_4\end{array}\right)\]

Suppose \(A\) is lower bidiagonal, write a function

invnorm(l,r)that takes in a list ofnnumbersl(denoting the main diagonal ofA) and another list ofn-1numbersr(denoting the first subdiagonal ofA) and return the infinity norm of \(A^{-1}\).Recommended Extensions (these require actual math):

Make

invnormrun in \(O(n^2)\) time (with respect tonthe sive ofl). Hint: the inverse ofAis lower triangular, and it turns out that with a bit of cleverness, you can construct each entry ofAin constant time if you know a few of the other entries ofA, a la the spirit of dynamic programming.Make

invnormrun in \(O(n)\) time. Hint: a) solving the system \(Ax = b\) takes \(O(n)\) time by dynamic programming; b) prove an invariance theorem on the properties of \(\|A^{-1}\|\) with respect to \(A\), then construct an invariant transformation under the mapping \(\|\cdot^{-1}\|_\infty\) which, combined with a), allows you solve the problem quickly.(Open) Is it possible to do better than \(O(n)\) time, what about for approximations?

Log in to reply

The solution to the first two extensions for those who want them and the pdfs – Lee Gao · 3 years, 8 months ago

Log in to reply

For those who really want a challenge, check out Prime Challenge – Pi Han Goh · 3 years, 8 months ago

Log in to reply

Programming Challenge: South African Programming Olympiad 2000 #4Given a string of digits 0-9. Group the adjacent digits to form numbers, in such a way that their sum will equal a certain given total T. A digit may only belong to one number. Input: A string of digits 0-9 followed by a second line containing the number T. Output: A string of groups. Output the groups as they appear in the original string, separated by commas.

Example

Input

String: 2415043

Total -T: 289

Output

Solution: 241, 5, 0, 43

Test you programme with the following:

a) String: 2237450 and T: 104

b) String: 1848935 and T:38 – Mark Mottian · 3 years, 8 months ago

Log in to reply

– Ivan Koswara · 3 years, 8 months ago

What are the constraints of the length of the string and the value of T?Log in to reply

– Mark Mottian · 3 years, 8 months ago

There are no constraints listed in the problem statement. I've posted the problem exactly the way it appears in the question paper.Log in to reply

Programming Challenge: South African Programming Olympiad 2013 #3A number is well-ordered when its digits are in numerically ascending order. E.g. 147 is well-ordered but 174 is not. In a well-ordered number, each of the digits 1-9 may only be used once. Write a program that will calculate the sum of all the well ordered numbers that are possible with a fixed number of digits.

Example:

Input: 2

Output: 1440

(Explanation: The programme added up all the well-ordered two-digit numbers. That is, 12 + 13 + 14 + 15 + 16 + 17 + 18 + 19 + 23 + 24 + 25 + 26 + 27 + 28 + 29 + 34 + 35 + 36 + 37 + 38 + 39 + 45 + 46 + 47 + 48 + 49 + 56 + 57 + 58 + 59 + 67 + 68 + 69 + 78 + 79 + 89) – Mark Mottian · 3 years, 8 months ago

Log in to reply

However, I have no better idea to do the actual computation without bruteforcing everything. Any ideas? – Ivan Koswara · 3 years, 8 months ago

Log in to reply

– Mark Mottian · 3 years, 8 months ago

This is ineffective! How would one solve the problem if the input is some large number such as 100 (as an explicit example)? Again, there are no constraints listed in the original question paper.Log in to reply

The problem is different when you are given both N and the base. (In this case, without the base, it's assumed to be 10.) – Ivan Koswara · 3 years, 8 months ago

Log in to reply

– Mark Mottian · 3 years, 8 months ago

Oh! That makes more sense.Log in to reply

Challenge: South African Programming Olympiad 2000 #2Imagine an alphabet that has been designed for a keyboard with only 2 keys: left and right. The keyboard sends the following signals: Left key pressed (L), Left key released (M), Right key pressed (R) and Right key released (S). Certain patterns of key presses or releases create meaning – in this case, letters of the alphabet.

Signals:

LM --> A

RS --> N

LRSM --> C

LRMS --> E

RLSM --> L

RLMS --> T

Task: Recognise the letters from the signals and print the message

Input: A string of letters Output: The resulting message

Example:

Input: RLMSLRMSRSRLMS

Output: TENT

Test Data:

i) RLMSLMRLSMLRMSRSRLMS

ii) LRSMLMRLMSRLMSRLSMLRMS – Mark Mottian · 3 years, 8 months ago

Log in to reply

Algorithm AlertWhat is the

most efficientalgorithm to determine the following?i) The lowest common multiple (LCM) of two (or more positive integers). E.g. the LCM of 10, 15 and 20 is 60

ii) The greatest common divisor (GCD) of two (or more positive integers). E.g. the GCD of 10, 15 and 20 is 5

iii) The prime factorisation of a single positive integer. E.g. the prime factorisation of 693 = 3x3x7x11 – Mark Mottian · 3 years, 8 months ago

Log in to reply

Euclidean algorithm is a sufficiently fast one (at the order of \(O(n^2)\) where \(n\) is the average number of bits of the numbers). A method to compute the GCD of more than two numbers is by computing the GCD of each integer and the current GCD, which probably means \(O(n^{2k-2})\) where \(n\) is the average number of bits of the numbers and \(k\) is the number of numbers.

ii)i) Use Euclidean algorithm again. Since LCM of \(a,b\) is simply \(\frac{ab}{\gcd(a,b)}\), we can compute it in \(O(n^2)\) for the GCD, then probably \(O(n^2)\) too for division of \(a\) with \(\gcd(a,b)\), and then probably \(O(n^2)\) again for the multiplication with \(b\), for an overall of \(O(n^2)\). So it will have roughly the same complexity as GCD, but will be much slower than it (partly due to threefold computation, partly because LCM grows in size while GCD shrinks as more numbers are processed, thus making multiplications/divisions harder).

iii) Widely believed to be NP-Intermediate; no polynomial time algorithm is known. The most efficient algorithm known is general number field sieve. – Ivan Koswara · 3 years, 8 months ago

Log in to reply

– Edward Jiang · 3 years, 8 months ago

I remember seeing a formula once that outputs the largest prime factor of any positive integer. I know the article (Dudley, U., Formulas for primes, Math. Mag., 56 (1983) 17-22) but can't really find the formula.Log in to reply

TASK!!!Write programs to determine what is outlined above. – Mark Mottian · 3 years, 8 months ago

Log in to reply

I guess this is a really popular one..But try finding the millionth prime number. – Thaddeus Abiy · 3 years, 8 months ago

Log in to reply

Programming Challenge: British Informatics Olympiad 2002 Sample Paper #1A group of friends are standing in a circle, playing a game. They proceed around the circle, chanting a rhyme and pointing at the next person (clockwise) on each word. When the rhyme finishes whoever is being pointed at leaves the circle. They then start again, pointing where they left off, and the game continues until only one person is left.

For example, suppose there are six friends (numbered 1 to 6) standing around the circle and the rhyme is "Eenee, Meenee, Mainee, Mo!". The first person to leave the circle is number 4, followed by 2 then 1, 3 and 6. Number 5 is left.

Sample run

Number of friends: 7

Words in rhyme: 3

Number 4 is left

TaskWrite a program that inputs two numbers (each between 1 and 1000 inclusive), the first being n, the number of friends, and the second the number of words in the rhyme. The output should be the number of the last person left.You should assume that the friends are numbered (clockwise) from 1 to n, and that the count begins at person 1. – Mark Mottian · 3 years, 8 months ago

Log in to reply

Log in to reply

Works by looping through and removing one person at a time. – Oliver Welsh · 3 years, 8 months ago

Log in to reply

– Ivan Koswara · 3 years, 8 months ago

Challenge: Can you do better than \(O(n)\)?Log in to reply

Programming Challenge: South African 2013 Programming Olympiad #4(I've managed to come up with a solution this problem, however, it's definitely not the most elegant.)

An anagram of a word contains the same letters as the original word, but in a different order.

Write a program that will calculate how many anagrams can be made with a given word - NOT counting the word itself. Anagrams that have the same letter-order may only be counted once. The words given will always be lower case.

Example 1:

Input: cat

Output: 5 (Explanation: the accepted anagrams for "cat" are: "cta", "act", "atc", "tac", "tca" which is a total of 5)

Example 2:

Input: see

Output: 2 (Explanation: the accepted anagrams for see are: "ese" and "ees". Although "ees" can be made up in two ways by rearranging the letters of "see", it only counts as a single anagram - because the final word in the same. A total of 2.) – Mark Mottian · 3 years, 8 months ago

Log in to reply

Log in to reply

Log in to reply

The Daily WTF:

Here, I again modify the program (without modifying the logic behind it), lest your program goes toI don't get why you put numerator = 0 and answer = 0 while you immediately assign them something else. – Ivan Koswara · 3 years, 8 months ago

Log in to reply

– Mark Mottian · 3 years, 8 months ago

This is exactly what I wanted! I wanted someone to improve my code whilst not altering the logic behind it. You are fantastic!Log in to reply

– Vamsi Krishna Appili · 3 years, 8 months ago

Can u please answer some of my Questions in Programming?Log in to reply

– Vamsi Krishna Appili · 3 years, 8 months ago

Please , can u answer some of my questions in Programming.., I would start discussion a minute later please reply?Log in to reply

– Mark Mottian · 3 years, 8 months ago

The entire Brilliant community will try their best to answer your questions.Log in to reply

– Mark Mottian · 3 years, 8 months ago

I really like your solution. I didn't think of making a dictionary to count each letter (I haven't used this enough). We had the same approach, but yours is more concise. I've really learnt a lot from your solution. Thank you so much!!Log in to reply

Log in to reply

– Mark Mottian · 3 years, 8 months ago

This is really simple! Well done! It takes quite a while for longer strings though.Log in to reply

Here's a fairly simple problem from CodeChef.com.

And one more suggestion I have - programming enthusiasts can also share their views about popular algorithms as well. – Kou$htav Chakrabarty · 3 years, 8 months ago

Log in to reply

– Mark Mottian · 3 years, 8 months ago

Thanks for an awesome problem! Do you have any other suggestions or problems? I think posting popular algorithms (in this thread) is an excellent idea!Log in to reply

Log in to reply

– Ivan Koswara · 3 years, 8 months ago

In programming problems, you must give the exact output as required. Your "Enter number of testcases:", "Number:", and "Output:" make your program fails the problem.Log in to reply

– Mark Mottian · 3 years, 8 months ago

Thanks for the advice. I put those keywords in the programme to aid better understanding of the code. The programme still works 100% (as outlined in the problem statement) if I remove those keywords.Log in to reply

Here's how your program can be shortened:

Standard input and standard output are separate, so what you output will not be broken by what the judge will input. For example, what the judge will see will not be:

But:

(At least that's what I know.) – Ivan Koswara · 3 years, 8 months ago

Log in to reply

– Mark Mottian · 3 years, 8 months ago

Very elegant!Log in to reply

– Vamsi Krishna Appili · 3 years, 8 months ago

Can u please answer some of my questions ., in JAVA .., PLEASE REPLYLog in to reply

The following is probably the best website for programming purposes ::

Project Euler – Priyanka Banerjee · 3 years, 8 months ago

Log in to reply

– Mark Mottian · 3 years, 8 months ago

Project Euler is awesome! I also use it. After a while, it does get a bit tedious. Why don't you put forward your favourite problem from Project Euler for us to solve?Log in to reply

sorry – Hao Tian Lee · 3 years, 8 months ago

Log in to reply