Dominater069's blog

By Dominater069, 2 months ago, In English

Recently, I got a request asking me to write down my thought process while solving questions. So, here is the promised blog.

I would like to thank IceKnight1093, qwexd, Sana, Everule and NovusStellachan for proof reading and suggesting edits in the blog. Special thanks to satyam343 for discussing most of the blog with me.

1. Overview

The blog contains my solutions to $$$7$$$ problems in a wide range of ratings, starting from $$$1200$$$ all the way upto $$$2700$$$. Each problem has a step-by-step solution and you can notice how there are no large jumps in logic, but everything comes naturally. I do not claim that this is always possible in each problem, however I solve majority of CF problems in such a manner.

There are certainly other high rated people who will have completely different methods of solving. However, this is about what works for me. There are some meta ideas taken from parts of the solution and listed at the end in a "What can we learn?" section. I hope the blog is useful for you.

2. Some General Question Solving Strategies

Here is a non-exhaustive list of techniques that are useful to keep in mind. These are internalized by most experienced participants already but maybe it helps you.

  • Figuring out the Nature of an Optimal Solution. One of the most important thing in problems imo.

  • Solving subtasks of the original problem and then trying to extend/generalize your solution.

  • Fixing a parameter and then trying to maximise the result with respect to that fixed parameter.

  • Finding necessary and sufficient conditions. Sometimes, your necessary conditions themselves become sufficient, or vice versa.

  • Identifying Lower and Upper bounds, and constructing them.

  • Reducing a problem into smaller subproblems, commonly used with Dynamic Programming or Inductive Proofs.

  • Considering the Decision Version of the Problem instead. Especially useful in Counting problems, where you need to count number of good subsequences for example.

  • Formalizing the Problem

3. Questions and Solutions Section

Question 1. 1979C - Earning on Bets

Step 1
Step 2
What can we learn?

Question 2. 1987D - World is Mine

General Idea
Step 1
Step 2
Step 3
Step 4
What can we learn?
Similiar Problems

Question 3. 1977C - Nikita and LCM

Step 1
Step 2
What can we learn?

Question 4. 1889B - Doremy's Connecting Plan

Step 1
Step 2
Step 3
What can we learn?

Question 5. 2002D1 - DFS Checker (Easy Version)

Step 1
Step 2
Additional Note
Implementation
What can we learn?

Question 6. 1930E - 2..3...4.... Wonderful! Wonderful!

Step 1
Step 2
Step 3
What can we learn?

Question 7. 2003E1 - Turtle and Inversions (Easy Version)

Disclaimer : My solution differs from the editorial completely. You can read the editorial for their approach. I will present mine. Try to extend to the hard version of the problem from this.

Subproblem
Subproblem Step 1
Subproblem Step 2
Subproblem Step 3
Step 4
Additional Note
Hint 1 of Hard Version
Hint 2 of Hard Version
What can we learn?

4. About Stress Testing

Something which a lot of low rated participants do wrong : They don't stress test.

