This summer, I spent 75 hours coding solutions to ~150 competitive programming problems! In my Competitive Programming Corner, I will share some insights into my journey and provide my solutions in the Nook, which is a fun code playground! I believe that anyone can become a competitive programmer and that the best way to learn is to program yourself and to review other people's solutions. Here, I showcase a FREE and opensource collection of my solutions to a plethora of problems in an interactive manner. Be INSPIRED, be MOTIVATED, and find your GUIDING SPARK! I hope I encouraged you to try at least one competitive programming problem!
No followers yet
Once you ship this you can't edit the description of the project, but you'll be able to add more devlogs and re-ship it as you add new features!
Finally, I added the Journey page, Resource page, and worked on the code playground. I spent a lot of time trying to make the editor in the code playground realistic and practical! I hope you like it :)
I attached an image of the updated Nook and you can see my full webpage by clicking the demo button on my SoM project page.
Hey!
Here's a list of what I completed:
- Explained
- problem structure with examples
- hints
- connection to math
- essential factors for success
- added warning and important notes styling
- fixed bug with offscreen arrows
- added the Nook, where my solutions will be displayed
- added code editor for the Nook (will elevate later)
Hey! Just completely elevated and transformed the website!
I added a new navigation feature using arrows to change between sections (using javascript to program the responsiveness, css to position the arrows, and html for the raw content), added more styling for text variations (the yellow text expands when hovered upon), and filled in some of the information for my site.
Here's an image!
Just started my website using basic html and css. I tried out a new font package! Here's an image:
Hey!
I completed three more questions, two of which were considerably difficult and required some extensive thinking to solve. They were both USACO problems, so they were also implementation heavy.
Here's the problem that was the most time-consuming:
Bucket Brigade (USACO):
Although the concept seems pretty simple at first, the rock placement greatly complicated the problem logic as I had to keep track of the x,y coordinates of the each of the lake, burning house, and rock. Eventually, I came up with a strategy after testing out many cases of the problem by hand. However, with the complex logic, I messed up the inequality signs and logical operators at times. In addition, I undermined the case of equal y coordinates between the lake and burning house. In the end, I was resilient and fixed all of these mistakes and reached an accepted solution!
Attached is proof of my successful submission to Bucket Brigade.
Hey, this short work session, I completed 3 questions, two of which required very lengthy and case subjective solutions.
The most significant question out of these 3 is
CCC '01 S1 - Keeping Score
Given the long string of input, I concluded a strategy of using four while loops for each of the suits and many variables and for loops to implement the question. However, I had to pay attention to every detail and every name of the variables as a single tiny typo could cost me an accepted solution.
Attached is proof of my accepted submission for CCC '01 S1 - Keeping Score.
Hi! This work session, I completed 4 problems of relatively low difficulty levels. They tested my knowledge of for loops, while loops, if statements, and variable manipulation with problems that required efficiency and accuracy.
Two significant problems:
1. COCI '19 Contest 3 #1 Preokret
This problem had three requirements for the answer; two of which were very simple to calculate; and the third of which required two variables and consistent manipulations to each. I had to track the team that is experiencing a turnover and also the length of the turnover. At the beginning, I didn’t check if a team experiencing repetitive goals was originally less than the other team before the “turnover,” so I had a wrong answer. However, after more thinking and outlining my strategy on paper, I greatly simplified the for loops and was able to reach an accepted solution! This shows just how much a little bit of planning and rest can contribute to solving a problem!
One of my first thoughts after reading this problem was that the Lost Cow Problem appeared very intriguing, so I continued to research it and discovered the insightful but complex mathematical proofs. I was able to learn a lot just because of this problem statement!
Attached is proof of my accepted solutions for the above 2 problems.
Hey! Today I completed a really quick session to get in some coding time.
I am working on COCI '19 Contest 3 #1 Preokret, which requires some difficult logic.
Attached is my output from my program.
This was a really short work session, but I managed to finish 5 problems!
The problem that really resonated with me was Adding Reversed Numbers.
I managed to find a simple way that did not use that much memory to reverse a number using mathematical concepts; modulo, division; and I also took advantage of the Java integer property that integers stay integers in all mathematical operations (they use floor in division). I will definitely put this method to use in the future.
Proof of my accepted submission to Adding Reversed Numbers is attached.
It's been quite a while since I last devlogged due to a heavy workload and also difficulty accessing my devlogs. This time, I have been practicing more Mathematically inclined questions to put to use my knowledge of Algebra, Geometry, Combinatorics, and Number Theory. However, most of these questions do not require that much thinking as I am experienced in competitive math and did not encounter much difficulty. I have completed a total of 42 problems that were all 5-7 pointers.
For more in-depth analysis of my solutions, you can visit my dmoj user page to view my submissions (also when I submitted and my accuracy level) : https://dmoj.ca/user/Sophia3145678
Currently, I have used vJudge to access a wider range of problems in a single database and for this reason, it remains useful to me; however, it often encounters many DMOJ login failures, so I wouldn't exactly recommend it.
Now a little bit on a couple of the problems I completed:
CCC '02 S1 - The Students' Council Breakfast:
Although this may seem like a difficult problem to some and the time limit may appear threatening, this problem is easily solved with a simple, clear, and accurate brute force solution. This problem taught me to implement solutions that you can easily explain to someone as they are clear and not only easy for you to program but also easy for you to debug.
CCC '15 J4 - Wait Time:
I have just successfully debugged my solution and it just ACed! This problem was one of the only non math related problems in this set, and it required 3 maps!!! for me. Originally, I didn't expect this problem to be as complicated as it turned out to be, so I didn't write out my plan completely and experienced confusion afterwards. Next time, especially with these types of problems, I will try to make a detailed plan before trying my hand at the problem.
Attached is proof of my accepted solution for these two problems.
Hi! I finished 14 problems in these 6 and a half hours and managed to try out the CPH Judge & Browser extension.
This time the problems I encountered were mostly 3 or 5 pointers but still managed to program an accepted solution for several 7 and 10 pointers. The topic for these problems was Data Structures (basic graph theory, binary search), Primes (Sieve of Eratosthenes, Brute Forcing up to sqrt of a number), and Recursion (calling a function inside of itself, checking for base case). Here are 5 problems from this work session and some insights I would like to share!
At first glance, one might solve the problem using an array and search every column/row for mysterious beings, however I solved this problem very easily with sets. I made two sets for both the rows/columns and added the row/column number if there is a mysterious being in that row/column. This allowed me to easily check if Saki is in the same row/column as mysterious being(s) and was time efficient! This problem truly reveals the power of sets and makes use of their O(1) searching time complexity.
I solved this problem using a complex strategy that combined binary search and prefix sum array. I used the same strategy from last week of testing if integer a is in the subsequence from index x-y by seeing if Collections.binarySearch(y)-Collections.binarySearch(x) is larger than 0 (I had to handle negative indexes if x/y doesn't appear in the list of occurences of a). However, after looking at other user's submissions, I discovered that a binary tree solution also works! I will learn more about binary trees and solve some of those problems in the near future.
This question was an interactive problem and required the user to discover the hidden trick in order to solve it (all of these interactive ones do). Using a crucial problem solving strategy, I tried to solve the problem using smaller cases of N and realized the strategy of discovering the first 3 numbers then finding the rest by comoparing them with the first number. However, this strategy uses too many requests of interaction, so I was forced to use a set to store all the values form 1 to N, then find the last number in the sequqence as the last one remaining after I remove every number from the set once it appears in my calculations.
In my first attempt at this problem, I didn`t realize that ranks could be repeated, as in if you have a contest and 3 people score 10/10 and 2 other people score 9/10, then the rank of the first three people is all 1, and the rank of the next 2 people is not 4, but 2. However, after implementing a list to store people with the same rank, I was able to reach an accepted solution!
Although I used a mostly brute force method myself, I discovered a new mathematical method and recusive algorithm that can solve the question much faster and with less code. I will be implementing a new solution very soon! This question required some basic knowledge of graph theory and implementation logic sense.
Overall, the binary search, primes, and recursion questions for this work session did not have an extremely high level of difficulty but it was interesting to program my solutions but also look at other users's successful code!
Hey! I just finished 7 (and a half) problems on DMOJ which mostly tested my knowledge of Binary Search. As I'm approaching more difficult areas of programming that have questions with higher point values, I've spent more time debugging for each question and also learning by looking at other people's faster solutions.
Here are 3 significant problems that I solved!
1. ECOO '20 P2 - Online Shopping
This question was mostly a data structures problem that I solved using a custom comparator and sorting. It was purely implementation and taught me the importance of noting down your solutions before coding them in order to have a well thought out and organized plan that will be easy to program.
GFSSOC '15 Fall J5 - Nightmare-a-thon
Although I didn't solve this problem the way that the question writer(s) meant for it to be solved in O(N) time, I used a binary search algorithm that finds how many episodes of a certain rating are in between two indexes (start and end of skipped episodes) then calculates how many episodes with that rating are left based on the total list size. However, I decided to learn about other people's faster strategies and discovered that keeping an array that monitors the largest episode rating to the left and to the right of each episode is the fastest solution and also was easy to implement.
BSSPC '21 S2 - Hacker Soup
This problem was extremely meticulous because of the weird array values that the question used as I often got confused on which value was x/y because the input placed the y first before the x. I had to write out a lot of grids to test out my code and originallly made an oversight when I didn't implement a program that correctly solves the problem if the rotating subgrid doesn't have the same x/y coordinates for each of the top left/bottom right grid boxes. After becoming completely confused in my first attempt at the problem, I eventually succeeded after taking a break and debugging every single rotation in a 3x3 grid to ensure all the outputs were accurate.
Now the half problem that I am in the process of solving:
4. BSSPC '21 S3 - James's Egirl Discord Status
I truly haven't seen a similar problem to Jame's Egirl Discord Status before, so I had a lot of difficulty deriving a solution for this question. However, upon further study, I discovered that it requires a Dynamic Programming approach instead of binary search/two pointer search to find the maximum subarray sum. I am currently learning more about dynamic programming and will hopefully be able to reach an Accepted solution very soon! I'll make an update about this question in my next devlog.
I attached proof of my accepted submissions for Hacker Soup and Nightmare-A-thon!
This work session, I completed 11 problems on DMOJ and USACO combined and I am still in the process of finishing two more USACO questions. Again I will provide insight into my problem-solving journey for 5 significant problems.
[USACO] Sleepy Cow Herding
To complete this problem, I test-solved countless test cases which I made up by myself and stimulated the solve such that it resembled my program. This was extremely beneficial as I was able to engineer a well-thought out solution easily, and in the end, the question didn't turn out to be as hard as I previously thought it would be; it only required a simple greedy solution.
Back To School '18: Letter Frequency
Although I originally strugged to come up with a memory and time efficient solution for this problem, I eventually combined a PSA solution with some data structures knowledge in order to form a satisfactory solution. My program was similar to a mass PSA for all the letters of the alphabet! This solution helped me develop my core implementation skills.
DMOPC '15 Contest 6 P3 - Harvest
This was a another PSA problem that stressed time efficiency. After using multiple PSA techniques I have mentioned previously in other devlogs (eg. double PSA), I used a O(N) double-pointer approach to finish my program.
Mock CCC '22 1 S2 - IU
After looking at the time requirement, I realized that 0.25s was only enough for one O(N) sweep of the String. After brainstorming possible shortcuts and greedy solutions, I settled with summing up the absolute differences of the position displacements across the 'I' characters. Although I didn't immediately AC, I changed an integer variable to long to avoid Integer Overflow and solved the problem. To further immerse myself in this problem, I checked the Best Accepted Java Solutions for this problem and discovered that everyone used the same method, yet their implementation varied from time to time.
The Cosmic Era P2 - Uneven Sand
Uneven Sand was a classic Binary Search problem. Having played this math game countless times in my early childhood, I immediately knew that Binary Search was the strategy that would allow me to easily search a large interval of integers for the answer. Bascially, my program tested the middle of the interval repeatedly and adjusted the interval`s largest and smallest values after receiving the result to narrow down the interval until the program guessed the integer correctly. Having already completed one other interactive problem, the syntax for flushing was not as unfamiliar!
As an overall summary, I implemented data structure, PSA, and binary search techniques to solve most these questions! I have attached proof of my accepted solutions for [USACO] Sleepy Cow Herding and DMOPC '15 Contest 6 P3 - Harvest.
Sorry for the late devlog; due to an internal error blocking me from accessing my project page and making a new devlog, I was unable to create one earlier for my previous work session and had to combine two of my work sessions in this devlog.
As I completed a lot of problems (12), I will quickly summarize some of the important ones, and you can assume that I completed the others during a short period of time and without too much difficulty. The next 3 problems required mostly general implementation and also some custom comparators.
Booster Cushions: This was a really annoying problem and I was stuck on it for at least an hour and a half as I implemented my solution in the wrong way with faults regarding x,y swaps for my 2D array but managed to solve the problem with a little tweak at the end.
Mr. N’s Presents (RESOLVED! from previous devlog)
This Maps problem’s solution required a custom comparator and custom class to store the values. To keep my solution inside the time limit, I also had to create multiple maps, relating indexes to the values, to prevent lengthy sorting and a large time complexity.
Box and Whiskers
Although this problem seemed quite straightforward, parity cost me a lot of WAs and to make my solution cleaner, I created a central method for calculating the middle of any array and was able to reach an accepted solution.
The next problem relates to PSA (prefix sum array) and DA (difference array), two very powerful time-saving techniques in competitive programming. All the logic from the 6 PSA/DA problems I solved was required in RGPC '18 P3 - Chocolate Day, so I will just explain one problem for these two topics.
I have attached proof of my accepted submissions from Booster Cushions and Chocolate Day.
I finished 7 problems in these 3 hours and developed an in-depth understanding of custom comparators! Hour #1 & Hour #2: I quickly breezed through 6 problems & attempted another one! 1. (5 mins) CCC '18 J3 - Are we there yet?: This was a really easy problem as the question only required simple math and array manipulation. 2. (20 mins) CCC '15 J3 - Rövarspråket: a little index confusion, but this was relatively easy to program, other than having to deal with char ASCII values. 3. (15mins) WC '18 Finals J1 - Conditional Contracts: a quick, easy and straightforward problem after making the key decision to use a map! 4. (10 mins) COCI '16 Contest 4 #2 Kartomat: just a string problem with easy implementation. 5. (30 mins) ATTEMPTED New Year's '17 P1 - Mr. N and Presents: Tried solving with a quick List implementation, but TLEd and I am currently working towards a faster solution. 6. (15 mins) CCC '06 S1 - Maternity: I understood the genetic theory, so finding the solution didn’t take long, but implementing the code took a while. 7. (~25 mins) FSSOC '15 Fall S2 - Hearth: The multiple interfaces were confusing at times, and I also originally failed to implement the double lexicographically least order, but this question was pretty straightforward.
Hour #3: I completed CCC '07 S2 - Boxes, a question requiring a custom comparator. It took a little while ~30 mins to write the solution, as I kept getting errors regarding Collection.sort() and the comparable class. Next time, I will ensure to implement a custom comparator correctly. Afterwards, I debugged my solution and dealt with an integer overflow error when the output of the box volumes were incorrect due to the volume amounts exceeding limits.
Finally almost finished with Sets and Maps! The first 3 hours of this work session was dedicated to completing the ten pointer CCO '99 P2 - Common Words as I fixed multiple index and interface errors in my first very messy attempt at the problem; then had to reprogram my code as a result of misreading the question the first time (To be precise, a word w is the kth most common if exactly k-1 distinct words occur more frequently than w in the data set). In my second attempt at the problem, I used a custom comparator to sort the words by the number of occurrences. The remaining time, I worked on improving my previous solutions by testing out other users' accepted java submissions in VS Code and gathering information on areas of improvement (how to make my code faster, and more simple). Of course, my own solutions are still the ones presented in my project. My accepted solution for Common Words is attached.
Continued the unit with 10 more problems (I forgot to mention before, but by the end of every devlog, I usually finish around 10 problems (sometimes this can be as little as 8 or as much as 20) on DMOJ and USACO. The problem set is comprised of (0-2) 3 pointers, a majority of (5-7) 5 & 7 pointers, and (2-4) 10 pointers. This work session, I managed to finish the problems faster, as some of the concepts could be transferred between problems, reducing the amount of brainpower required. The problems that I solved required knowledge of Maps algorithms to complete, although I struggled with some whitespace errors on Spirals and overcounting in USACO 2021's ACOWDEMIA III. These problems took quite some time to debug. Here is one of my accepted solutions (Spirals).
I finished the Sets and Maps problems! In addition, I worked on finishing up some long awaited brain twisters which I have been stuck on for a while but was unable to commit to because of my goal to finish ALL of this week's Sets and Maps problems. These conundrums included https://dmoj.ca/problem/coci16c2p3 (DMOJ: Nizin) and https://usaco.org/index.php?page=viewproblem2&cpid=1108 (USACO: Comfortable Cows). I struggled on time complexity and index errors but was able to achieve AC after continuous debugging :) I haven't attached an Accepted USACO submission yet, so here it is:
I continued with more problems about sets and maps, and similar to before, I submitted my solutions to DMOJ and USACO. For me, these problems required more debugging and more efficient programming in order to develop a solution that would not time out yet also maintain accuracy. Here is one of my accepted solutions.
I completed some problems which were centered around Sets, Maps, and Binary Search (coded and debugged). My solutions were submitted to DMOJ and USACO. One of the problems that I spent the most time on is Appleby Contest '19 P4 - Rectangles, as I dealt with TLE due to my bad time complexity and other errors, but eventually developed an efficient solution. Evidence of my Accepted submission is attached, but one could find my DMOJ account and search for the problem there to find my full solution.