Competitive Programming LDN #2

We are Competitive Programming London, we meet once a week to practice on some algorithm problems from Codeforces, Hackerrank, Leetcode and other problems. Everytime we meet we work on several problems in pairs and then discuss eachother’s solutions as a whole towards the end. For this event we had a go at three problems:

• Codeforces distinct digits
• Leetcode valid parenthesis
• Hackerrank drawing book

This post will summarise our discussion points and how we approached the solutions for each problem.

Distinct Digits

problem link: https://codeforces.com/contest/1228/problem/A

This problem asks us to find a any number with distincts between the range a and b. The constraints of the problem are that both a and b is between 0 and 10⁵. Furthermore b is always larger than a. Like most competitive problems, its usually wise to see if a brute force solution would be enough for this problem. Our range is at most of size 10⁵, but if we were to check any range between a and b what is the most number of checks we have to make? Well lets find out with a quick script:

The program above will tell us how many calculations we can expect to perform in the *worst case* for the range between 0 and 10⁵. After we run it we get the following output:

1047 10987 12034

Which means the most calculations we will be performing are 1047, and that is for a=10987 and b=12034 . So this tells us that we can comfortably write a bruteforce solution to solve it:

Is there a more “efficient” way? It turns out there is, and its to as outselves if we can generate the minumum number greater than or equal to x which has distinct digits. I have pasted the code below which does this type of generation. It will take too long to explain what it does so if you have any questions about it reach out to me on social media (links below)

Valid Parenthesis

Problem link: https://leetcode.com/problems/valid-parentheses/

As with most problems involving parenthesis, they can be solved using a stack. Every time you see an opening brace you push it to the stack. When you see a closing brace you pop the stack and check for a match. If one exists proceed. If the is no match or the stack is empty the sequence is invalid.

If we iterate through the string without issues, we just check in the end that the stack is empty. If it is, then our sequence was valid, otherwise if the stack was not empty then our sequence was invalid:

Drawing Book

Problem link: https://www.hackerrank.com/challenges/drawing-book/problem

In this problem we just need to find which flip number we are in for a given page number. To do that, dividing by 2 (floored) will give us this value. for example for page 1, 1/2 = 0 , for page 2, 2/2 = 1 , for page 3, 3/2 = 1 , for page 4, 2/2 = 2 , and so on. So this gives us which flip index we are in. The key is then to calculate the flip index of the last page, and then our answer will be the minimum of the flip distance from the start (index 0) until the flip index of p , and the distance from the end until the flip index of p :

def pageCount(n, p):
    fromStart = p // 2
    fromEnd = n // 2 - p // 2
    return (min(fromStart, fromEnd))

If you are in London I hope to see you in the next event :). Interested in joining our slack group to discuss problems like this? Drop me a line on twitter or linkedin to join