lazypanda's blog

By lazypanda, history, 2 months 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

Read more »

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

By lazypanda, history, 3 months ago, In English

Can anyone explain how can I improve submission link..

Read more »

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

By lazypanda, history, 3 months ago, In English

Problem Link ~~~~~ import java.io.*; import java.util.Arrays; import java.util.StringTokenizer;

public class Present { 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 n=s.nextInt();
    int a[]=new int[n+1];
    for(int i=1;i<=n;i++){
        a[i]=s.nextInt();
    }
    int ans=0;
    for(int i=0;i<=25;i++){
        int b[]=getArray(a,i);
        Arrays.sort(b);
        long count=getCount(b,n,i);
        if(count%2!=0){
            ans|=1<<i;
        }
    }
    System.out.println(ans);
}
public static int[] getArray(int a[],int k){
    int b[]=new int[a.length];
    int t=1<<(k+1);
    for(int i=1;i<a.length;i++){
        b[i]=a[i]%t;
    }
    return b;
}
public static long getCount(int b[],int n,int k){
    long ans=0;
    int left1=1<<k;
    int right1=1<<(k+1);
    int left2=(1 << k) + (1 << (k + 1));
    int right2=1 << (k + 2) - 1;
    int x=n+1;
    for(int i=1;i<=n;i++){
        int rc=getInd(b,i,n,left1);
        if(rc==x){
            continue;
        }
        int lc=getInd(b,i,n,right1);
        ans+=lc-rc;
        if(k!=0) {
            rc = getInd(b, i, n, left2);
            if(rc==x){
                continue;
            }
            lc = getInd(b, i, n, right2);
            ans += lc - rc;
        }
    }
    return ans;
}
public static int getInd(int a[],int ind,int n,int reqd){
    int num=a[ind];
    int low=ind+1;
    int high=n;
    int ans=n+1;
    while(low<=high){
        int mid=(low+high)/2;
        if(a[mid]+num>=reqd){
            ans=mid;

Read more »

 
 
 
 
  • Vote: I like it
  • -10
  • Vote: I do not like it

By lazypanda, history, 6 months ago, In English
 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By lazypanda, history, 6 months ago, In English

I have been working around this question for quiet sometime :( https://www.spoj.com/problems/CT23E/ . Can anyone please help me how to approach this particular problem?

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By lazypanda, history, 7 months ago, In English

I tried solving the problem the following way: 1) Using dfs I maintained the euler tour of the graph,height(or depth) of nodes,along with first and last occurence of index in euler tour. 2) Built a segment tree to give the minimum depth node in an interval along with its index. 3) Built another segment tree to give the number of different colors within an interval in the euler tour array.(I used Bitsets in java here). 4) for each query I calculate first the lca of the given nodes, call it X,using first segment tree. 5) then using first and last pos of X in the euler tour I calculate the number of different colors in this interval,using second segment tree.

But unfortunately I have been getting TLE at 15th test case. I tried optimising it a lot but its not working. Any help would be appreciated!

UPDATE: Instead of using segment tree to find the number of different color,instead for each node I calculated the number of different colors in a subtree using BitSet while dfs itself only. Now I'm calculating only the lca in log(n) time while answering the number of different colors in a subtree in O(1). But guess what? Now I'm getting NZEC on the same test case 15 which I don't get why:(. Any help would be appreciated:)

UPDATE: GOT accepted with c++ the same logic!

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By lazypanda, history, 7 months ago, In English

There's this problem INVPHI on spoj, I have not been able to solve it. I have been getting NZEC runtime error. Could anyone tell me how to approach as I feel I have exceeded the memory limitations.

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it