LCH15JEF - Editorial

editorial
, , , , ,
5

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[i] < '0') :
			i += 1 
		op1 = 0 
		while i < N and (S[i] <= '9' and S[i] >= '0') : 	
			op1 = op1 * 10 + (int(S[i])-int('0'))
			i += 1
 
		while i < N and (S[i] > '9' or S[i] < '0') :
			i += 1 
		op2 = 0 
		while i < N and (S[i] <= '9' and S[i] >= '0') : 	
			op2 = op2 * 10 + (int(S[i])-int('0'))		
			i += 1 
		ans = ans * pow(op1,op2,M)
		ans %= M
	print ans 		 
	T -= 1
6

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
7

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

8

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
9

CodeChef: Practical coding for everyone . Any ideas why this solution got NZEC ?

10

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

11

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?

12

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

1 Like
13

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

14

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

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

with

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

i got WA. can you tell me why?

15

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 ?

16

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?

17

TIL Python has fast modular exponentiation. Thanks!

18

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.

19

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

20

@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
21

@gdisastery1 If you see 10 more problems like this, you could get a WRONG impression that Java/Python are better because there are prewritten classes for big numbers, for example.

22

@alexvaleanu If you are a beginner, you might get this wrong impression. So you are implying C++ is better than Java/Python? Even though it is the most preferred language in competitive programming (I also use C++ mainly), it is not the best - it really depends on the problem.

23

thanks for the looking into my code! :slight_smile: another of doubts was how was it possible to have xi and yi of the order 10^999 or so; since the string length was restricted to a lesser value (10^4)?
Thanks for your time :slight_smile:

24

@gdisastery1 This is the point that I am trying to prove. I am not saying which language is better. It does not matter. A language should not be favored by a problem.