Competitive Programming

Competitive Programming Logs

I used to have these logs in the GitHub, now moving them over to Obsidian.

TODO: Do 912div2 https://codeforces.com/contest/1903

Practice with this: https://themecp.vercel.app/guide

I think I should have a more systematic thing. Use a table?

Look into your process of thinking.

Hard problems that are easy to understand:

Easy problems that are super hard for me. Should reattempt to reassess if my thinking process is improved:

  • 1979B (div2), 1000 ratedā€¦
  • 2024C 1300 rated, counting number of inversions
  • 1987C
  • https://codeforces.com/contest/1950/problem/D div4 question FFS
    • The reason I fumbled here is because I didnā€™t really know a fast way to generate all binary numbers. Thereā€™s the
  • 2025C 1300, could have been 2 pointers
  • 2033C 1400, a permutations problem that wasnā€™t obvious to me
    • Actually had something pretty close to optimal solution, however the order in which I did it was wrong
    • Have more intuition on the ordering! But I donā€™t understand how this is different
for (int l = n / 2 - 1; l >= 0; l--) {
    int r = n - 1 - l;
    if ((a[l] == a[l + 1] || a[r] == a[r - 1])) {
        swap(a[l], a[r]);
    }
}

vs

for (int l = 0; l < n/2; l++) {
    int r = n - 1 - l;
    if ((a[l] == a[l + 1] || a[r] == a[r - 1])) {
        swap(a[l], a[r]);
    }
}
  • Like that doesnā€™t produce the correct answer.

This is because, because your comparisons are based on a[l+1] and a[r-1]. However, if those values donā€™t stay fixed (Which it wonā€™t if you go for l from 0 to n/2 -1), then your solution cannot produce a correct answer. Whereas fro n/2, your checks for l+1, those values are final, since that is the ordering of your l.

Weaknesses:

Need to practice more Tree questions.

Things that work for me

  • Write down the thinking process in comments since you hate pen and paper, helps step through the problem
    • USE your iPad, actually really helps

For hard problems, itā€™s oftentimes

I actually get stuck on so many problem Cs, itā€™s so sad. If I can solve problem Cs, I will unlock a lot of potential.

You gotta finish these:

ProblemDifficultyStatusAnalysisMetacognitionTakeaways
2040D?Could understand the problem, but actually had no idea about the working solution.
2040C?TODOCouldnā€™t do this at the contest, but seems like 2k+ people were able to do it.
2050EGot a little confused on the indexing.
2050FTODOI knew pretty fast that this was a segment tree problem. However, I never actually did many segment tree problems
2021B1200DONEWTF, Iā€™m so stupid. Couldnā€™t solve it.

Had the right idea with a priority queue, but even that TLEd because you donā€™t have a guarantee of O(n). The map as well didnā€™t well
Use the frequency array. Never underestimate frequency arrays.
2047D
2047CDONEReally wasnā€™t hard. But I semi-brainfarted in terms of greedy intuition. I was like, why is there n = 5000, I have an O(n) solution, this canā€™t be rightā€¦Had the intuition super fast. But then, I couldnā€™t figure out why greedily taking the column with the largest sum doesnā€™t work.You cannot assume the following: If a + b > c + d, then a+b+ max(c,d) > c + d + max(a,b). This is NOT TRUE. Consider

a = 19, b =2, c = 10, d = 10

31 > 39 is NOT TRUE.
2042C?Came up with idea to binary search k. But thereā€™s a smarter solution of sorting the suffixes!!I thought binary search, and then you always greedily choose the first few intervals. But that didnā€™t work.Thereā€™s a similar problem 1903C.
1948D1700TO FINISHEasily saw the O(n^3) solution, but could not figure out a faster solution in O(n^2). Cost me 2 hours of sleep.Thereā€™s a way to do it in O(n^2).
1968E1600DONEHonestly should have been able to do this one without looking at editorial. The key idea of splitting even numbers and odd numbers went over my head. I should know this better.Was good drawing it and trying to visualize a solution. Intuition was good, drawing the diagonal. And then just switching the 2 numbers.
1968F1800TO FINISHItā€™s an XOR problem.
1925C1500DONEEasy! yay I donā€™t think i was supposed to get it that easily?? I literally got it in 1 minute
1925D1900Itā€™s a probability question, which I should have gotten faster!! I can do this definitely.
1934B1200DONEFor some reason, I fumbled this. Maybe it was because I did it pretty late at night.Essentially, should have reasoned more about the coins, and checked the cases. I missed the idea that each coin except for 15 can only be used at most 1-2 times.Think harder.
1934C1700DONEPretty happy that I got the initial idea correctly with those 4 queries. I did struggle for the cases of computing the top right, I was thinking of binary searching that number, but you can just derive it analytically through math.

