Way_Above_your_level_lol's blog

By Way_Above_your_level_lol, 4 years ago, In English

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 :)

Full text and comments »

By Way_Above_your_level_lol, 4 years ago, In English

Time: 5:45pm IST

  • Solved A
  • Couldn't solve B
  • Couldn't think of C

-- Up-solve :

  • Read the question wrong for A and started swapping on all elements, should read carefully and remember A is the easiest so the probability of there being a catch is less.
  • Started on right track of taking elements on the edge of -1 valleys. Should've added them in a vector more efficiently, instead I made complex vectors which was confusing. Then I did not think of a mathematical proof instead I made a intuitive guess which was wrong. Should try to get a mathematical proof for every question!
  • Couldn't even think of going the opposite route of finding subsets of zeros. This mindset of solving something else to get something else always comes with Subset questions, I got one such previously too. Keep this in mind.

What I Learnt

  • How to get max_element and min_element directly from arrays. ( cout<< *max_element( arr.begin() , arr.end()) )
  • I wonder what is the complexity? O(N)? research ("YES")
  • Find mathematical proofs and don't get scared
  • Using pop_back() function (similar to push_back) pop_back
  • using resize() function resize
  • using substr() function, Reaaally helpful! substr

--- New Things to learn:

  • Writing LL after a integer constant makes them Long long, good for using max() functions, can I convert into any other format like float to double?
  • ANS: Yes I can, by multiplying with typecast of 1.0 . ** eg int x=5.0; x= 1.0*x; ** //now x is double
  • Maybe there is some list of questions like C. I should search for that!

  • Sparse Tables, problem E uses them, will learn and share good resources!

---- Pending :

  • Read and try E

EDIT 1: D has been solved really neat how the editorial solves the problem, not the approach but the code. Soo smooth.

----Song of the contest

Sweet Child O' mine by Guns and Roses :)

Full text and comments »

By Way_Above_your_level_lol, 4 years ago, In English

Time: 8:08pm IST - - Solved A - Solved B - Solved C - Solved D - Couldnt think of E

-- Upsolve :

  • Idea for A was on point. Can reduce time taken from 5 minutes to 4.
  • B was easy too but didn't implement faster.
  • C was good since I tried a custom testcase before running my code, which led me to right solution so should always make my own testcases.
  • D took too long. Got confused in my own variable names and used wrong indice for array. Can be more careful, should've been done within 1 hour.
  • E no idea how to approach. Started playing Runescape lmao, didn't have long enough attention span. Maybe since I never solve till D? Need to work on this.

--- New Things to learn: — Patience - finding max element in array using C++ inbuilt function.

---- Pending :

Read and try tutorial E2 and F

EDIT 1: Solved and understood E1 very easy greedy solution. Should've spent more time!

Cheers.

Full text and comments »

By Way_Above_your_level_lol, history, 4 years ago, In English

Time: 9:15pm IST

  • Solved A
  • No idea B
  • TLE C
  • Not Read D -- Upsolve : Idea for A was exactly on point. can reduce time taken from 5 minutes to 4.

Got confused while solving B. Should've just written down math formulas instead of weird diagrams.

Was on right track for C i.e. greedy approach. Should've thought more about reducing time using hashmap.

Didn't read D since was preoccupied.

--- New Things to learn:

  1. How to use lower_bound() Will read on C++ forums.

  2. Euler totient functions: formula is easy but will watch youtube video for proof.

EDIT1 : Found link for proof. Time stamp for crux : 2:47 Euler totient proof

EDIT2: Found link for lower_bound() Lower_bound reference

---- Pending :

Read and try E

Cheers.

Full text and comments »