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

×

problem with implementation of partition problem from jan long

Guys can anyone point out the problem in my implementation of partition problem. I wrote two implementation with same logic and both gave wa on diff set of tcs. implementation 1 : here implementation 2 : here

Thanks in advance. It will help me a lot

asked 15 Jan '18, 16:58

vikaskodag98's gravatar image

4★vikaskodag98
512
accept rate: 0%


In you first solution, you have taken variable i as int then it could be overflow that's why you got wrong answer.

link

answered 15 Jan '18, 17:22

chhekur's gravatar image

1★chhekur
233
accept rate: 0%

i think variable i wouldnt overflow because i can never greater than n. and constraints on n are 2 ≤ N ≤ 1,000,000. if you found anything else tell or if i am leaving anything in my implementation.

(15 Jan '18, 17:54) vikaskodag984★

counter case for 2nd implementation is: n = 15, x = 12

I would suggest to generate some random input and test your program if you get wrong answer and are unable to figure it out

Hope this helps

link

answered 15 Jan '18, 17:42

inovation123's gravatar image

4★inovation123
4537
accept rate: 10%

thanks for the tc @inovation123

(15 Jan '18, 18:12) vikaskodag984★

The solution for 2nd implementation would work if you would write else if instead of if when you are checking that whether sum is greater than i or not.

link

answered 15 Jan '18, 17:46

nikesh_04's gravatar image

1★nikesh_04
443
accept rate: 0%

thanks bro it worked. i check what i did wrong there.

(15 Jan '18, 18:12) vikaskodag984★

Hey @vikaskodag98 :) Well your second implementation is a bit buggy. It will fail at some test cases like: 24,32 ; 12 15 ; 65 90 etc... Suppose the test case is (12,15) then your program will evaluate 'sum' initially as 54. Since you are iterating from last number i.e. 15, a[15]=1 (as sum= 54 is well greater than i=15) and it continues till i=13 where sum remains to be 25. Here your program decrements i as (sum-i)==x gets true(since x=12 here). Now you are left with i=12 and sum= 25 and since (sum>i) gets true in your second if block you evaluate a[12]= 1 which is wrong.

link

answered 15 Jan '18, 18:18

ayush_0101's gravatar image

3★ayush_0101
512
accept rate: 28%

thanks for pointing out the mistake @ayush_0101. It was a silly mistake i overlooked.

(15 Jan '18, 18:26) vikaskodag984★
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:

×191
×33

question asked: 15 Jan '18, 16:58

question was seen: 463 times

last updated: 15 Jan '18, 18:26