codeforces 414B help

general
, ,
1

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

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.

2 Likes
3

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

1 Like
4

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