Wrong answer in Flipping Coins

general
21

@vijju123

Also tried on ideone with the same pastebin code.

22

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

23

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

24

@vijju123

Also tried on ideone with the same pastebin code.

25

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.

26

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

27

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

28

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.

29

@l_returns

MAX 262143 // Why?

30

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ā€¦

31

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

32

@l_returns

Can you look into this.

https://discuss.codechef.com/questions/128380/getting-tle-in-basic-lazy-propagation-problem-updateit-from-spoj

33

@vijju123

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

34

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)

35

@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

36

Ok, will add it in to-see list.

37

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

38

Looks like I made a mistake. Sorry.

39

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

40

#HERE is your accepted solution

1 Like