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↵
↵
I was able to "solve" 3 questions today(technically 2), mainly I am happy that I have finally started CP again and that I still have my basics and intermediate concepts under a firm grasp :)↵
## Revision questions:↵
None↵
↵
## Problem: New Rating↵
- Problem Link: [this](https://mirror.codeforces.com/contest/2029/problem/C)↵
- 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](https://mirror.codeforces.com/contest/2027/problem/C)↵
- 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://mirror.codeforces.com/contest/2033/problem/D)↵
- My solution to this problem got hacked, today I found out that all I had to do was replace int with long long.....↵
- :(
↵
↵
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↵
↵
I was able to "solve" 3 questions today(technically 2), mainly I am happy that I have finally started CP again and that I still have my basics and intermediate concepts under a firm grasp :)↵
## Revision questions:↵
None↵
↵
## Problem: New Rating↵
- Problem Link: [this](https://mirror.codeforces.com/contest/2029/problem/C)↵
- 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](https://mirror.codeforces.com/contest/2027/problem/C)↵
- 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://mirror.codeforces.com/contest/2033/problem/D)↵
- My solution to this problem got hacked, today I found out that all I had to do was replace int with long long.....↵
- :(
