BinaryBubble's blog

By BinaryBubble, history, 5 weeks ago, In English

Hello guys!

Most of you know about the legendary one stop CP Topic List created by YouKn0wWho (for those who don't know can check it out here).

Personally I'm not a fan of this cool UI in CP related things. I like it to be simple and it was too complex for my cyan brain to understand. (really personal opinion so don't jump on me for that :D)

So what i did is i scraped the ultimate topic list and put it all in a spreadsheet for me and y'all to have it.

Here's the link: CP Topic List (Jus make a copy and you'll be able to edit it as your personal sheet)

Here's an SS of how my personal one looks like :P

My Sheet

There's two things I'd also like you to know about this list.

  • You can sort everything by Serial Number and it will be divided chunk wise into more general topics like maths and graphs

  • You can sort everything by Difficulty and it will be divided into 3 chunks of increasing or decreasing difficulty.

I'd also like to ask you guys. what rating range does difficulty 1, 2 and 3 map to? feel free to comment and I'll attach the best ones in the blog for others.

Rating Ranges for Difficulties

  • 1 — [0 — 2400] Quoting galen_colin, "you basically could get to red with just the basics every red coder in the forum agreed"
  • 2 — [yet to be decided]
  • 3 — [yet to be decided]

Thankyou for reading!

Special Thanks to ORZ YouKn0wWho

Full text and comments »

  • Vote: I like it
  • +48
  • Vote: I do not like it

By BinaryBubble, history, 3 months ago, In English

During the Educational CF Round 128 while solving problem C, I stumbled upon a cheeky DP based solution to the problem.

Problem: 1997C - Even Positions

(it doesn't even have a dp tag)

for those who're too lazy to click on the link, in short the problem says that.

we're given a sequence a Bracket sequence which was originally a valid bracket sequence but now every odd position element is lost and we have the remaining sequence (eg: _(_)_)). now we need to find the minimum cost between all the possible valid sequences where the cost of a sequence is summation of the distance between each opening and its corresponding closing bracket (eg: for _(_)_) a possible valid sequence can be (())() and its cost would be $$$3 + 1 + 1 = 5$$$).

Now given the incomplete bracket sequence we need to find the minimum possible cost among all the possible valid sequences.

Constraints are so that its always possible to construct a valid sequence.

Solution I found:

we can say that $$$dp[i] = \text{minimum cost if we just consider the suffix from i to n}$$$

the base case will be $$$dp[n] = 1$$$ as last element will always be ) and the only valid answer for that is always () which gives 1 as the minimum cost. we can clearly see this in the figure below.

Image to show that only the top left combination works which gives the answer for base case as 1

now the transition from one state to next state will be

$$$dp[i] = dp[i + 1] + 1$$$ (if we stumble upon ))

or $$$dp[i] = dp[i + 1] + 3$$$ (if we stumble upon ().

we can just create our answer all the way to $$$i = 1$$$ and our final solution will be at $$$dp[1]$$$ (PS: we're considering 1 based indexing here)

now why does it work ? let's look at some bigger cases.

We can observe that no matter which type of bracket we get we can always create smaller brackets whose cost will be 1.

if we get ) we just create a smaller bracket but if we get ( we still create a smaller bracket of cost 1 but we push it inside a bigger bracket whose cost keeps increasing by 2 with each incoming (.

so why $$$+3$$$ ? $$$+3$$$ represents the increase in size of the bigger bracket by $$$+2$$$ and a creation of smaller bracket which costs $$$+1$$$ in total giving us a $$$+3$$$.

Here's an AC solution to the problem with this approach: 277181878

PS: This is my first blog so feel free to leave any suggestions/feedback and Sorry for any mistake i made :)

Full text and comments »

  • Vote: I like it
  • +16
  • Vote: I do not like it