# Learnings from a CP Contest (ProSort 68 Div-2)

Recently I took part in a competetive programming contest. It was a practice one and I learnt some very important things.

## Major take-aways

Thanks to Bhavye Anand Gupta, for the explanations and patience :D

1. Modular Arithmetic
1. `(a*b)%m = a%m * b%m`
2. `(a/b)%m = a%m * (b-inverse)%m`
2. Fermat’s Little Theorem (FLT): `(b-inverse)%m = ( b^(m-2) )%m`
IF m is prime, and in our case it is.

PS: For calculating `b^(m-2)` use fast exponentiation. Fast exponentiation means a recursive function in which; for `a^n` you just calculate `a^(n/2)`, and so on.
3. For calculation of Factorial, pre-compute it and store in an array

I was successfully able to solve the following two problems:

## Problem 1: “New Problem”

You can find the same problem in Practice on Codeforces. Original Problem Page Alternate Page with exact same Problem

``````iTa={1: 'a', 2: 'b', 3: 'c', 4: 'd', 5: 'e', 6: 'f', 7: 'g', 8: 'h', 9: 'i', 10: 'j', 11: 'k', 12: 'l', 13: 'm', 14: 'n', 15: 'o', 16: 'p', 17: 'q', 18: 'r', 19: 's', 20: 't', 21: 'u', 22: 'v', 23: 'w', 24: 'x', 25: 'y', 26: 'z'}
aTi={'q': 17, 's': 19, 'k': 11, 'u': 21, 't': 20, 'f': 6, 'n': 14, 'l': 12, 'j': 10, 'g': 7, 'z': 26, 'x': 24, 'i': 9, 'm': 13, 'w': 23, 'h': 8, 'b': 2, 'a': 1, 'e': 5, 'r': 18, 'y': 25, 'o': 15, 'd': 4, 'p': 16, 'c': 3, 'v': 22}

def getNext(a):
if a=="":
return ""
if(a=='z'*len(a)):
return 'a'*(len(a)+1)
else:
if(a[-1]!='z'):
return a[:-1]+iTa[aTi[a[-1]]+1]
else:
return getNext(a[:-1])+'a'

# a='a'
# for i in range(100):
# 	print(a)
# 	a=getNext(a)
n = int(input())
l=[]

for i in range(n):
l.append(input())

out='a'

while True:
flag = False
for i in l:
if out in i:
flag = True
break
if flag == False:
print(out)
break
else:
out = getNext(out)
``````

## Problem 2: “Beautiful Numbers”

You can find the same problem in Practice on Codeforces. Original Problem Page Alternate Page with exact same Problem

``````#include<bits/stdc++.h>
#define MOD 1000000007

using namespace std;

bool checkGoodness(int a, int b, long long int check){
while(check!=0){
if(!(check%10==a || check%10==b))
return false;
check=check/10;
}
return true;
}

long long int fastExp(long long int base, long long int power){
// Includes modular
if(power==0) return 1;

long long int res = fastExp(base,power/2);
if(power%2==0)	return (res*res)%MOD;
else return (((res*res)%MOD)*base)%MOD;
}

long long int modInv(int x){
return fastExp(x, MOD-2)%MOD;
}

int main(){
long long int a,b,n;
scanf("%lld %lld %lld", &a,&b,&n);

//PreComputing for Factorial
long long int pre[n+1];
pre[0]=1;
for(int i=1; i<n+1; i++)
pre[i]=(pre[i-1]*i)%MOD;

long long int ans=0;
for(long long int x=0; x<n+1; x++){
long long int summ=x*a+(n-x)*b;
if (checkGoodness(a,b,summ)){
long long int toAdd = pre[n] * modInv((pre[x]*pre[n-x])%MOD);
}
}
printf("%lld\n", ans);

return 0;
}
``````

Python gave a TLE for me

``````from math import factorial

MOD = 1000000007
a,b,n=list(map(int,input().split()))

def checkGoodness(a,b,st):
for ch in str(st):
if int(ch) not in [a,b]:
return False
return True

#Pre Computing for Factorial
pre = [0]*(n+1)
pre[0] = 1;
for i in range(1,n+1):
pre[i] = (pre[i-1] * i) % MOD

def fastExpo(base,power):
#includes modular
if power==0:
return 1

if(power%2==0):
return (fastExpo(base, power//2)**2)%MOD
return ( ((fastExpo(base,power//2)**2)%MOD) *base)%MOD

# assert 1024==fastExpo(2,10)
# assert 512==fastExpo(2,9)
# assert 243==fastExpo(3,5)

def modInv(x):
return fastExpo(x,MOD-2) % MOD

# def fac(n,till):
# 	ans =1
# 	for x in range(n,till,-1):
# 		ans=((ans%MOD)*(x%MOD))%MOD
# 	return ans

ans=0

for x in range(n+1):
summ = x*a+(n-x)*b
if checkGoodness(a,b,summ):
print(ans)

``````

## Files and Resources

1. Complete Problem Set: Link, PDF
2. new_problem.py
3. beautiful_numbers.cpp
4. beautiful_numbers.py(this one was giving TLE, but algorithm is similar)
Written on January 25, 2019