Problem — Nastya and Scoreboard
My submission — Cryptic Taiga's Submission
I figured out a way to solve this problem. First I saved the number of changes needed to be made in each input string/digit to a digit from 0-9 in the array changes[][]. Next, I filled up the dp[][][] array with 0, 1 depending upon if this path leads to the maximum obtainable number as per the requirement of the question.
But, somehow i am getting TLE in the testcase 7.
Please help solving and correcting my submission.
I converted your code into C++ and it got AC in 576 ms: 87943417 Java should be able to get AC still I think.
If you put the smallest dimension of a multidimensional array as the first dimension, you can get a huge performance boost (I just experienced this myself).
It could be that String concatenation is a problem as well, but I'm not sure. Using StringBuilder, string concatenation is $$$O(length of added string)$$$ instead of $$$O(length of new string)$$$. StringBuilder works similar to C++ string.
Also consider using your own class for reading input and using PrintWriter for output. Scanner and System.out.print are slow for large amounts of data.
I tried doing that and used a custom class called Reader to take inputs as they could be huge and used a StringBuilder to store the answer but still i am getting a TLE on test case number 7.
My submission — CrypticTaiga's Submission
This sucks. C++ submission with same idea get accepted. I guess people who code in Java should be allowed 2 sec/test-case for such problems. Many platforms do this !
Just changing the order of dimensions in the arrays makes it TLE on testcase 22 now: 88004254 but even with fast I/O and using StringBuilder, it still TLEs on testcase 22: 88005979. Its failing on the biggest testcase. It almost finishes, but TLEs while printing the output. Its about 2.12 times slower than the C++ solution, so it fails the time limit.