There have even been contests where I stress tested $$$3$$$ problems. I tend to make a lot of errors while writing code and it is not easy to always catch those errors with manually reading or debugging. Learning the skill of stress testing is insanely useful (and you don't need any tools for it, I do it all in the same piece of code without taking much time).

This was the first problem (I think) that i had stress tested during contest : 1854A1 - Dual (Easy Version) I was still done within $$$12$$$ minutes and it took me less than $$$5$$$ mins to stress test, and fix my bug (this is an easy example though as I didn't have to write a brute). My bug only occurred when all elements of the array were equal and negative, I don't think I would manually be able to catch that.

1987F1 - Interesting Problem (Easy Version) In the initial submission to this problem, I missed so many if-cases. I was very careless. But i managed to stress test and avoid more WAs. I think it took me 3 — 4 iterations of finding bug with stress test, fixing them and then again running stress test before my code was actually correct.

I highly recommend stress testing for you. It is simpler than you think : all you need is a brute function, and a generator. I usually replace my input function with a generator, and use a lambda function for the brute. It takes barely $$$5$$$ minutes to setup for most problems.

  • Vote: I like it
  • +263
  • Vote: I do not like it

»
2 months ago, # |
  Vote: I like it +2 Vote: I do not like it

Dominater069 orz Thanks for the CodeChef rounds and for writing comments in your solutions. I hope to see more educational blogs and contests from you.

»
2 months ago, # |
  Vote: I like it -36 Vote: I do not like it

bro stop wasting your times writing this blogs and instead practice some problems.
we are desperately waiting for first LGM from bharat

»
2 months ago, # |
  Vote: I like it +27 Vote: I do not like it

Thanks for the blog. Also congrats Dominater069 on reaching 2800+ and LGM performance this contest.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

thanks

»
2 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Thanks for the great blog! I think it's worth mention that writing a few example on paper and making conjecture/observation based on them is also extremely useful and used a lot when solving ad-hoc problems.

»
2 months ago, # |
  Vote: I like it +52 Vote: I do not like it

I guess Radewoosh was incorrect on this one /j

Also, one last tip: I've noticed it observing all the top people on Codeforces/Atcoder. None of them uses the word "question" instead of "problem"/"task". So don't do it. You won't progress if you'll keep calling problems "questions"
  • »
    »
    2 months ago, # ^ |
      Vote: I like it +97 Vote: I do not like it

    It is intentionally done due to that :)

    If you look deeper into the blog, i always mention "problems" (because i was lazy to change them) only the headings have questions

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      you don't solve questions you answer them

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      you might become the first "question" lgm

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I really wanted you to do this <3. As they always target lower-rated individuals.

»
2 months ago, # |
  Vote: I like it +117 Vote: I do not like it

God, it's like staring in the mirror...

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

this strategies are really very helpful

»
2 months ago, # |
  Vote: I like it +3 Vote: I do not like it

can you elaborate what you mean by "Nature of an Optimal Solution" ?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    what are some properties that at least one best solution of the problem may contain?

    for example, read the solution to q4 and its what can we learn section

»
2 months ago, # |
  Vote: I like it +4 Vote: I do not like it
Typo for Q1

Other than that, this is a nice blog as I can see how a top competitor approaches a problem. Please do more of these write ups!

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

It would be nice if someone added this blog to the catalog

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

That's of great help! Hope it can be read by more!

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

If I encounter a new thing while solving a problem, then how do I learn that topic and questions related to that to solve for getting better at it? For e.g. Graph or DP.

»
2 months ago, # |
  Vote: I like it +13 Vote: I do not like it

Thank you for your helpful blog! I still have a questions(perhaps there are many others who have the same question): how do you complete a stress test in 5 minutes? Can you explain it in more detail?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    278921664 This is what I do

    Of course time taken depends on the time to write the brute mainly, and so longer brute => longer time.

»
2 months ago, # |
Rev. 5   Vote: I like it +2 Vote: I do not like it

“Great work!@Dominater069 I really appreciate the valuable time you put into this blog. I believe that combining all these with other great blogs in the catalog will help us improve to a certain extent.”

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

"(You can do it the other way too, for example dp(i,j)= the maximum value of |x| under the constraint that $$$∑freq_x$$$ is j ).

If you understood the question, transitions are pretty simple to come up with(no its not) and are left as an exercise."

How? Don't we need the value of the dp ( |x| ) to do the transitions?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks a lot for the tips, also where can I find a more detailed guide for stress testing? thanks again :)

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

thanks , we need more of this !

»
2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I see most of your explanations are heavily relied on mathematics(algebra). If you don't mind can you please suggest us the topics that we need to master in mathematics in order to come up and write the solutions as you did in the blog. Thank you!!

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for this really helpful blog!

»
3 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

Waiting for, How to Create Questions Dominater069 Version

»
3 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

Please write a blog about stress testing