LCH15JEF - Editorial

editorial
, , , , ,
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.

25

Again, I am truly for my mistake. If a Python user should code a very complicated data structure, a C++ user should too. Problems should not be about different aspects of programming languages.

26

@alexvaleanu I mean, that for python coder, coding a complicated data structure is usually out of their range

27

@alexvaleanu There are always two sides of a problem in a PROGRAMMING CONTEST - first the theoretical solution - with pseudocode maybe, and second the implementation. If you are saying the problems should not be dependent on the language, each problems would only have the first part - and we would all be writing pseudocode or explaining the solution theoretically. Boring, isn’t it?

If you are picking the wrong tool for the wrong problem, then it’s your fault for coding too long. It’s like cutting a cucumber with a hammer.

3 Likes
28

@ankitdhall, just notice that 10^9997 has 9998 digits and a string of length 10^4 can have 10000 digits :wink:

29

Looks like I should learn java