DEFACING - Editorial

editorial
, , , ,
41

Your WA is actually RE. It seems that for this test
2454 211622
the following happens

Error:-1
Error:java.lang.ArrayIndexOutOfBoundsException: -1
Error:java.lang.Exception: java.lang.ArrayIndexOutOfBoundsException: -1
1 Like
42

Ohhh
You are right, thanks for the input, Iā€™ll work on the bug

43

@syker >> Try these tests:

8 13

8 24

Correct Answer: 8 and 18 respectively

Your answer: 89 and 89

UPD.
Your code gives correct answer for the above tests when they are performed initially, but gives 89 when they are written after some tests like 10 100. That might be because of faulty/misplaced initialization of some check arrays.

44

@anton_lunyov
I am now struggling with TLE issue for this problem.

What I find odd is: time limit is the same irrespective of platform. Isnā€™t some languages faster as compared to others? And I havenā€™t seen a single successful submission for JAVA for this problem. I know, it could be a mere coincidence but it still makes me wonder.

I have tried many optimization techniques but none of them are giving any improvements. On my system I see lot of improvements with every major optimization(I have simulated huge inputs, as per given constraints, using random number generators)but when I submit here, I donā€™t see any improvement at all in time, every time i just get 4.04 seconds, not even slightest improvement.

Moreover, some optimization techniques which definitely should have worked have actually deteriorated the performance, e.g. if you compare the submissions:
http://www.codechef.com/viewsolution/1877893 and
http://www.codechef.com/viewsolution/1883458

the only change is in the function convertToNumber(), where instead of using String object, to append digits one by one, I used StringBuilder and append() function, which according to me should give better performance, but instead the time deteriorated to 10 seconds from 4 seconds.

Any pointers in this regard?

45

Actually there were several AC in Java even during live contest:


But AFAIK EgorK invent an O(lg(M)) solution in order to solve the problem while having TLE with O(lg(M) * lg(S)) solution.
So probably for Java TL is a bit strict, though it is twice as usual TL.

46

Why is the answer for 25, 100 is 89 but not 98 ?

025 ā€”> 089 ā€”> 89

250 ā€”> 098 ā€”> 98

Somebody please clarify, Iā€™m strugglingā€¦

47

I posted my code on Ideone: http://ideone.com/tJKTyy
I am getting a WA.

I think it is passing the test cases given in the question and the comments here (as well as some ones I made myself), but I might simply be misreading. Can someone help me find my problem? Or at least a test case where my program is returning the wrong answer?