Wrong answer in Flipping Coins

range
segment-tree

#1

I am getting wrong answer in Flipping Coins. This is my code, can anyone help me to figure out what is wrong.


#2

Did you try debugging yourself first? The error was quite prudent.

Input
4 5
1 0 0
0 0 0 
1 0 0
0 0 3
1 0 0
Your Output
0
1
3
Expected Output
0
1
0 (We are only inquiring for rang [0,0], and the coin is flipped twice by the time last query happens)

#3

There is some issue with your input class(I checked on codechef compiler)… hence please use “Scanner” class from
java.util.Scanner


#4

alt text


#5

@vijju123

I clicked the link from this page and copied and pasted the code from there.

Anyways I have updated the the input class in the below solution. and this input class has been copied from one AC solution so there is no possibility of it to be incorrect.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class FlippingCoins {

    static int tree[] = new int[400010];
    static int lazy[] = new int[400010];
    static final int UNDEFINED = -1;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Reader reader = new Reader();
        StringBuilder sbr = new StringBuilder();
        int n, q;
        String s[];
        //s = br.readLine().split("\\s");
        n = reader.nextInt();
        q = reader.nextInt();
        Arrays.fill(lazy, 0, 200010, 0);
        for (int i = 0; i < q; i++) {
            //s = br.readLine().split("\\s");
            int type = reader.nextInt();
            int A = reader.nextInt();
            int B = reader.nextInt();
            if (type == 1) {
                sbr.append(query(1, 0, n - 1, A, B)).append("

");
} else {
update(1, 0, n - 1, A, B);
}
}
System.out.print(sbr.toString());
}

    private static int query(int id, int start, int end, int a, int b) {
        if (a > end || b < start) {
            return 0;
        }
        if (start >= a && end <= b) {
            return tree[id];
        }
        if (lazy[id] > 0) {
            shift(id, start, end);
        }
        int mid = (start + end) / 2;
        return query(id << 1, start, mid, a, b) + query((id << 1) + 1, mid + 1, end, a, b);
    }

    private static void update(int id, int start, int end, int a, int b) {
        if (a > end || b < start) {
            return;
        }
        if (start >= a && end <= b) {
            updateNode(id, start, end);
            return;
        }
        if (lazy[id] > 0) {
            shift(id, start, end);
        }
        int mid = (start + end) / 2;
        update(id << 1, start, mid, a, b);
        update((id << 1) + 1, mid + 1, end, a, b);
        tree[id] = tree[id << 1] + tree[(id << 1) + 1];
    }

    private static void updateNode(int id, int start, int end) {
        lazy[id] = 1-lazy[id];
        tree[id] = (end - start + 1) - tree[id];
    }

    private static void shift(int id, int start, int end) {
        int mid = (start + end) / 2;
        lazy[id << 1] = lazy[id];
        lazy[(id << 1) + 1] = lazy[id];
        tree[id << 1] = (mid - start + 1) - tree[id<<1];
        tree[(id << 1) + 1] = (end - (mid + 1) + 1) - tree[(id << 1) + 1];
        /*updateNode((id << 1), start, mid);
        updateNode((id << 1) + 1, start, mid);*/
        lazy[id] = 0;
    }
}

class Reader {
    static BufferedReader reader;
    static StringTokenizer tokenizer;

    Reader() {
        reader = new BufferedReader(
                new InputStreamReader(System.in) );
        tokenizer = new StringTokenizer("");
    }

    static String next() throws IOException {
        while ( ! tokenizer.hasMoreTokens() ) {
            tokenizer = new StringTokenizer(
                    reader.readLine() );
        }
        return tokenizer.nextToken();
    }

    public int[] nextIntArray(int n) throws IOException {
        int[] a = new int[n];
        for(int i=0;i<n;i++) a* = nextInt();
        return a;
    }
    public long[] nextLongArray(int n) throws IOException {
        long[] a = new long[n];
        for(int i=0;i<n;i++) a* = nextLong();
        return a;
    }
    public double[] nextDoubleArray(int n) throws IOException {
        double[] a = new double[n];
        for(int i=0;i<n;i++) a* = nextDouble();
        return a;
    }

    static int nextInt() throws IOException {
        return Integer.parseInt( next() );
    }
    static long nextLong() throws IOException {
        return Long.parseLong(next());
    }
    static double nextDouble() throws IOException {
        return Double.parseDouble( next() );
    }
}

#6

deleted…


#7

##Hey your problem is solved… finally… I understood your whole code
#there is some problem with shift function… line number 75 and 76 should be
lazy[id << 1] = 1-lazy[id << 1] ; lazy[(id << 1) + 1] = 1-lazy[(id << 1) + 1] ;
#instead of
lazy[id << 1] = lazy[id] ; lazy[(id << 1) + 1] = lazy[id] ;

Its obvious here we have to flip the lazy segment each time it needs update… no need to make it as parent…

#let’s say I have 2,3 child nodes and 1 as parent
##and 2 is marked and 3 as not
#then if I update node 1 then I have to make

3 as marked and 2 as not… obviously…

#just flip it…


#8

@vijju123

Where did you execute my code, I am getting answer as expected i.e, 0 1 0 on my laptop as well as codechef’s online IDE.


#9

he is right… 0 1 3 is the output… I did on codechef compiler


#10

I guess this problem also affected your solution of that spoj SALMAN problem


#11

@l_returns

What is the issue with my input class, I am able to take the inputs using that class.


#12

I just checked that soln gives TLE on using scanner class… so I am trying some FAST I/O methods and will reply you if it works shortly…


#13

@l_returns did you use the exact code on the pastebin link.


#14

first problem I found is I had to add “class” before FlippingCoins
and then the output was as follows… maybe copying code have a problem to me and vijju
OR you have two versions of code…


#15

yeah I just freshly copied that code from “raw” page from pastebin link


#16

just added “class” before “FlippingCoins” because that was giving compilation error…


#17

take outputs by taking random inputs and compare it with THIS solution


#18

To verify I have also copied the code from pastebin and tried to execute it.


#19

@l_returns

I have also tried by copying input class from one AC solution but I am still getting the WA.


#20

I fear that you gave wrong solution link for pastebin then. The solution at that link gave

0 1 3

as output