You are not logged in. Please login at www.codechef.com to post your questions!

×

Wrong answer in Flipping Coins

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

asked 02 Jun, 14:36

arpit728's gravatar image

2★arpit728
6831149
accept rate: 10%


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...

link

answered 03 Jun, 15:23

l_returns's gravatar image

5★l_returns
1.0k18
accept rate: 27%

edited 03 Jun, 15:32

one more overflow problem is you don't need shift when it's a leaf...

but It won't give wrong answer as your array declaration size is too large..

but surely..

if (lazy[id] > 0)

should be

if (lazy[id] > 0 && start!=end)

(03 Jun, 15:36) l_returns5★
1

HERE is your accepted solution

(03 Jun, 15:38) l_returns5★

@l_returns

Thank you so much for devoting too much time and find out what was wrong I almost gave up on this problem.

I have finally got accepted.

I wrote shift function that way so that the remaining changes of parents could propagated to children. Did you understand why my shift function didn't work.

(03 Jun, 16:42) arpit7282★
1

Yeah I do mentioned what was wrong...

In the example I gave above in this answer.. your code will either mark both or it unmark both...

Note that "mark" means lazy[node] = 1.

And unmark means lazy[node] =0

(03 Jun, 17:06) l_returns5★

@l_returns

You have done a great help to me in solving this question. I am really very thankful to you for this one.

Thank you.

(06 Jun, 21:27) arpit7282★

Welcome :)

(07 Jun, 00:25) l_returns5★
showing 5 of 6 show all

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)
link

answered 02 Jun, 14:45

vijju123's gravatar image

5★vijju123 ♦
14.2k11349
accept rate: 18%

@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.

(02 Jun, 15:01) arpit7282★
1

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

(02 Jun, 15:16) l_returns5★

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

link

answered 02 Jun, 15:19

l_returns's gravatar image

5★l_returns
1.0k18
accept rate: 27%

edited 02 Jun, 15:19

1

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

(02 Jun, 15:22) l_returns5★

@l_returns

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

(02 Jun, 15:24) arpit7282★
1

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..

(02 Jun, 15:24) l_returns5★
1

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

(02 Jun, 15:40) l_returns5★

@l_returns

MAX 262143 // Why?

(02 Jun, 21:28) arpit7282★

Because the next multiple of 2 after 10^5 is 131072 and if I had n=131072 then I need exactly 131072+131071 = 262143 integers to store whole tree without any overflow of bounds
So it's a safe number to define size of tree when inputs are less than 131072.
Though you can use 262144 for being more safe..

(02 Jun, 23:21) l_returns5★

Trees are always to me made about keeping n= next multiple of 2 after the real n

(02 Jun, 23:23) l_returns5★
showing 5 of 7 show all

alt text

link

answered 02 Jun, 15:23

arpit728's gravatar image

2★arpit728
6831149
accept rate: 10%

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

(02 Jun, 15:34) arpit7282★
1

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...

(02 Jun, 15:34) l_returns5★

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

(02 Jun, 15:35) l_returns5★
1

just added "class" before "FlippingCoins" because that was giving compilation error...

(02 Jun, 15:35) l_returns5★

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

(02 Jun, 15:44) arpit7282★

@l_returns

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

(02 Jun, 15:47) arpit7282★

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

0 1 3

as output

(02 Jun, 15:55) vijju123 ♦5★

@vijju123

Also tried on ideone with the same pastebin code.

https://ideone.com/jN6fHk

(02 Jun, 16:12) arpit7282★
showing 5 of 8 show all

@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("\n");
            } 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[i] = nextInt();
        return a;
    }
    public long[] nextLongArray(int n) throws IOException {
        long[] a = new long[n];
        for(int i=0;i<n;i++) a[i] = nextLong();
        return a;
    }
    public double[] nextDoubleArray(int n) throws IOException {
        double[] a = new double[n];
        for(int i=0;i<n;i++) a[i] = 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() );
    }
}
link

answered 02 Jun, 16:10

arpit728's gravatar image

2★arpit728
6831149
accept rate: 10%

I dont think this is the code given at link. Just check line no. 9 in both. Its public class FlippingCoins here, and only FlippingCoins there

(02 Jun, 16:13) vijju123 ♦5★

@vijju123

That's not going to make any difference and codechef compiler won't let you run your code with public class unless the name is Main.

(02 Jun, 16:18) arpit7282★

@vijju123

Also tried on ideone with the same pastebin code.

https://ideone.com/jN6fHk

(02 Jun, 16:18) arpit7282★

Get the point of the comment dude, not the superficial stuff. The point was that the code at link was not same as what you pasted above which led to different outputs at that case.

(02 Jun, 16:24) vijju123 ♦5★

@vijju123

I am sorry about that.

I do admit line-9 is different in both the codes but it's not going to impact the output.

Also you can look at ideone code that is same as the pastebin link.

(02 Jun, 16:35) arpit7282★

deleted........

link

answered 02 Jun, 19:36

vijju123's gravatar image

5★vijju123 ♦
14.2k11349
accept rate: 18%

edited 03 Jun, 14:00

@vijju123

Thank you so much for finding out the failing test case for my code. Can you please tell me how did you got there.

(02 Jun, 20:03) arpit7282★

I saw that the lazy propagation isnt correct implemented. After that, I just had to find a case to fail it. A large $N$ makes it easy for me. If you try for $N<100$ , it can be tough or time taking to frame the case.

(02 Jun, 20:54) vijju123 ♦5★

@vijju123

Can you please point out what is wrong with my lazy propagation.

(03 Jun, 11:44) arpit7282★

Not 100% sure though, but I feel you should always tend to check if any remaining update is there at the node, and then do any other check. I see you did handled it in your own way, but I cannot guarantee that its correct (it can be, but I cant say)

(03 Jun, 12:06) vijju123 ♦5★

@vijju123

I think there is problem with the test cases of this problem I have seen the accepted solutions generating same output as that of mine for the test case which you mentioned.

https://www.codechef.com/viewsolution/18735597

(03 Jun, 13:28) arpit7282★

Ok, will add it in to-see list.

(03 Jun, 13:40) vijju123 ♦5★

@vijju123

In fact output of my code is correct for the test case which you have specified because other then (53-59) interval (65-67) is also active.

(03 Jun, 13:48) arpit7282★

Looks like I made a mistake. Sorry.

(03 Jun, 14:00) vijju123 ♦5★
showing 5 of 8 show all
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,629
×53

question asked: 02 Jun, 14:36

question was seen: 260 times

last updated: 07 Jun, 00:25