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

×

Dynamic Programming Problem

How to solve the problem STANOVI from COCI contest 4 ?

http://hsin.hr/coci/contest4_tasks.pdf It is the 6th problem.

asked 02 Jan '15, 02:15

neo1tech9_7's gravatar image

6★neo1tech9_7
8.5k51537
accept rate: 19%

Any ideas on how to solve ? @neo1tech9_7

(04 Jan '15, 00:38) Organic-Shilling0★

well I know what the states of the dp are but I don't know how to calculate them efficiently or how to transition between them there are n.m.16 states consider a cell x,y then it has an edge with x - 1, y, x + 1, y , x, y + 1, x, y - 1 so in total 4 edges and 2^4 possible subsets (think each edge on and off) since there are n.m cells so in total n.m.16 states

(04 Jan '15, 04:24) neo1tech9_76★

I may be wrong though.

(04 Jan '15, 06:27) neo1tech9_76★

upd : editorials will be released in a day or two.

(05 Jan '15, 12:59) neo1tech9_76★
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,966
×9

question asked: 02 Jan '15, 02:15

question was seen: 522 times

last updated: 05 Jan '15, 12:59