×

# Wrong answer in Flipping Coins

 0 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 '18, 14:36 1★arpit728 683●19●68 accept rate: 10%

# 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] ;

lazy[id << 1] = lazy[id] ; lazy[(id << 1) + 1] = lazy[id] ;

1.6k211
accept rate: 23%

# but surely..

if (lazy[id] > 0)

# should be

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

(03 Jun '18, 15:36)
1

# HERE is your accepted solution

(03 Jun '18, 15:38)

@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 '18, 16:42) 1★
1

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

## And unmark means lazy[node] =0

(03 Jun '18, 17:06)

@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 '18, 21:27) 1★

Welcome :)

(07 Jun '18, 00:25)
showing 5 of 6 show all
 0 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)  answered 02 Jun '18, 14:45 15.5k●1●20●66 accept rate: 18% 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 '18, 15:01) arpit7281★ 1 he is right... 0 1 3 is the output... I did on codechef compiler (02 Jun '18, 15:16) (02 Jun '18, 23:55) arpit7281★
 0 There is some issue with your input class(I checked on codechef compiler)... hence please use "Scanner" class from java.util.Scanner answered 02 Jun '18, 15:19 1.6k●2●11 accept rate: 23% 1 I guess this problem also affected your solution of that spoj SALMAN problem (02 Jun '18, 15:22) @l_returns What is the issue with my input class, I am able to take the inputs using that class. (02 Jun '18, 15:24) arpit7281★ 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 '18, 15:24) 1 take outputs by taking random inputs and compare it with THIS solution (02 Jun '18, 15:40) @l_returns MAX 262143 // Why? (02 Jun '18, 21:28) arpit7281★ 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 '18, 23:21) Trees are always to me made about keeping n= next multiple of 2 after the real n (02 Jun '18, 23:23) showing 5 of 7 show all
 0 answered 02 Jun '18, 15:23 1★arpit728 683●19●68 accept rate: 10% @l_returns did you use the exact code on the pastebin link. (02 Jun '18, 15:34) arpit7281★ 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 '18, 15:34) yeah I just freshly copied that code from "raw" page from pastebin link (02 Jun '18, 15:35) 1 just added "class" before "FlippingCoins" because that was giving compilation error... (02 Jun '18, 15:35) To verify I have also copied the code from pastebin and tried to execute it. (02 Jun '18, 15:44) arpit7281★ @l_returns I have also tried by copying input class from one AC solution but I am still getting the WA. (02 Jun '18, 15:47) arpit7281★ I fear that you gave wrong solution link for pastebin then. The solution at that link gave 0 1 3 as output (02 Jun '18, 15:55) @vijju123 Also tried on ideone with the same pastebin code. https://ideone.com/jN6fHk (02 Jun '18, 16:12) arpit7281★ showing 5 of 8 show all
 0 @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
 0 deleted........ answered 02 Jun '18, 19:36 15.5k●1●20●66 accept rate: 18% @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 '18, 20:03) arpit7281★ 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 '18, 20:54) @vijju123 Can you please point out what is wrong with my lazy propagation. (03 Jun '18, 11:44) arpit7281★ 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 '18, 12:06) @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 '18, 13:28) arpit7281★ Ok, will add it in to-see list. (03 Jun '18, 13:40) @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 '18, 13:48) arpit7281★ Looks like I made a mistake. Sorry. (03 Jun '18, 14:00) showing 5 of 8 show all
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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,768
×58

question asked: 02 Jun '18, 14:36

question was seen: 326 times

last updated: 07 Jun '18, 00:25