I began to learn about CP during the last quarter of my first year at college through the CP community at our university. I created an account on Codeforces and attempted to solve random problems, often aiming for higher rating problems to prove to myself that I was skilled.
I wasn't following any strategy, and there was no one to guide me. I simply pick random problems with ratings higher than my actual skill level and try to solve them even if it takes me days to do it.

I managed to reach a Specialist with no knowledge. and after gaining some random knowledge in various topics, I stopped training and CP for almost a year, barely solving problems when I was bored. Now, I realized all my mistakes and understand that I wasn't actually training; I was simply wasting my time.

The issue I'm facing now is that I'm in my third year at college, and in my country "Egypt", passing a job interview requires more than just problem solving you also need to know about the technology stack relevant to the position. Additionally, I have to complete my graduation project, which involves studying some AI. While I know that FAANG and similar companies do PS only interview, I know that it's very difficult to land a job there, even with qualifications. The possibility of reaching the interview stage is around 1%, so I have ~1 year to make all of this.
(getting better at CP to reach ICPC learn some technology stack like backend development and study AI for graduation project)

So, let me ask you
have you regretted quitting CP?
Is it worth staying another year in college to reach ICPC?
Would I miss a lot if I quit now?
Since I've already walked on this path, it's hard to leave because I haven't achieved anything.

I'm 20 years old am I too old to achieve success in CP?
I have been diagnosed with ADHD would that affect the process?

Feel free to downvote this Idc.

Introduction:

Hello codeforces, In this blog, we will explore a technique for efficiently handling insertions and deletions in arrays using partitioning and deques. I cannot be certain if this idea has been previously explored or not, but I have conducted extensive research and consulted with friends to determine if a similar concept exists. If you have come across this idea before, I kindly request that you share the relevant link and acknowledge the original author's novelty in developing it And if no similar idea exists, then it seems like I've stumbled upon my very own data structure creation LOL. I have developed a method that leverages partitioning and deques to optimize array operations. I invite you to read about this efficient data structure and welcome your feedback and insights.

Understanding Partitioning and Deques:

Before delving into the technique, let's briefly understand the key concepts involved:

1.1 Partitioning

Partitioning involves dividing an array into equal-sized parts. In our approach, each partition contains sqrt(n) elements, where n represents the total number of elements in the array. The final partition may have fewer elements if the array size is not a perfect square. This partitioning ensures a balanced distribution of elements.

1.2 Deques (Double-Ended Queues):

Deques are data structures that allow insertion and deletion at both ends in constant time. They provide efficient access to elements at the front and back, making them ideal for our purpose.

Efficient Deletion: Let's explore how we can efficiently delete an element at a specific index, k, using the partitioning and deque technique:

2.1 Identifying the Corresponding Part:

we divide k by sqrt(n) to determine the index of the deque that contains the desired position.

2.2 Removing the Element:

Within the identified deque, we can delete the element at index k % sqrt(n) efficiently, taking O(sqrt(n))

2.3 Adjusting the Deques:

After the deletion, we need to maintain the equal-sized partitions. We sequentially shift elements from the front of the following deques to the previous ones, starting from the deque following the one we deleted from. This shifting operation takes O(1) time for each deque with overall O(sqrt(n)) (number of deques).

Efficient Insertion: Now, let's explore how we can efficiently insert an element at a specific index, k, using the partitioning and deque technique:

3.1 Identifying the Corresponding Part:

Similar to deletion, we divide k by sqrt(n) to determine the index of the deque that contains the desired position.

3.2 Inserting the Element:

Within the identified deque, we can efficiently insert the element at index k % sqrt(n), taking (O(sqrt(n))).

3.3 Handling Full Deques:

After the insertion, we need to maintain equal-sized partitions. We sequentially shift elements from the back of the current deque to the front of the following ones, starting from the deque we inserted at. This shifting operation takes O(1) time for each deque with overall O(sqrt(n)) (number of deques).

Time Complexity Analysis:

The partitioning and deque technique offers significant improvements in time complexity compared to traditional methods:

Deletion: O(sqrt(n))

Insertion: O(sqrt(n))

Access: O(1)

Examples:

Let's consider an array of size 25. We divide it into equal-sized parts, each containing 5 elements. The partitioning would look as follows:

• Part 1: Elements at indices 0 to 4
• Part 2: Elements at indices 5 to 9
• Part 3: Elements at indices 10 to 14
• Part 4: Elements at indices 15 to 19
• Part 5: Elements at indices 20 to 24

Scenario 1: Deleting an Element at Index 7

Identify that index 7 belongs to Part 2.

Remove the element from Part 2, taking O(sqrt(n)) time.

Adjust the deques by shifting the front from Part 3 to the back of Part 2, Part 4 to Part 3, and Part 5 to Part 4. This shifting operation takes O(sqrt(n)).

Scenario 2: Inserting an Element at Index 13

Identify that index 13 belongs to Part 3.

Insert the element into Part 3, taking O(sqrt(n)) time.

If Part 3 is already full, shift back from Part 3 to Part 4, Part 4 to Part . This shifting operation takes O(sqrt(n)).

Conclusion:

By leveraging partitioning and deques, we can achieve efficient insertion and deletion operations in arrays. This technique reduces the time complexity from O(n) to O(sqrt(n)), resulting in significant performance improvements.

I hope this blog has provided you with valuable insights into the efficient technique of using partitioning and deques for array operations. Feel free to reach out to me with any questions, suggestions, or ideas via direct message (DM) or the comments section.

you can find the implementation on GitHub

Note: you don't have to use all this code cause it may be a bit long just because this approach was to make the full Structure so feel free to customize it.

thanks to AliRagab313, _Mahmoud_Ayman, _heisenberg, Queen.., Moatazoleq for their valuable contributions through testing, suggestions, and consultation. Their efforts have been truly appreciated.

I'm facing a naming dilemma for this structure, and I would love to hear your suggestions in the comments section. Some ideas that have been floating around include "mesh map" in the Egyptian common language, humorously meaning "not map" xD, or "SRT" (Sherif's Root Tree) — a playful choice inspired by my name, although it may look Narcissism lol.

Thank you for reading the blog ^^.