LCH15JEF - Editorial

PROBLEM LINK:

Practice
Contest

Author: Pavel Sheftelevich
Tester: Roman Rubanenko
Editorialist: Paweł Kacprzak

DIFFICULTY:

Easy

PREREQUISITES:

Math, Big-num

PROBLEM:

For each test case you are given a number m and an expression which contains only numbers multiplications and exponentiations. Your task is to find the value of the expression modulo m

QUICK EXPLANATION:

Parse the expression and calculate it using big num representation and fast exponentiation.

EXPLANATION:

EXPECTED SOLUTION:

If we are able to handle 3 operations: multiplication, exponentiation and modulo calculation, we can solve the problem easily after parsing the input first. Since input numbers can be very large, this is not straightforward and I’ll show how to implement these 3 operations step by step:

  1. Calculating modulo. Let assume that we have to calculate A % M. In this problem M is always < 10^8 so we can store it as 64-bit integer. Let dk-1, dk-2, …, d0 be the digits of A from left to right. Then A = 10^(k-1) * dk-1 + 10^(k-2) * dk-2 + … + d0 and based on this fact, we can write A % M as (10^(k-1) * dk-1) % M + (10^(k-2) * dk-2) % M + … + d0 % M which can be easily computed using Horner’s method - please check the author’s solution for details.

  2. Exponentiation. Let assume that we have to calculate A^B, where A and B can be arbitrary long numbers. First we can calculate reduce A to A^M because (A^B) % M = ((A%M)^B) % M. So now we are raising a number A < 10^8 to an arbitrary long exponent. Let B = 10^(k-1) * dk-1 + 10^(k-2) * dk-2 + … + d0 where di is the i-th rightmost digit of B. Then A^B = A^(10^(k-1) * dk-1 + 10^(k-2) * dk-2 + … + d0) which can be written as A^(10^(k-1) * dk-1) * A^(10^(k-2) * dk-2) * … * A^d0 and you can again use the Horner’s method to compute it - please check the author’s solution for details.

  3. Multiplication of two numbers A, B < 10^18 modulo MOD < 10^18. The result of this operation may not fit into 64-bit integer, so we have to be smart here. You can use the same idea as in the fast exponentiation algorithm here, please check this function from author’s code:

long long MOD;
long long mult(long long A, long long B)
{
	if ( B == 0 ) return 0;
	long long u = mult(A, B/2);
	long long res;
	if ( B%2 == 0 ) 
		res = u + u;
	else
		res = u + u + A;
	while ( res >= MOD ) res -= MOD;
	return res;
}

SOLUTION USING BIG NUMS:

Since numbers in the statement can be very large and m can be big also, this problem is very easier to code in a language which has implemented a big number representation. For example Java or Python is a really good choice here. If you are planing to write the solution in a language which doesn’t support big numbers, you have to implement it on your own along with operation of multiplication, fast exponentiation (which is done by multiplication) and modulo calculation. The bottom line is that you have a strong advantage here if you are using a language which supports big numbers or you have an implementation of it prepared before the contest.

I will focus now on the implementation, because if you do it fast and smart, you can benefit huge from it.

First things first, we have to parse the input statement, because it is given as a string of numbers and operands. If you are familiar with regular expressions, you are in a pole position here. Let change two start representing exponentiation to ^ symbol duo to formatting issues in this editor only for editorial purposes. If we divide the statement x1^y1 * x2^y 2 * … * xn^yn into pairs of numbers (x1, y1), (x2, y2), …, (xn, yn) we can first compute the result of exponentiation for each pair and then multiply these intermediate results. So let’s split the input statement just into consecutive numbers! Then we can get two such numbers, do the exponentiation on them and multiply the current result by the result of this exponentiation - remember that all operations have to be calculated modulo m.

If you are using python or another language with regular expressions built in, you can split the input statement s in consecutive numbers using the below regular expression:

re.split(r'[^0-9]+', s)

where s is the input string and re is the standard regular expression module

In python there is a built in fast exponentiation functions which can also calculate the result modulo given number. To compute (a^b) % c just run mod(a, b, c). I encourage you to use it, because it is really fast and very well implemented.

If you want to know how to do fast exponentiation on your own, please check this link. One important note is that for big exponents, a resursive exponentiation of it will give you Runtime Error duo to stack overflow. You should implement it iteratively.

Since my python solution in quite short, you can see the full code below:

import re

t = int(raw_input())

for i in xrange(t):
    m, s = raw_input().strip().split()
    m = long(m)
    s = s.strip()
    a = re.split(r'[^0-9]+', s)
    res = 1
    for i in xrange(0, len(a), 2):
        res = (res * pow(long(a*), long(a[i + 1]), m)) % m
    print res 

ALTERNATIVE SOLUTIONS:

