Link back to all posts

August 1st-15th

After last post’s 6 contest ficaso, and recent personal entries taking 9 eternities to complete, I’m now trying to write this post faster than normal. This is so that I force myself not to ramble endlessly in these logs and in upcoming weeks my school schedule means I will not have as much time to write these posts. Hopefully I can still go into reasonable depth in my contest recaps, speaking of, there are three here:

Educational Round 133

Problems Solved: A, B, C

New Rating: 1883 (+20)

Performance: 1937

I have made several references to “SpeedForces” and this contest was a prime example of this. When Problem A has 14265 solves from Division 2 competitors and Problem B has 12524 solves, how many people would you think solved Problem C? The fact that I even gained 20 ELO from this contest despite only solving 3 problems says everything about the difficulty gap between C and D. Problems C and D had a similar 800ish number of solves. Speed is not usually a skill to focus on for competitive programming, but it ends up being crucial when 80% of the rankings are determined by who solved the first two problems faster.

All of the problems after B happened to be dynamic programming problems. For C the solution is based around noticing there are only two types of paths the robot can take:

1. A snaking path that prioritises finishing each column. From the robot’s start position this would be down, right, up, left moves repeated.

2. A looping path that prioritises finishing each row. From the robot’s start position this would be going right as far as possible, down, then left as far as possible.

Calculating the time to snake across any given number of rows using dp is relatively simple, but for the looping path, the time taken to loop across the last x columns has to be calculated. On top of that, 2. describes a clockwise looping pattern; the counterclockwise looping pattern also needs to be calculated. With all of this the time required for all given paths can be calculated since any possible robot path is either fully snaking, fully looping, or a combination of snaking the first x columns and looping the rest.

Then there is Problem D. In the contest I spent most of the remaining time trying to work out some sort of dp idea by writing out various patterns to no avail. With k = 1 I ended up with the sequence 1 1 2 2 3 4 5 6 7 10 12 15 and I still have no clue what the generating method is. Interestingly both C and D were 2000-rated problems. Even though both were around the same “difficulty”, I had widely varying success on them, which shows that I can solve Candidate Master level problems, just inconsistently. This contest also puts me in legitimate striking range of reaching 1900 ELO in the next contest, as my calculations find that I only require a similar performance of 1945 ELO to reach the goal.

Round 812

Problems Solved: A, B, C

New Rating: 1857 (-26)

Performance: 1775

This was a choke. I finished the first three problems in 22 minutes and all I needed was Problem D. I even figured the right method to eliminate two contenders with each guess so I had the right algorithm in place. Where my submission failed was in the implementation, which inexplicably was calling too many queries. I’m still in striking distance of Candidate Master, but now need a 2012 ELO performance for glory.

Round 813

Problems Solved: A, B, C

New Rating: 1834 (-22)

Performance: 1766

What happened here was a combination of the previous two contests. A similar strong start to Round 812 with Problems A through C solved in 25 minutes, the difficulty gap from C to D being nuts like Educational Round 133 due to the number of solves going from 8578 to 763, and then the contest finishing like Round 812 did with possibly a choke. Problem D was the question where I collapsed, and guess what? It’s another graph problem. I ended up having a TLE result here so I’m not entirely sure if my solution was too slow or wrong.

August 15th Update

Turns out for Problem D I really am unsure how to solve this. My in contest submissions likely TLEd because using a segment tree for minimum queries is O(log n), but with 1.5 seconds and n = 100000, this time limit is very iffy. Using a sparse table with O(1) minimum queries reduced the runtime but resulted in WA verdict. This could be because I am assuming paths like 1->2->5 will always be less expensive than 1->3->2->5, ie. the shortest path contains at most 2 edges. Having spent three hours on this problem and still not making any progress, only now I decide to look at the tutorial just to see how close I actually was in solving the problem. And it turns out that the easiest method to solve this is to binary search for the answer.

def solution(id: char):
	if id == "A" or id == "B": return simpleStuff()
	elif id == "E" or id == "F": return complexStuff()
	else: return "binary search the answer"

if solution(failedQuestion.id) == "binary search the answer":
	print("Pain.")

Pain. In my last 10 contests, I have dropped ELO 6 times. Half of those times were because of scuffed greedy solutions when binary searching for the answer would have been much simpler. Now I need a 2072 performance for glory, effectively meaning I need another breakout run.

It is true there are still 4.5 months left for me to reach Candidate Master this year. My original goal was Expert but was changed due to me reaching this back in April. The real issue is the upcoming school term. In earlier logs I mentioned I was seeking co-op, but these plans changed, mainly because there were many courses I could take this term that I have been waiting for months to get, and in all honesty, I did not feel ready for co-op. The Fall 2022 academic schedule, which will contain 6 courses, is my own decision. Combined with external projects I’m planning to post on my Github, I will not have the luxury of being able to attend every CodeForces contest scheduled. In September to December, there may be 10 contests that fit in my schedule if I’m lucky; any other contests will be the result of suboptimal circumstances. So the next three contests are vital, as they will be my best chances to attain Candidate Master this year.

August 16th-31st

