Competitive Programming Progress

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.

1. 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.

2. 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.

3. 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.

1. Chocolate Day This problem appears a little complicated, but with extensive experience with Prefix Sum Arrays, I was able to solve it by separating it into small sub tasks and solving each one individually (a very important problem-solving technique!). The three tasks were: handling the fill operations, completing prefix sum array twice to get the value of the actual array then the prefix sum array of the actual array, and finding the largest amount of cup combinations possible. I had to solve the problem in O(N) time using a two pointer array searching for the last task. After adding a buffered reader input system, I ACed!

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.