adaptatron's blog

By adaptatron, 5 weeks ago, In English

I created a blog that talks about 3 quirks of maps/multisets.

  1. Accessing non existent elements in maps keyed on characters may lead to WA.
  2. Accessing non existent elements in maps keyed on integers may lead to TLE.
  3. Using the fancy count operator in multisets may lead to TLE.

There's no new/unique insights, I just documented my personal experience with these quirks, along with the problems link where I first encountered this issue. It might be helpful to beginners in competitive programming.

https://cfstep.com/training/tutorials/general-techniques/quirks-of-non-existent-map-elements/

Full text and comments »

  • Vote: I like it
  • -17
  • Vote: I do not like it

By adaptatron, 5 weeks ago, In English

The editorial of D. Colored Balls mentions that the first part of the problem is a standard puzzle, so it doesn't go into too much details. However, what's standard to old timers is new learning opportunities for newcomers. At least, to me, it was not at all obvious why the given formula works, until I encountered a good visual proof for the same.

I created a video talking about the strategy to solve the puzzle, with proof.

https://youtu.be/3TbkZ1A489o?si=V6Qq5CoXdbAfPi6U

Full text and comments »

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

By adaptatron, 6 weeks ago, In English

Problem Link

Target Audience : If you are not able to come up with the $$$O(n^2)$$$ algorithm in 5 minutes, and the $$$O(n)$$$ algorithm in additional 5 minutes, this tutorial is for you. If you are a beginner to Dynamic Programming on Prefix, this 1D DP problem is a good starting point for you to learn the technique. This tutorial assumes that you already have some experience with 1D DP.

I came across a simple yet elegant problem, which might be trivial to some but a good learning experience for others. So I created a blog that talks about how to optimize DP transitions by switching from Pull DP to Push DP.

You can submit your $$$O(n^2)$$$ and $$$O(n)$$$ solution here : https://mirror.codeforces.com/group/7Dn3ObOpau/contest/517981

https://cfstep.com/training/tutorials/dp/push-dp-vs-pull-dp/

If you have an alternate solution for any of these problems, do let me know in the comments.

If you have more practice problems on this concept, please share them in the comments below and I'll add them to the practice contest.

Full text and comments »

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

By adaptatron, 6 weeks ago, In English

I created video editorial for H. The Most Reckless Defense from last Div 3 Round (CF Round 938). It talks about Bitmask DP, exponentials, and how to approach problems with long description.

Youtube Link : https://youtu.be/bBTW58NEoJ4?si=zItmAtlyEGBiNMG_

Here's a practice contest on bitmask and bitmask DP

If you need any help or hints for the practice problem, you can ask on my Discord Server or on the Twitter thread. In case you are interested, you can also checkout my youtube channel

Full text and comments »

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

By adaptatron, 2 months ago, In English

To improve, just upsolving problems is not enough. You also need to ask yourself at what point you diverged from the intended solution, or what you could've done differently to arrive at the intended solution.

I made a video editorial discussing my train of thoughts involved for solving D. Learning to Paint from last CodeTON Round. The video talks about how you can spot patterns in problems and use them to your advantage for future problems.

Youtube Link : https://youtu.be/EGp72-5MV8U?si=1l9kq1SFQ_qhFRro

If you need any help (for this problem only), you can ask on my Discord Server or on the Twitter thread. In case you are interested, you can also checkout my youtube channel

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By adaptatron, 2 months ago, In English

I made a video editorial discussing D. Birthday Gift from last Div 2 Round (CF Round 936). The video talks about how the concept of submasks can be helpful outside of subset counting problems.

Youtube Link : https://youtu.be/qZobx4EOVm0?si=LsPPCv4mi2szw-PR

Here's a practice contest on bitwise operations:

If you need any help or hints for the practice problem, you can ask on my Discord Server or on the Twitter thread. In case you are interested, you can also checkout my youtube channel

Full text and comments »

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

By adaptatron, 2 months ago, In English

Given an array of positive integers, for each element, you can choose to multiply it by $$$-1$$$. Find the maximum number of negative elements at the end, such that the prefix sum of the final array contains strictly positive integers only.

I created a short blog that talks about how the obviously incorrect greedy strategy for some problems can actually be fine-tuned to be correct, by going back and altering our choices.

To help you solidify the concepts discussed, I've created 1 + 1 practice problems. You can access them here: https://mirror.codeforces.com/group/7Dn3ObOpau/contest/513385

