Chef vs Bharat - CodeChef July Long Challenge solution in Python | AskTheCode

Codechef July Long Challenge 2021 Solution | Chef vs Bharat solution in Python | AskTheCode

---

Problem:

Chef and his friend Bharat have decided to play the game "The Chefora Spell".

In the game, a positive integer N (in decimal system) is considered a "Chefora" if the number of digits d is odd and it satisfies the equation

where Ni is the i-th digit of N from the left in 0-based indexing.

Let Ai denote the i-th largest Chefora number.

They'll ask each other Q questions, where each question contains two integers L and R. The opponent then has to answer with

Bharat has answered all the questions right, and now it is Chef's turn. But since Chef fears that he could get some questions wrong, you have come to his rescue!

---

Input:

• The first line contains an integer Q - the number of questions Bharat asks.

• Each of the next Q lines contains two integers L and R.

Output:

Print Q integers - the answers to the questions on separate lines.

---

Sample Input:

2
1 2
9 11

Sample Output:

1
541416750

---

EXPLANATION:

• For the first question: (A1) ^ A2 = 1^2 = 1.
  

• For the second question: (A9) ^ A10 ⋅ (A9) ^ A11 = 9 ^ 101 ⋅ 9 ^ 111 ≡ 541416750 (mod 10 ^ 9 + 7).

---

Code:

def odd_Palindrome(val):
	n, palindrome = val, val
	n //= 10
	while n > 0:
		palindrome = ((palindrome * 10) + (n % 10))
		n //= 10
	return palindrome

class Palin():
	"""docstring for Palin"""
	def __init__(self, n):
		super(Palin, self).__init__()
		self.n = n
		self.i = 0
		self.palindrome = [0]*n
		self.prefix = [0]*n

	def fill(self):
		return self.i == self.n
	def add(self, v):
		self.palindrome[self.i] = v
		self.prefix[self.i] = v
		if self.i != 0:
			self.prefix[self.i] += self.prefix[self.i - 1]
		self.i = self.i + 1
	
	def basePalin(self, l):
		return self.palindrome[l]
		
	def rangedPrefix(self, l, r):
		return self.prefix[r] - self.prefix[l]

def create_Palin(palindrome):
	idx = 1
	while not palindrome.fill():
		palindrome.add(odd_Palindrome(idx))
		idx += 1

def calc(left, right, palindrome):
	power = palindrome.rangedPrefix(left - 1, right - 1)
	base = palindrome.basePalin(left - 1)
	return pow(base, power, 1000000007)

class Solution(object):
	try:
		obj_Palin = Palin(100001)
		create_Palin(obj_Palin)

		num_Of_Queries = int(input())
		while num_Of_Queries > 0:
			left, right = map(int, input().split( ))
			print(calc(left, right, obj_Palin))
			num_Of_Queries -= 1

	except Exception as e:
		raise e