3 questions "solved" in 2 hrs of practice. I am happy that I was able to continue my streak for at least one more day :)

Looking forward to practicing and improving tomorrow.

2033C - Sakurako's Field Trip

2008D - Sakurako's Hobby

1713C - Build Permutation

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
• 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
• My solution to this problem got hacked, today I found out that all I had to do was replace int with long long.....
• :(

I tried accessing clist.by but it gives a a 504 error. Is this the same for others? How long will the site be down for?

Problem Statement: this Is there a way to prove that if we are not able to connect the vertices to 1 in the greedy order that has been suggested, then there exists no other answer?

Thanks.

This video(copied with time stamp) presents an approach to solving problem 1665C and I understood the broad approach but I am not able to understand that if we have the sum of left over vertices after considering infection is greater than the number of injection operations remaining we directly say that x is not possible, but shouldn't we also consider the fact that even if we have less injections left, they would all still spread in parallel at any given time?

For example lets say that x = 3 and the sum of count values is 4. And this value comes from two sets comprising of two sibling nodes. Then it is possible to infect all of them in 3 seconds, because once we infect one of them the infection spreads to the sibling. So this is why I have this doubt, maybe I might have misunderstood something in which case I would really appreciate any help

This solution fails the second testcase and I don't understand why since the logic that I have used here seems to be fine. Any help would be appreciated.

Can someone tell me why this code is giving WA. I have tried coming up with counter testcases but it passes all of them. Thanks.

Hello, I wanted to know why the this submission was giving TLE. Thanks :)

The problem in question is Hamiltonian wall and I wrote a solution to this that works, but I suspect that it is the wrong solution. My solution is this. The reason I suspect that my solution is incorrect is because, if in the DFS function I change the order of the two loops, I get the wrong answer(when that should not be happening). I would really appreciate if anybody could point out what is wrong with DFS function.

Thanks, if you need any clarification regarding some of the terms in my template or regarding my approach, feel free to comment down below EDIT: I removed the lengthy template

This editorial problem E1, Erase and Extend, can someone please give a logical explanation as to how the optimal string is supposed to be a repetition of a prefix? The editorial takes a lot of leaps and the comments do not have any explanation. Thanks. (Ask me for further clarification if needed)

For problem this, the editorial suggests a naive way in which we break the chain and linearly kill all the monsters(then they present an optimization based on this), how do we know that this is the optimal way? Why can't I first kill monsters from one segment and then once the cascading effect stops, I jump to another monster which(say) has the highest b[i]/a[i] ratio? I need help in understanding this. Thanks in advance. (You can ask for further clarification from me if required)

The problem in question is problem and I have solved this using another approach, but I want to know why this two pointer approach does not work. Thanks

The following code despite being asymptotically fine, is still giving TLE on the 31st test case. I have tried everything, but I am not able to optimize this code further. I need inputs from more coders, any help would be appreciated. The problem link is this and my attempt is this (Incase the code is not readable, inform me I will format and edit in the code)