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

×

codeforces 414B help

codeforces 414B << link
solution i was looking at >> 31509108

There's a note at bottom that says: [1, 2], [1, 3] will be lists included.
if i divide 1 by 2 (successor) as 1/2=0.5 or leaves remainder as 1.
and also b1 <= b2 therefore the list can't be [2,1]. Why is [1,2] included in the good sequence?
Can we consider fractions?
So i tried looking at the above mentioned solution but couldn't get it. I am able to solve dp problems with usually 1D array memorization much easily but fail implementing such where we need 2D. Am i missing some concepts of DP or is it only a matter of practice. How to i get to form logics for such problems. Shall I take some tutorials or learn practicing?
* i am a newbie started a month ago, and don't have any idea about combinatorics, so need guidance.

asked 24 Oct '17, 20:33

ashigahlawat's gravatar image

2★ashigahlawat
875
accept rate: 0%

edited 24 Oct '17, 20:44


http://codeforces.com/contest/414/submission/30988220 Here is my solution. What i did was to at first generate all the factors for all no.s from 1 to n and store them in a vector. factors[i] is a vector that stores all the factors of i. Now i need sequences of length k so my dp states become k(in my code it is n in the function) the current index i am at and l i.e the last element chosen in current set.So to choose 1 more element i need to choose some factor of l. Read my code hopefully you will get it.

link

answered 24 Oct '17, 21:43

soham1234's gravatar image

6★soham1234
1.8k614
accept rate: 22%

1

Btw read it properly ai|a(i+1) means ith no.in set divides (i+1)th no.

(24 Oct '17, 21:53) soham12346★

yeh thats "|" and not"/". thanks soham

(24 Oct '17, 22:00) ashigahlawat2★
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:

×2,214
×900
×688

question asked: 24 Oct '17, 20:33

question was seen: 737 times

last updated: 24 Oct '17, 22:00