Be faster next time!!
1969C1700Damn, harder problem than I thought it was. I thought a greedy approach would work.
2025C1300Like i got a solution, but there were simpler ideas:
1. Binary searching for first value where thereā€™s a ā€œjumpā€
2. Using 2 pointers where you move index i and j
Get more comfortable with 2 pointer implementations. practice again
1966A800DONEFor some reason, really struggled with the logic here. I ended up using a priority queue. However, I think it can be brute forced because the input is so small.
1966C1400Found this problem to be quite hard, even though it was 1400 rated.
1934C1700TODO
2026C1500Made a silly mistake because a value of 0 with type size_t -1 becomes a super large number, and then accessing an array results in an incorrect value.
ProblemDifficultyStatusMetacognitionTakeawaysAnalysis
1990C1500DONEReally panicked and was afraid of not being able to come up with a solution. Take the time to write out the problem, and the steps to solve it.
Try to figure out patterns and insights, in this case after an iteration or two, the numbers stabilize to always be increasing, and you notice that numbers donā€™t disappear anymore.
I didnā€™t know how to approach the problem. Made the most STUPID mistake with vectors, and not noticing that I should not push_back when I already initialized them with a given sizeā€¦ That was just a huge brain fart. My assumptions are wrong, was put in shambles. In those scenarios, look at every assumption you make and question if it is correct. push_back assumes that the vector is initially empty, but I forgot the factor that i initialized it with vector<int> v(n) (size n already). Mistake happened because most of the time, I just initialize it without anything.
1990D1800DONEThinking was good, just a little slowSolution is actually not that hard, itā€™s just making sure that the greedy solution is optimal.Have trouble coming up with the insight. Made the observation that in most cases, just wipe by rows. I have feeling DP works, but I didnā€™t have ideas to the solution. Actually, let me think it through more. I got the insight without looking at editorial, which shows that I am capable of solving1800 problems
1988C1300DONEKnew very early on that it was a bitmask problem. Double checked my correctness in my mind, which was great.I forgot to do 1ll << shift instead of 1 << shift, causing negative values to creep upā€¦Canā€™t believe Iā€™m struggling on a 1300 problem.
1988D2000TODOWas intimidated because I saw it as a tree question. Didnā€™t know how to solve it with current toolset, but actually, I did. I just needed to confidenceDonā€™t know how to prove that my solution is correct, i.e. greedy is good (maybe it isnā€™t?)
1994C1600DONEHad to read the solution to understand. Itā€™s actually not that hard, but itā€™s undersatnding and visualizing.Need to figure out the subproblem correctly through DP.My implementation was also a bit wrong. Need to read the nuance, because itā€™s <= and not <. So be aware when it resets.
1995B21700DONEHad no ideas for the life of me. Read up again on solution, and have a vague idea
1993BTook me much longer, had 2 failed submissions. Had an idea with the greedy solution of just replacing with the maximum sum. However, that was not optimal. Should have convinced myself that it was optimal first. See that we have at most n +1 replacements, where n is the number of even numbers.This is just practice, and maybe a bit of bad luck.
1993CI solved this but didnā€™t think my solution was optimal.Could not reason about the number of periods. Yea, somewhere from to , for some reason I did to and got the right answerā€¦
1995C1800Idea was partially there, but I couldnā€™t see that you can square in constant time, and that relative powers could be used. However, the idea of using negatives was a nuance that I couldnā€™t catch. Also, ā€œresettingā€ to 0
1983B1200DONEHonestly struggled with this one even though it was a 1200. I only thought of 1 pattern for the solution, which was to move outside in to find a solution. I didnā€™t think of just using the top left corner of the rectangle. I was also ā€œtrickedā€ because the grid can be any size, as the question thought. Next time, need to think through more possibilities.Fairly trivial question, just need to make the observation.
1983C1400DONEvery not bad, had the idea fairly quickly due to it being interval question, maybe also I saw the question typeā€¦ but I think implementation still needs to be faster, I spend too much time thinking and implementing, and not enough time convincing myself itā€™s a correct solution
1992D1700Wasnā€™t actually that hard, though my idea might not pass. They essentially find the bounds of the number, I could not reason about that. Not actually that complicated, just needed to be able tot hink it through
1989BTook way too long for implementation, idea came pretty quickly. Could have gone for a linear time solution. Ideas are all there, try all the numbers, that ends up being the best one.I just binary search it, and it seems like I canā€™t exactly binary search it well. Because the increasing decreasing order doesnā€™t work that well. Also, iterating from -neg to n
1979B1000XOR question. could not come up with solution, seems to boil down to algebra. Thereā€™s some idea that my brain canā€™t come up with.
1979D1600Idea was off, didnā€™t make the right observation of it being 1 of 3 choices, I also misread the question.
1999BFumbled this question even though it was so easy. I drew out the game tree in my head, but it wasnā€™t so obvious that the two scenarios are basically the same.Finally figured out by writing out the 4 scenarios. I w
1999CAlso easiest question of my life that I fumbled. I had a if for the last case, because the case is handled differently, when actually, itā€™s an extra check that I need to do. Itā€™s just a habit that I had, which caused me to overlook it.
1999D1500Make the observation about the potential subsequences. How those would look like.
1981B1300DONE
ideas were there, just had to push a little to get there.Came up with solution :)) Failed first attempt due to only checking the first 30 bits, instead of first 31 bitsā€¦ stupid mistake
1981C1800DONEIdea is also there, but pushing through to something working is hard. Also taking me too long.Spent like 1.5 hours. Ideas was there pretty quickly, but I could not figure it out.

