SLIMSHADYNICK's blog

By SLIMSHADYNICK, history, 4 years ago, In English

I need help in this problem. I have tried all the test cases on Udebug as well, they are passing. But Vjudge is not accepting my code.



import java.io.DataInputStream; import java.io.FileInputStream; import java.io.IOException; class Investigation { static class Reader { final private int BUFFER_SIZE = 1 << 16; private DataInputStream din; private byte[] buffer; private int bufferPointer, bytesRead; public Reader() { din = new DataInputStream(System.in); buffer = new byte[BUFFER_SIZE]; bufferPointer = bytesRead = 0; } public Reader(String file_name) throws IOException { din = new DataInputStream(new FileInputStream(file_name)); buffer = new byte[BUFFER_SIZE]; bufferPointer = bytesRead = 0; } public String readLine() throws IOException { byte[] buf = new byte[64]; // line length int cnt = 0, c; while ((c = read()) != -1) { if (c == '\n') break; buf[cnt++] = (byte) c; } return new String(buf, 0, cnt); } public int nextInt() throws IOException { int ret = 0; byte c = read(); while (c <= ' ') c = read(); boolean neg = (c == '-'); if (neg) c = read(); do { ret = ret * 10 + c - '0'; } while ((c = read()) >= '0' && c <= '9'); if (neg) return -ret; return ret; } public long nextLong() throws IOException { long ret = 0; byte c = read(); while (c <= ' ') c = read(); boolean neg = (c == '-'); if (neg) c = read(); do { ret = ret * 10 + c - '0'; } while ((c = read()) >= '0' && c <= '9'); if (neg) return -ret; return ret; } public double nextDouble() throws IOException { double ret = 0, div = 1; byte c = read(); while (c <= ' ') c = read(); boolean neg = (c == '-'); if (neg) c = read(); do { ret = ret * 10 + c - '0'; } while ((c = read()) >= '0' && c <= '9'); if (c == '.') { while ((c = read()) >= '0' && c <= '9') { ret += (c - '0') / (div *= 10); } } if (neg) return -ret; return ret; } private void fillBuffer() throws IOException { bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE); if (bytesRead == -1) buffer[0] = -1; } private byte read() throws IOException { if (bufferPointer == bytesRead) fillBuffer(); return buffer[bufferPointer++]; } public void close() throws IOException { if (din == null) return; din.close(); } } public static void main(String[] args)throws IOException { Reader s=new Reader(); int test=s.nextInt(); int c=1; while(test--!=0){ char a[]=Long.toString(s.nextLong()-1).toCharArray(); char b[]=Long.toString(s.nextLong()).toCharArray(); int m=s.nextInt(); if(m>=100){ System.out.println("Case "+c+": 0"); c++; continue; } long r=solve(b,m); long l=solve(a,m); // System.out.println(l+" "+r); long ans=r-l; System.out.println("Case "+c+": "+ans); c++; } } public static long solve(char a[],int m){ int n=a.length; long dp[][][][]=new long[n+1][m][m][2]; dp[0][0][0][1]=1; for(int i=1;i<=n;i++){ int cd=a[i-1]-48; for(int p=0;p<=9;p++){ for(int j=0;j<m;j++){ int nj=(j*10+p)%m; for(int k=0;k<m;k++){ int nk=(k+p)%m; if(p<cd){ dp[i][nj][nk][0]+=dp[i-1][j][k][0]+dp[i-1][j][k][1]; } else if(p==cd){ dp[i][nj][nk][0]+=dp[i-1][j][k][0]; dp[i][nj][nk][1]+=dp[i-1][j][k][1]; } else{ dp[i][nj][nk][0]+=dp[i-1][j][k][0]; } } } } } return dp[n][0][0][1]+dp[n][0][0][0]; } }

Here's the problem Link

Tags #dp
  • Vote: I like it
  • -40
  • Vote: I do not like it

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

Auto comment: topic has been updated by SLIMSHADYNICK (previous revision, new revision, compare).

»
4 years ago, # |
  Vote: I like it +26 Vote: I do not like it

First of all, you say your code isn't being accepted. What is the verdict? Wrong answer/RTE/TLE? What do you want us to be looking for here?

Second, have you tried writing a brute forcer to generate a break case? It is quite easy to write a naive O(biggestNumber) solution that just checks every number in the range. In the future, please at least try writing a naive solution to find an obvious break case before DMing me and posting a blog asking others to debug your code.

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

    It is saying wrong answer sir. Secondly, as I said I just wanted to check if the java submission is getting accepted or not, as I have tried various test cases on Udebug, and my outcome matches expected outcome.

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

      What do you mean you 'want to check if it is getting accepted'? If it is getting wrong answer as you said, then it isn't getting accepted.

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

        I mean if there is a problem with java. As there were no accepted submissions in java.

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

          That's simply not true. The user: avijit_agarwal got an accepted java submission in Java that ran in ~300 ms. Here's the submission link. I don't think there is an issue with java.

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

            thx a lot! Now I can see the error if there's any!

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

Auto comment: topic has been updated by SLIMSHADYNICK (previous revision, new revision, compare).