Time: 11:29pm IST
- Solved A
- Solved B
- Solved C
- Couldn't think of D
-- Up-solve :
Solved A in 8 minutes. I think I could've solved it faster but my computer froze up. Nevertheless I should aim for sub 5 minute timings on A. I wonder do the people who solve it in 1-2 minutes even test their solutions? E.g. tourist who solved in 0:00 minutes. I used the coding format from 619's D problem and coded really nice solution. Happy to see up-solving paying off! O(n)
Really had fun time solving B. I imagined the circles intersecting as the rabbit's hops and felt pretty awesome after submitting the solution. I think elegant mathematics plus coding solutions is the best kind of computer science. Especially when you can visualize the concept in a 2D plane. I submitted a wrong answer which I knew in the back of my head was the case when he can hop in a single step to destination, guess I should think of all testcases before submitting answer. O(1)
First realize that solution will have either 1 letter hidden string or 2 letter. More than that isn't possible. Got this idea using some examples and mathematically too. I solved this then by storing results in 2D table. the table contained frequency of letters till that point. Then simple addition over this 26*n table for O(n) complexity gives answer. Really intuitive solution. See attached photo! photo
I had no idea how to work with D. I need to brush up on graph theory skills. Will watch William Fiset's Graph theory tutorials soon, then will try to solve as many questions as I can. Search for more resources.
What I Learnt
- Binary Search+ segment trees was a possible solution for D. How I don't know but the fact that they can be used is amazing.
- Calmly solving question with mathematical proof pays off.
- Up-solving previous contest was reason I could perform well this time. Need to keep this streak.
--- New Things to learn:
- I don't understand what is meant by Suffix Maximum array in D's editorial. Need to see some solutions.
- Using emplace_back() function
- Solving BFS questions to find shortest Distance from node to node.
- Djikstra's implementation I need to try out.
---- Pending :
- Read and try D
----Song of the contest
Thunderstruck by AC/DC :)
although the way you are treating the contest is a proper one, you should consider that publicly announcing your efforts is not always a good idea. why won't you write a blog about strategies to perform well in contests (after some research ofc) and how to upsolve them in a good way? :)
You don't have to post this on every blog he will send!
These blogs are very helpful for others to learn from. Please keep it up!
you can watch mifafaOwO's screencast to understand D's solution
suffix maximum is just suffix_max[i] = maximum of subarray [i, n]
then try to solve very similar problem 1016F - Road Projects
link for the stream pls!!(in english)
74017