Their solution encodes this as a binary tree. My idea was from a pretty simple observation about the shortest set of sequences to go from a to b.
1981D2400
1977B1100DONEfound it pretty hard to come up with the correct idea, even though the intuition was there. Ultimately got there with observation about 11 = -101
1977C1900NOT DONEAlso made observations, but correct idea is just not there for me.Read the solution and still donā€™t understand.
1987C1200DONEFAILED SO MANY TIMESā€¦ have the idea pretty fast, but implementation is wrong. Yea, I missed the greedy part.Didnā€™t realize I can just shave off a[i] and then take a max to a[i+1], the recurrence is quite simple, but you gotta make sure you get the idea corrrectly.
1987D1800NOT DONEReally not obvious to me why we canā€™t just greedily eat the smallest cake and end of story?This is the Alice and Bob question that I cannot figure out for the life of me. Need to use some kind of DP.Right because as the opponent, if i eat a cake that apears multiple times, then itā€™s a waste of energy. Need to eat the unique cakes first.
1986D1400DONEI always come up with the greedy solution and am convinced it works, without proving it. I need to prove it more.I actually had the correct idea. However, when my implementation doesnā€™t work, and I canā€™t figure out why, this is like debugging. And it seems that I really suck at debugging, or figuring out really quick the root issue. CP is really good practice for this.
- Figured it out, itā€™s because I treat 1 and 0s to be the same. But if itā€™s 0, the answer is actually 0, whereas if itā€™s 1, itā€™s a multiplication by 1. Very big difference.
2002C1200DONEIdea was there, good job steven. However, my stupid brain started using doubleā€™sā€¦ should have kept using long long.
1980C1300DONEThis was REALLY easy to me. Instantly got the idea.I get TLE if I use unordered map hereā€¦hash collisions Iā€™m guessing.
1980D1400DONEReally not hard, just have to brute force it. Thinking was correct.
1980E1600DONEIā€™m either cracked or this was a really easy problem.
1985E1200DONEReally struggling with this one for some reason, looks like the solution might be some sort of brute forcing? Yes, I figured it out, though a little slower than I thought.Just brute force the different options.
1985F1500DONEProblem is easy to understand, but couldnā€™t come up with a fast solution instantly.
1985G1600DONEThis isnā€™t that hard too, though it was a little harder to understand. I think I figured out the pattern, but I was slow, and I donā€™t know how to handle for 10^9 case.Okay, this is just hard because of the counting rules.
1996D1500DONEGot intimidated by this, but really itā€™s not that hard.
1984C1300-1700DONEAgain, easy problem to understand, but difficult to reason about a correct solution.
- The reason itā€™s hard to solve in my head is due to having difficulty reasoning about the fluctations in the numbers.
The harder problem was also not that bad, but reasoning about it proved a little difficult. Also, need to account for the case that all the numbers are positive, in which case its just 2^n. Else, you need to go over each time the number reaches the minimum sum, as you have the option of taking the absolute value.
1997D1500DONESolution is actually pretty simpleGot wrong answer due to large valuesā€¦itā€™s actually stupid. Needed to add a check for integer overflow
1996E1600DONERead the question, had only the idea of a prefix array, but could not see a way to do it in linear time. Binary search is at best O(n log n), but how would you even binary search that??
1982B1200DONEStruggling with this problem is actually disappointing, I donā€™t think Iā€™m taking the time to think.Think. And be careful with variables getting updated.
1879D1700DONE, BUT VERY HARDā€¦I found this to be a REALLY hard problem. The #1 observation I need to make is that in XOR, usually you do bit wise. However, I still donā€™t understand the solution doesnā€™t subtract 1 at the end.ooh the length of the subarray is correct, I donā€™t need to do 1, because itā€™s actually the length -1.
1976C1600VERY HARD without being shown solution