https://cfstep.com/training/tutorials/general-techniques/time-travel-in-greedy-algorithms/

If you have an alternate solution for any of these problems, do let me know in the comments.

If you have more practice problems on this concept, please share them in the comments below and I'll add them to the practice contest.

The problems are untested. If you see any issues, please let me know.

If you need any help or hints for the practice problem, you can ask on my Discord Server or on the Twitter thread. In case you are interested, you can also checkout my youtube channel

Full text and comments »

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

By adaptatron, 3 months ago, In English

I made a video editorial for CF1923E : Count Paths discussing the DP solution that acts as the foundation of the small to large trick.

Youtube Link : https://youtu.be/D454rHDUb6E?si=FtfBwoKG3_p-8m7f

I also created practice contest with easy problems:

Full text and comments »

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

By adaptatron, 3 months ago, In English

I made a video editorial discussing G. Vlad and Trouble at MIT from last Div 4 Round (CF Round 928). The video can act as a gentle introduction to Tree DP.

Youtube Link : https://youtu.be/xB2sZz7aa-M?si=z2eRU0dDai-jodmf

Here are 3 practice contests:

If you're a complete beginner, then you should only attempt these 3 problems : 1, 2 and 3

Full text and comments »

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

By adaptatron, 3 months ago, In English

The editorial for ABC340G: Leaf Color from last Atcoder Beginner Contest mentions an interesting exercise/subproblem for the readers

Fix a color and find the answer in $$$O(N)$$$ with Tree DP. Although not easy, it is a good exercise for blue coders, so we recommend you to think about it.

So I created a blog post that discusses how to find

  1. The number of induced subgraphs that are trees.
  2. Number of connected induced subgraphs with degree $$$d$$$ for any $$$d$$$.
  3. Number of connected induced subgraphs with degrees $$$0$$$, $$$1$$$ and $$$\geq 2$$$.
  4. Number of connected induced subgraphs with monochromatic degree 1 vertices.
  5. Followup problem to apply the concepts learned.

To help you solidify the concepts discussed, I've created 2 + 1 practice problems. You can access them here: https://mirror.codeforces.com/group/7Dn3ObOpau/contest/504547

https://cfstep.com/training/tutorials/trees/dp-on-induced-subgraphs-of-a-tree/

If you have an alternate solution for any of these problems, do let me know in the comments.

The problems are untested. If you see any issues, please let me know.

If you need any help or hints for the practice problem, you can ask on my Discord Server or on the Twitter thread. In case you are interested, you can also checkout my youtube channel

Full text and comments »

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

By adaptatron, 3 months ago, In English

ABC339G: Smaller Sum from the last week's ABC had restrictions for online query and someone in the comment section was interested in knowing the alternate easier solution if the queries could be answered offline. So, I've written a short blog that talks about how to use sweep line to answer these 2 problems:

  1. You are given an array and several queries. A query consists of a subarray and $$$x$$$. Print the sum of all elements from this subarray that are $$$\leq x$$$.
  2. You are given a tree and some queries. In each query $$$(x, y, T)$$$ print YES if there is a path from $$$x$$$ to $$$y$$$ such that the maximum value on that path is $$$ \leq T$$$.

To help you solidify the concepts discussed, I've created 1 + 1 practice problems. You can access them https://mirror.codeforces.com/group/7Dn3ObOpau/contest/503852

https://cfstep.com/training/tutorials/general-techniques/answering-queries-offline-with-sweepline/

The problems are untested. If you see any issues, please let me know.

If you need any help or hints for the practice problem, you can ask on my Discord Server. In case you are interested, you can also checkout my youtube channel

Full text and comments »

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

By adaptatron, 3 months ago, In English

Given an array, how do you efficiently find out the minimum xor pair. I've written a short blog discussing the idea behind it.

To help you solidify the concepts discussed, I've created 1 + 1 practice problems. You can access them here: https://mirror.codeforces.com/group/7Dn3ObOpau/contest/503551

https://cfstep.com/training/tutorials/bitwise-operations/xor-is-minimized-for-adjacent-sorted-elements/

The problems are untested. If you see any issues, please let me know.

If you need any help or hints for the practice problem, you can ask on my Discord Server. In case you are interested, you can also checkout my youtube channel

Full text and comments »

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

By adaptatron, 4 months ago, In English

