CrypticTaiga's blog

By CrypticTaiga, history, 4 years ago, In English

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.

  • Vote: I like it
  • +9
  • Vote: I do not like it

| Write comment?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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 !

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.