DONE
Found this to also be a little hard, I think problems are a lot easier if you can frame it in the correct way.

How could I have framed it again, not knowing the solution? Have the idea that at some point of the process, the recruiter has to choose incompetent. So things will change if we donā€™t hire someone, and only the first person who is hired incorrectly is changed. Him changing wonā€™t change the rest, since itā€™s just 1 good spot.
Had to see that weā€™re essentially left with forced to choose a candiate.Need to think about it in terms of how the score looks if
2000E1400DONEAm struggling to figure out how to do the summation correctly. Could not figure that idea out.Yes, this formula:
(min(š‘–,š‘›āˆ’š‘˜)āˆ’max(āˆ’1,š‘–āˆ’š‘˜))ā‹…(min(š‘—,š‘šāˆ’š‘˜)āˆ’max(āˆ’1,š‘—āˆ’š‘˜))
.
I need to get better at deriving that. Need to make the basic observation of (i - (i-k))(j - (j-k). However, we need to cap it, since left and right side. So then you take a min and a max. Actually a hard problem for me.
1974C1400DONEUsing the idea of a map of set, as opposed to tuples. And then going over the array and just updating the counts. Thatā€™s smart. I did not think about that. How could I have thought about the idea? I was actually very close. Just needed to subtract the count of the current one, and needed to work with tuple. And not use the n (n-1)/2 formula.
2001BHad the idea pretty quickly, which I was happy with, but I was not able to prove the correctness of the solution on the fly, so I got AC by luck. I guess the insight is that we can control how much carriage returns by swapping the order. However, I did not prove there was a sequence in which they exactly match.Good observation of seeing the numbers decrease.
2001C1500
DONEEssentially a binary search on trees through queries, should have figured it outā€¦
1973B1300DONESmall mistake in setting up the if-else statement.
1973C1700DONEDid this with a little help from the solution. The main observation here that I missed was the idea that we can even indices sum to <= n, and odd indices sum to >= n+1. For even indices, only use the numbers smaller to n/2. And then we use the greater numbers. We just need to be careful about where n is.
1956C1600DONE with helpDidnā€™t seem that hard, yet I got it wrong a few timesā€¦This is a problem where the solution is really easy, but proving that it is optimal is the hardest part. You need to use the pattern.
1957C1600DONE with helpThe most obvious thing is to just do DP. But I donā€™t know. I could exhaustively search. Should have made the observation in a 2x2, and realized if I used 2x for the diagonal, that already gives the wrong answer, and similarly for the other sides.Order doesnā€™t here, because you can always have it come up later. So just pick a row and a column. Iā€™m still not convinced. Itā€™s the DOUBLE COUNTING part that Iā€™m getting confused on. Yea, itā€™s because you still need to check the last row and column, which are still free. So you would essentially double count.The big thing that I missed here is to observe that order doesnā€™t matter. I came up with the semi correct formula, but it was wrong because I thought order mattered, in which case I counted extra cases.
1956D2000This problem, even reading the solution is a little hard.
2004D1600DONE with helpI missed the observation that only 1 intermediate city is possible.And to get the closest city, use a table that tells you the nearest node with that particular value. You only have 6 possible values
2004E2100Need to revisit this once I understand the Sprague-Grundy Theorem theorem
1946CHappy that I had the idea of binary searching early on the value. However, the thing I miss is checking whether is possible or notā€¦ I actually had the idea of doing DFS too, but I couldnā€™t prove in my head that the greedy way works.
2003D2I feel like I should have gotten that one. I got the idea pretty fast with formulating the problem as a graph.Needed a modified disjoint set union. I mean, rather should have used DP with a graph. How could I have had the foresight that disjoint Union set doesnā€™t work? When the formulation requires some weird tricks. There might be a better formulation for the problem. Just be able to see the problem better. I mean, you can reach 4. The size doesnā€™t model the relationship correctly.Wow, thereā€™s also nuance to the value being the MEX itself as the max that we need to initialize. Thereā€™s a lot of nuance to this question, hard to get right.
1838B1100DONEThis is the problem that caused me a massive elo drop at a contest.Damn I fumbled it again. I made the correct observations, but like 90%. I eliminated the possibility of considering the 3 cases. It was an idea for a split second. I was like, we only need to look at the 2 smallest values.
1944D2000DONELooking at how a string is not K-good by looking at the case that it is K-Good.
1935C1800DONEMy idea/intuition was to use a greedy approach, but it couldnā€™t work since there the remaining val has too many values to check.Optimal seems to be greedy.

The idea of iterating over the array, and greedily taking away the maximum value is something I need to remember.

Greedily taking away the max sum, using the data structure to store the actual values, itā€™s really smart.
1935D1800DONEALMOST had it. I didnā€™t know how to calculate the intersection of both sets.
1935E2300TODOSome bit things
1991C1300Wow, idea went completely over my head, going bit by bit. I should have made the observation that we are limited to 40 numbers, and thinking about reducing the range of possible numbers through a bitwise fashion. I was just thinking about numbers alone.I think I had a brief though about iterating over bits, but im so stupid. Didnā€™t necessarily need to think bitwise. Just take the maximum number, and divide by 2. Then, you divide the range by half. At most ~30 elements (log 10^9)
1954D1800RAELLY HARD. DP over the potential values. That idea didnā€™t come up to me.Should have made the observation about the sum of the balls not exceeding 5000. Also, realize that the distribution is always s/2.

But even so, it seems non trivial.
2008FThis was a relatively easy question using prefix sums. However, I did not know modulus for the life of me. Either should use a class, and learn Modular Multiplicative Inverse
1950D1100DoneThis is a Div4 D problem, should be easy yet I as not able.Do not underestimate brute-forcing. Be smarter understanding time complexity. 2^5 divisors.
1950E1500It went over my head that there are only so many divisors.
1950FCorrect idea but failed a few times in implementationā€¦

Actually my idea was partially wrong
I need to be able to prove that the tree is minimum height. I was not able to come up with a counter example.
2009Clearned about how to implement ceil fast.
2014DDONEI rejected the idea of a sliding window. I had good ideas, and itā€™s actually not hard, but I opted for just checking overlaps. Itā€™s stupid.Sliding window is still O(n), do not reject that idea.
2014EI could not see how a variant of Dijkstraā€™s could solve this..
2030CDONECouldā€™ve had more conviction in my idea. Didnā€™t follow up. The first observation about 1s being on the side was really good. Just had to see that contiguous ones work.Kind of cheated. My idea was halfway there
2022BDONEHoly shit Iā€™m stupid, I donā€™t know why Iā€™m not able to do this problem
2019BDONEReally struggled with the interval calculations. Integer overflow againā€¦ at this point Iā€™m just going to default to long long and not worry about these stupid problems.
2013CDONEBruh, I actually solved this pretty fast. I realized that the first character takes 1 guess, and then subsequent will take 2 guesses at most (to check that it is the last string). And then if both guesses are wrong, then you know itā€™s in the other direction. And then that only takes 1 guess.I was pretty happy that I found the answer pretty quick. It seems that I didnā€™t need to do this BFS approach. Actually, tutorial has this graph implementation, but I didnā€™t need that. Couldā€™ve just pushed back the edges, and then tried to create something: https://codeforces.com/contest/2027/standings/friends/true/participant/195276602
2013D
2027CIā€™m SO PISSED. I forgot that I should never use unordered_map or unordered_set for a codeforces problemā€¦why am I so stupid. I got the question right.
1955E1700Man, I got too intimidated. Solution really isnā€™t that hard, itā€™s just sliding window bruteforcing.
2032D1800DONEIt was similar ideas, but actually here, itā€™s doing a linear search as opposed to a binary search of components. Pretty fun to try out.
2024C1300DONEThis is a very easy problem that I didnā€™t manage to figure out?? Like I genuinely didnā€™t know what to doā€¦Very not obvious that the idea is to use the sum to compare. I need to prove this out.

problem - difficulty - status - metacognition - takeaways

Problem solving: Lots of intuition, the solution should come to you. You make observations that lead you to coming up with a correct solution.

Leetcode:

[1,0,1,0,1],
[1,1,1,1,1],
[0,0,0,0,0],
[1,1,1,1,1],
[1,0,1,0,1]

[0,0,0,0,0],
[1,1,1,1,1],
[0,1,0,1,0],
[0,1,0,1,0],
[1,0,0,0,1]]