For the first subtask, you don’t have to use big numbers at all since numbers in the expression are digits and m is small enough. For the second subtask, every result of an exponentiation can be keeped small when calculated modulo m, because m < 10^9 and this allows you to do multiplication in the statement in 64-bit integers because a * b, for a, b < 10^9 fits 64-bit integer.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.
Tester’s solution can be found here.

RELATED PROBLEMS:

3 Likes

These kind of programs pose a huge advantage to JAVA / PYTH users.

Luckily , I code in Java and so I could use BigInteger and get a 100 easily.

But,such programs are not advisable for contests like LunchTime where one

expects high standard algorithmic programs rather than just implementation.

6 Likes

@pkacprzak I implemented the same thing as your editorial but I was awarded only partial points.
What part have I missed?
Solution link here.

Thanks,

Regards, Ankit

Worst problem of all time. This type of problem (boring, unoriginal and made for Python/Java) is useless in a contest of this kind. A language should not be favored by a problem.

4 Likes

I did it in Python as these problem are only language oriented / implementation oriented

import sys 
f = sys.stdin
T = int(f.readline())
while T:
 
	M,S = [str(x) for x in f.readline().split()]
	N = len(S)
	i = 0
	ans = 1 
	M = int(M)
	while i '9' or S* < '0') :
			i += 1 
		op1 = 0 
		while i < N and (S* <= '9' and S* >= '0') : 	
			op1 = op1 * 10 + (int(S*)-int('0'))
			i += 1
 
		while i < N and (S* > '9' or S* < '0') :
			i += 1 
		op2 = 0 
		while i < N and (S* <= '9' and S* >= '0') : 	
			op2 = op2 * 10 + (int(S*)-int('0'))		
			i += 1 
		ans = ans * pow(op1,op2,M)
		ans %= M
	print ans 		 
	T -= 1 

Since there is a big discussion on this problem, I’ll give my view on it:

@alexvaleanu This python solution is mine and I wrote it for editorial purposes. I also code 99% of problems in C++, but I know that there are problems for which there are better languages and this is one of them.

##Here is the important note

Are you complaining that you code in C++ and this problem is the worst of all time? Think different. If there is an user who codes in Python mainly and he has to implement a very complicated data structure in order to solve a problem, should he complain that this is the worst problem of all time because he cannot code it in Python? Be versatile, I am not the author of the problem, but this is a programming competition and not C++ contest.

10 Likes

I implemented the biginteger using strings in c++ and did the problem the same way as in the editorial . But it gives me a TLE . solution link

To all who thinks that this problem is just about parsing, implementation and programming languages(especially as @alexvaleanu)

Author’s solution implemented in C++ and doesn’t require any big numbers arithmetic. Editorial will be updated soon. Now you can have a look at author’s solution.

Sorry for the situation with many solutions easily passed using Python or Java, that wasn’t supposed(but it’s programming contest and I think it’s ok to use advantages of the languages though it wasn’t planned).

Also I think you should at first think about possible alternative algorithm ideas(by the way not absolutely obvious) before writing: “Worst problem of all time”

5 Likes

http://www.codechef.com/viewsolution/5993673 . Any ideas why this solution got NZEC ?

The difficulty says “To be updated soon”. Isn’t it decided during problem setting??

Although I missed the contest, I was trying to solve the problems! When I solved this problem in python, the following code worked perfectly for me:

T = int(raw_input())

for t in range(T):

M, S = map(str, raw_input().split())
`
M = int(M)

S = eval(S)

print S%M

However, when I checked a few solutions, they were way too long codes!!! Is my code wrong?

Please explain the exponentiation part of the author’s solution. I believe this is a very useful problem for C,C++ programmers.

1 Like

author’s solution is giving wrong answer
consider this input:
1
10000 2x3x4x5
answer should be =120
author’s answer = 1

@pavel1996 when i use author solution and replace in solve()

for (int i=0;i<l;i++) 

with

for (int i=0; s* != ‘\0’; i++)

i got WA. can you tell me why?

while Calculating modulo of

A % M , M < 10^8
A     = 10^(k-1) * dk-1 + 10^(k-2) * dk-2 + ... + d0 
A % M = (10^(k-1) * dk-1) % M + (10^(k-2) * dk-2) % M

how are we handling for k > 30 ?

http://www.codechef.com/viewsolution/6589294

This is fetching only 70 points. It’s probably something got to do with overflow but I can’t figure out what. What am I missing?

TIL Python has fast modular exponentiation. Thanks!

Java (and even Python maybe) will be available in the upcoming IOIs, so I don’t think this problem is completely useless since one should keep in mind that different languages, which I consider as weapons, have different advantages.

Ask any ACM ICPC team, there is always someone who could program in Java because it offers BigDecimal and BigInteger.

@pkacprzak I am sorry for that comment. I wasn’t paying attention to whose solution it is.

@ankitdhall I see that you are using int64_t as you big, but int64_t is the 64-bit integer which is not enough for this problem. You have to be able to handle numbers consisting of 9998 digits.

1 Like