These two weeks effectively act as Judgement Day. Routine competitive practice will be impossible after this with a course load that is just a “bit” difficult, so these next contests are crucial as to if I’ve attained Candidate Master, placed myself in very close striking range for the few contests I have left this year, or killed off any chance of reaching this goal with untimely collapses.

Round 814

Problems Solved: A, B, C, D1, D2, E

New Rating: 1981 (+147)

Performance: 2363

Holy hell I did it. The only “downside” from this contest was that I was not able to participate in Rounds 815 and 816 due to oversleeping for both of them, but screw that. I’ve reached Candidate Master in 8 months! Bring out the champagne!

So how exactly did this happen? Problems A and B were pretty easy, and I figured out the only trick in Problem C being that once the strongest player is in the match, they’ll win all of the remaining fights, so only the fights up to that one have to be calculated. Problem D was a harder problem where I made several greedy attempts that failed first, but unlike previous contests where I would make small tweaks each time hoping that I on the right idea, I made several attempts with significant changes each time, even trying a dp idea in one attempt (Submission History). The I found for solution for D can actually be summarised in one sentence:

Problem D solution

``` Minimum time = Array length - maximum number of subarrays that can be created out of array where xor of all the elements is 0 ```

The only difference between D1 and D2 is runtime constraints, D1 can allow O(n^2) while D2 needs at least O(n log n). My implementation runs in O(n) time, and in fairness, this extra constraint did not really affect the problem much, as the rating difference between the easy and hard versions was only 100 ELO.

The true breakout that led to an International Master level performance was in Problem E. In this case, the problem is solvable via greedy method, so all that is required to check is if the letter count matches the sum of the first x Fibonacci numbers, and then to assign each Fibonacci number from highest to lowest to the highest value remaining without repeating letters twice. I did not expect to solve this question in 15 minutes, and to be honest, it was easier for me compared to D, but it is my first ever E solve in a Division 2 contest. This question also happened to be only Problem B in Division 1 (usually it would be C), so that may explain how I somehow got this question so fast.

Each point on this graph represents a contest in the last 8 months, with the first 5 contests being excluded since my rating there was provisional. From being on the 1400 ELO borderline between Pupil and Specialist in February and March, to climbing and maintaining Expert in May and June, to now reaching Candidate Master is a nice climb. The journey however is still not over yet, as technically, I’m still a candidate. Being an actual “master” of competitive programming at 2100 ELO would be fun. I’m unsure if I can reach that by the end of this year with my upcoming school term limiting the quantity of contests I can partake in, but I sure as hell will try. Also, I’m working on two special posts to be up (eventually) reflecting my first year on CodeForces and what each rating in CodeForces means, 2022 edition.

August 28th update:

Well it turns out there’s another contest announced for this month. Might as well participate in that one. How did that turn out?

Educational Round 134

Problems Solved: A, B, C

New Rating: 1883 (-98)

Performance: 1562

Pain.

To put the above in a more optimistic viewpoint, the fact that a performance that would be considered decent for my rating back in February is now losing me nearly 100 ELO shows how much I’ve improved in the last 8 months. It still doesn’t excuse that in this contest, I was a mess. Problem D I figured out the solution. Oversimplified, for D you first find what bits can be 1 after the AND statement, and then try to build the answer from most to least significant bit. The issue is with sets like a = [1,0,0,3,3] , b = [2,3,2,1,0], the bits with value 1 and 2 can both be set to 1 after the AND statement, but not simultaneously. I compare this part with the following problem.

There are n keys and n doors. You are given m statements.
Each statement consists of x keys and x doors, x <= n.
The x keys given unlock the x doors, but you do not know
which key links to which door specifically.
Determine if all the statements can be true simultaneously.

If I could find a solution to the above problem, then I solve Problem D. There’s probably some really simple solution I’m missing here, and from the first half of the tutorial for this question, I have the same solution up to this point. Alas, being close on a problem does not give partial credit.

I’m not even mad over Problem D though. Had I avoided the 2 incorrect submissions I submitted for problems B and C each, I would have placed 1323rd with a penalty of 67, a performance of about 1690 ELO, and only losing about 70 ELO, keeping me in Candidate Master. Instead I proceed to be an absolute clown and completely forget about obvious test cases which unsurprisingly, results in additional penalties. Problem B was a glorified yes/no question where you needed to track which “walls” the laser touched to determine if a path existed. For my first submission, I said that a path did not exist only if the right and bottom walls were touched. In the below diagram, I initially thought only the left most scenario could lead to no paths.

Problem C is not much better. I got the first submission wrong, which sure, it happens. So why am I submitting again 5 minutes later with only a single line edit?? The program failed on pretest 2, so I should be relooking at the entire algorithm, not thinking there is some edge case breaking everything. A fail on pretest 2 either means something in your algorithm is wrong, or you made a blatantly idiotic error. The one line edit I made didn’t even affect the program at all so the second submission was just me handicapping myself with more unnecessary penalties. The third submission finally worked, which only took 26 minutes after the previous one. I have finished Problems A to C in that time before.

I guess you could say that at least I didn’t mind block C completely to the point of not solving it at all but for where I am right now, that is the bare minimum of what is expected. I’m not sure what the hell happened to my early question consistency in this contest. At least I still have one more chance on September 2nd to return to Candidate Master before school starts again.