LCH15JEF - Editorial

editorial
, , , , ,
21

same thing happened to me. c++ bigint code gets TLE

22

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
23

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

24

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

25

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?

26

Your code will only work for the first subtask. IT will timeout for the rest.

27

can anyone explain the author’s solution? I have no idea how, exponetiation happened in it…

28

Nice problem, I guess it’s unfortunate that it could be solved so easily with other languages.

Why doesn’t the editorial describe this solution instead of talking about the obvious brute force bignum algorithm? The reason everyone is raging here is because it looks like the official and expected solution is to use Python/Java because that’s the only solution described in the editorial. If your solution had been posted as the editorial then I doubt as many people would have complained.

1 Like
29

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

1 Like
30

Refer this: http://discuss.codechef.com/questions/62764/exponentiation-lch15jef

31

Refer this: http://discuss.codechef.com/questions/62764/exponentiation-lch15jef

32

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

33

String cannot be input this manner. Its of the format (a1)(a2)(a3)…an where each ai is of the form bi**bj.

34

It’s still possible to write a solution quite a bit shorter than the ones most contestants have done.

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

35

It is updated now, but in general deciding a difficulty after the contests is better, because a number of contestants who solve it correctly affect the level of difficulty. For example, there can be an unexpected method of solving it which comes up during a contest.

36

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

37

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 ?

38

It was a good problem and can be coded easily in C++ if one remembers basic arithmetic operations and the logic behind them. I did it easily.

1 Like
39

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?