I took a break from CP(no one cares ik, lmao) cause I was reaching a point where my additional efforts were sort of making me worse.
After spending some time away from CP I thought let's just focus on solving questions, forget about the rating and focus on my system since that is the only thing that I control. Even if it means not being able to come up with anything and looking at the editorial or the code. I do not need to be a perfectionist, just consistent, overtime the sheer volume of questions will make it so that I will be able to come up with approaches just by gauging similarity between questions.
Anyways, I plan to track my consistency, not my progress(tho I will give contests ofc) on this site since writing all of this will make me self reflect and be conscious of my system. My practice plan(feel free to give suggestions) is:
- Practice questions topic wise on clist.by
- The luck filter on the questions will be between 10 — 75 percent.
I may or may not be consistent due to my office work and the events that come associated with it, but I figured there is no harm in trying.
I'll log the questions and my understanding of their approaches(this is also something that you can comment on and give suggestions, if you feel to do so).
Currently I am practicing DP problems for the given week.
Practice time: 2 hrs
Revision questions:
None
Problem: New Rating
- Problem Link: this
- I was not able to solve this question, at all. I had to look up the editorial and to my frustration the solutions(binary search and DP) were pretty straightforward.
- For the DP solution, you can basically declare a two dimensional array $$$dp_{i,j}$$$ where $$$j \in {0,1,2}$$$ and each number for $$$j$$$ has a specific configurational meaning attached to it(there is no point in repeating it.) You can also declare a function $$$f(a,x)$$$ which returns the new value when the score is $$$a$$$ and the current rating is $$$x$$$. We will give the value of $$$dp_{i,j}$$$ here since they represent the maximum score possible for a prefix upto i.
- This is not the first time I have seen this sort of dynamic programming being used, I have encountered leetcode questions where we had to skip a subarray to compute one score and we ended up making a 2D-DP array with a constant second dimension.
- Point to remember : Whenever you get a computation problem in which you can skip at most one subarray, then you can use dynamic programming as shown in the editorial to solve that problem in $$$O(n)$$$ time.
Problem: Add Zeros
- Problem Link: this
- Thoughts
- For there to be a finite answer for maximum array length, the operation has to terminate at some point.
- This means that at some point we will be a array $$$a$$$ such that $$$\forall 1 \le i \le |a| \neg \exists i \text{such that} a_i + i = |a| + 1$$$.
- We can re-write the expression as: $$$a_i + i - 1 = |a|$$$. If we make $$$i$$$ be zero-indexed instead of 1-indexed as is used in the question, then: $$$a_i + i = |a|$$$
Approach 1:
- The idea of this approach is Graph + BFS based.
- For each $$$a_i$$$ I will compute $$$a_i + i$$$ and draw a directed edge from the former to the latter. Since $$$a_i + i$$$ represents some $$$|\alpha|$$$ the resulting graph would represent all the possible transitions that can be made from one array length to the other
- Now given the starting point $$$n$$$ we just need to find the largest length / vertex reachable. This can be done via a simple BFS.
- This approach passed :), although I had to use map<...> to make the graph and a set<...> to maintain the seen vertices, but other than that I am satisfied with the solution I came up with.
- Time complexity: $$$O((V + E)lg V)$$$ where $$$V$$$ and $$$E$$$ are the vertices and edges of the graph respectively.
Problem: Kosuke's assignment
- Problem Link: [this](https://codeforces.net/contest/2033/problem/D) - The solution to this problem got hacked. - Today I found out that my approach to this problem was correct but instead of using long long, I used int. Once I corrected it, the solution passed. - :(