2024-08-17

This is not the same as

ans = (ans + m[prefix[i]] * (n - i + 1ll)) % MOD;

Incorrect

ans += (m[prefix[i]] * (n - i + 1ll)) % MOD;
  • Ahh, because I need to take a MOD on ans afterwards too, iā€™m so stupid..

2024-08-09

Really werid compiler optimization going on

  • behavior causes modifcations to same memory addresses
        cout << endl;
        int m = median(n - 1);
        for (int i = m; i >= 0; i--) {
            if (mod1[i].second == 1) {
                mod1[i].first += k;
                cout << "? " << i << endl;
                break;
            }
        }
        for (int i = m; i >= 0; i++) {
            if (mod2[i].second == 1) {
                mod2[i].first += k;
                break;
            }
        }
  • 965div2 C.cpp

2024-02-27

Doing a codeforces contest again today.

This question is pretty easy, but I am not sure how to deal with the edge case?? https://codeforces.com/contest/1932/problem/C

  • Need to take a modulus, but when??

2024-02-26

Struggled with diameter of the tree offer.

2023-07-04

Bruh, why do I find this leetcode daily problem hard. Am I just bad at XOR problems?? 137.Ā Single Number II https://leetcode.com/problems/single-number-ii/

2023-06-15

Got the nvidia offer, but this is still super fun. 714.Ā Best Time to Buy and Sell Stock with Transaction Fee: https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/submissions/

  • Damn I really struggled with this problem today.

2023-06-06

Wellā€¦ seems like the interview is spread over 2 days now. More stress. But this should be fun.

https://leetcode.com/problems/letter-combinations-of-a-phone-number/

  • Really make sure to pay attention to detail!!

2023-06-05

Speedrun this list https://leetcode.com/explore/featured/card/top-interview-questions-easy/ (brush up on your data structures and algorithms, < 1 hour?)

  • I think that the math questions are super easy

I have a lot of trouble with sorting, therefore I am going to focus a lot on the sorting stuff.

2023-06-04

I completely bombed the Codeforces contest today: https://codeforces.com/contest/1838/standings/participant/156529852#p156529852

  • I feel like it could be due to a lack of sleep, or I got unlucky with the questions, because they just didnā€™t click with me

bro I did so many practice interviews on Pramp, so many of these people are SOOO slow at getting the solution. At this point, itā€™s better to just practice

Goal is to

Bruh, even with a question as simple as removing duplicates, I am struggling. This is honestly really pathetic.