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

×

Help required

Can anyone get me the solution of

https://www.codechef.com/COWH2017/problems/COWHR102/ Thanks in advance

asked 09 Aug, 19:32

adhish_kapoor's gravatar image

2★adhish_kapoor
9048
accept rate: 9%

@vijju123 How to count...any idea ?

(09 Aug, 19:52) adhish_kapoor2★

I think you can refer to catlan number.

Thinking-

Catlna number denotes the number of "balanced bracket sequences" (known fact).

[Balance bracket sequences mean, The sequence of brackets of "{" and "}" is closed, eg "{{{}}}".]

Assume husband to be '{' and wife to be '}' . Now, the condition reduces to, that, the brackets should be balanced.

(A bracket sequence can never be balanced if "}" comes before "{"-Equivalent to a wife sitting before her husband)

Try this approach and see if it works. If it doesnt, get back to me, didnt tested yet. Kind of stuck atm :(

link

answered 09 Aug, 23:40

vijju123's gravatar image

5★vijju123 ♦
9.7k213
accept rate: 18%

Ok...I will try

(10 Aug, 00:22) adhish_kapoor2★

Refer to wiki for catlan number. Geeksforgeeks for generation, or else you can simply store first 20 catlan numbers in an array and be done with. If it doesnt work, tell me.

(10 Aug, 00:24) vijju123 ♦5★

It is not working in my case. I don't know why. I just used the code of gfg to generate the Catalan numbers and printed as it was asked. Have I done something wrong? https://www.codechef.com/viewsolution/14895067

(10 Aug, 14:55) vishesh_3453★

@vijju123 Will you please have a look.

(10 Aug, 17:27) vishesh_3453★

I am looking into it right now. Sorry for delay, things are coming up and keeping me busy.

(10 Aug, 17:54) vijju123 ♦5★

The matter is solved. The test cases are INCORRECT (as i suspected- since its a excontest problem). The setter included the case for N=0 (for which he assumed answer to be 0) while constraints mention that N is between [1,20).

Also, i kind of dont agree with answer being 1 for N=0. You have nobody, so empty set could be an answer. Anyway, its just that, the constraints are incorrect. There is a case of N=0.

(10 Aug, 18:35) vijju123 ♦5★

No problem, I can understand :

EDIT: Oh I wrote it for your previous comment. Btw Thanks. I was really wondering why it's not working.:)

(10 Aug, 20:21) vishesh_3453★

Correction -

i kind of dont agree with answer being 1 for N=0.

Its i kind of dont agree with answer being 0 for N=0, since we have empty set. Sorry for confusion, idk what was on my mind.

(10 Aug, 20:25) vijju123 ♦5★
showing 5 of 8 show all

vijju123 has said rightly

link

answered 13 Aug, 01:21

anmolmishra's gravatar image

2★anmolmishra
112
accept rate: 0%

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,878

question asked: 09 Aug, 19:32

question was seen: 193 times

last updated: 13 Aug, 01:21