The editorial of ARC171C mentions that the sum of $$$\prod deg(u)!$$$ over all spanning subgraphs can be computed using DP but doesn't mention how. So I created a blog post that discusses how to compute:

  1. Number of spanning subgraphs where root vertex has degree $$$d$$$.
  2. Sum of $$$\prod deg(u)!$$$ over all spanning subgraphs
  3. Sum of $$$\sum deg(u)$$$ over all spanning subgraphs

To help you solidify the concepts discussed, I've created 2 + 1 practice problems. You can access them here: https://mirror.codeforces.com/group/7Dn3ObOpau/contest/503270

https://cfstep.com/training/tutorials/trees/dp-on-spanning-subgraphs-of-a-tree/

The problems are untested. If you see any issues, please let me know.

Full text and comments »

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

By adaptatron, 4 months ago, In English

I've written a short blog discussing the idea of extending Binary Strings with DP. It also discusses the solution to problem E: Counting Binary Strings from last Div 2 round.

To help you solidify the concepts discussed, I've created 5 + 1 practice problems. You can access them here: https://mirror.codeforces.com/group/7Dn3ObOpau/contest/498710

https://cfstep.com/training/tutorials/strings/extending-binary-strings/

The problems are untested. If you see any issues, please let me know.

Full text and comments »

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

By adaptatron, 4 months ago, In English

I've written a short blog discussing the applications of Dijkstra's Algorithm (to find shortest path, second shortest path, monochromatic shortest paths, etc).

Target Audience : You've used Dijkstra's algorithm as a black box in the past. Or you have some understanding but not the complete picture of why the algorithm works.

To help you solidify the concepts discussed, I've created 1 + 3 practice problems.You can access them here: https://mirror.codeforces.com/group/7Dn3ObOpau/contest/497900

Can you write/prove Dijkstra’s algorithm without referring to external sources? What about BFS? If your answer to the first question is NO, and to the second question is YES, this tutorial is for you.

https://cfstep.com/training/tutorials/graphs/dijkstra-is-bfs-in-disguise/

Full text and comments »

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

By adaptatron, 4 months ago, In English

I made a video editorial discussing ABC335F : Hop Sugoroku. The video talks about how to use Distributing DP and optimize it using the square root trick.

Youtube Link

Easy version of the problems and practice problems can be found in this contest : https://mirror.codeforces.com/group/7Dn3ObOpau/contest/496787

Full text and comments »

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

By adaptatron, 5 months ago, In English

I've written a short blog discussing the applications of tracking time while performing DFS. It also discusses the (partial) solution to problem E: Happy Life in University from Good Bye 2023. To help you solidify the concepts discussed, I've created 4 + 1 practice problems.You can access them here: https://mirror.codeforces.com/group/7Dn3ObOpau/contest/496216

If you're familiar with DFS, but don't know what Euler Tour and Tree Flattening mean, this tutorial is for you.

https://cfstep.com/training/tutorials/trees/timer-on-trees/

Full text and comments »

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

By adaptatron, 5 months ago, In English

I made a video editorial discussing ABC334F : Christmas Present 2. The video talks about how to use the sliding window technique to optimize DP transitions.

Youtube Link

I also created 1D version of the problem, with 3 versions so that you can submit your $$$O(N^3)$$$, $$$O(N^2)$$$ and $$$O(N * Log(N))$$$ solution and verify the correctness. You can access the group using this link https://mirror.codeforces.com/group/7Dn3ObOpau In the contests section, you'll see a contest by the name DP + Sliding Window.

The problems are untested, so if you spot any issues, please let me know.

Full text and comments »

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

By adaptatron, 5 months ago, In English

I made a video editorial discussing Edu 160D — Array Collapse . The video talks about how to use monotonic stacks to perform DP transitions faster.

Youtube Link

I also created some basic problems to help you practice the stuff covered in the video. You can access the group using this link https://mirror.codeforces.com/group/7Dn3ObOpau In the contests section, you'll see a contest by the name Monotonic Stack + DP. If you want me to add even more basic problems, like finding the previous smaller element or next greater element, please let me know. The problems are untested, so if you spot any issues, please let me know.

Full text and comments »

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

By adaptatron, 5 months ago, In English

I made a video editorial discussing ABC 333 F — Bomb Game 2 . The video covers a common technique used in Probability DP problems, and how to handle cycles between DP states.

Youtube Link

I would appreciate your feedback!

Full text and comments »

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