I have gathered a lot of things to ask so i decided to write a blog.↵
I also have a few things to tell about my experience of the last [contest](https://mirror.codeforces.com/contest/2229) held on codeforces.↵
↵
You can directly jump to the questions if you don't want to read the story.↵
↵
**Question 1.**↵
↵
(i) How often do you stress test during a contest ?↵
(ii) How much time do you take to write the brute solution ?↵
Does it actually take around 5 mins like [user:Dominater069,2026-05-26] said in [this](https://mirror.codeforces.com/blog/entry/133289) blog.↵
(iii) When should i stress test a problem during contest ? Only after getting a WA ?↵
↵
I usually get the logic of the problem correct, but end up getting a WA due to some edge/special case or a minor flaw.↵
↵
Please share if you have any valuable resources about stress testing.↵
↵
I got a WA2 in Problem B so i went to stress test it directly. The sad part is that i took approximately 15-20 minutes writing the brute solution, i got B accepted at 00.43 which is kind of a shame, but anyways.↵
↵
C1 i did in 6 minutes and started C2.↵
↵
I wrote the correct code for C2 in like 20 minutes, but i was not confident enough to submit as it was my first time submitting a C2 in any contest above Div3, also some candidate master in my friend list had 2 negatives in C2 and none of the friends got it accepted at that point (there was also a 50 pts penalty). My output for each given test case(a vector) was not the exact ones given, because multiple answers were possible for the questions and i was also aware about it. So, i thought instead of dry running the operations and calculating the parameter (which was supposed to be maximized) for both outputs, and then comparing them, let's just write a brute quickly and stress test it as my solution will "obviously" have many flaw. Again, sadly i took a lot of time writing a brute (in this one i had to take all permutations of 0 to n-1 and then all possibilities of taking/skipping that index, so the time complexity was O(n! * 2^n) ). I wrote it, and there was some segmentation fault in my brute so i just got frustrated and submitted (at 01.52) the same solution which i wrote initially. And it got accepted. I was experiencing many emotions at the same time, frustration of not submitting it 30 minutes ago, and excitement of solving C2 in a Div. 1+2 in first go. ↵
↵
Past this point, i was not able to concentrate in the contest like before.↵
↵
As for the Problem D(spoilers ahead), i completely did not see the Binary Search on answer approach. But i came up with a greedy strategy which i thought should be optimal (it was). Although, i was not able to implement it in 1 hour. I still think that my approach was much more intuitive, and will share it in some other blog maybe.↵
↵
**Question 2.**↵
↵
(i) How to be sure if my greedy solution is optimal or not?↵
(ii) Do i need to emphasize on standard techniques for proving greedy solutions mentioned in books, or i just have to take a gist of their ideas?↵
↵
I have tried to learn proving techniques like exchange arguments and greedy stays ahead from a lot of youtube videos and books (i also found [this](https://mirror.codeforces.com/blog/entry/111849) blog insightful). But till this point i haven't understood anything except the very idea of the techniques. Although, i think my problem solving skills of greedy and constructive problems have improved a lot, only by knowing these ideas. ↵
↵
(iii) For the people who are Candidate Masters and above, how often do you think about these proofs of correctness when solving greedy problems ? Does it now get just intuitive ?↵
↵
(iv) Is there a way to know that this problem is not a greedy one ? (or am i just not good enough in DP lol) ↵
How do you know if "you" are not able to come up with a greedy strategy or this problem is not a greedy one?↵
Or do you first think about DP, then greedy ?↵
↵
There are a lot of instances when i waste 1.5 hours on a problem in a contest trying to find a greedy strategy just to know it was a DP problem. Few examples are [this](https://www.codechef.com/START232D/problems/SORTSUB9?tab=statement) and [this](https://mirror.codeforces.com/contest/2222/problem/C).↵
↵
Some types of dp like knapsack, dp with bitmasks, even matrix chain multiplication can be seen directly, atleast in easier problems. But things like interval dp and partition dp is pretty hard to find. Can you tell me the patterns which signals you to think about these ?↵
↵
Please share if you have any good resources related to proving a greedy solution or finding out DP v/s greedy.
I also have a few things to tell about my experience of the last [contest](https://mirror.codeforces.com/contest/2229) held on codeforces.↵
↵
You can directly jump to the questions if you don't want to read the story.↵
↵
**Question 1.**↵
↵
(i) How often do you stress test during a contest ?↵
(ii) How much time do you take to write the brute solution ?↵
Does it actually take around 5 mins like [user:Dominater069,2026-05-26] said in [this](https://mirror.codeforces.com/blog/entry/133289) blog.↵
(iii) When should i stress test a problem during contest ? Only after getting a WA ?↵
↵
I usually get the logic of the problem correct, but end up getting a WA due to some edge/special case or a minor flaw.↵
↵
Please share if you have any valuable resources about stress testing.↵
↵
I got a WA2 in Problem B so i went to stress test it directly. The sad part is that i took approximately 15-20 minutes writing the brute solution, i got B accepted at 00.43 which is kind of a shame, but anyways.↵
↵
C1 i did in 6 minutes and started C2.↵
↵
I wrote the correct code for C2 in like 20 minutes, but i was not confident enough to submit as it was my first time submitting a C2 in any contest above Div3, also some candidate master in my friend list had 2 negatives in C2 and none of the friends got it accepted at that point (there was also a 50 pts penalty). My output for each given test case(a vector) was not the exact ones given, because multiple answers were possible for the questions and i was also aware about it. So, i thought instead of dry running the operations and calculating the parameter (which was supposed to be maximized) for both outputs, and then comparing them, let's just write a brute quickly and stress test it as my solution will "obviously" have many flaw. Again, sadly i took a lot of time writing a brute (in this one i had to take all permutations of 0 to n-1 and then all possibilities of taking/skipping that index, so the time complexity was O(n! * 2^n) ). I wrote it, and there was some segmentation fault in my brute so i just got frustrated and submitted (at 01.52) the same solution which i wrote initially. And it got accepted. I was experiencing many emotions at the same time, frustration of not submitting it 30 minutes ago, and excitement of solving C2 in a Div. 1+2 in first go. ↵
↵
Past this point, i was not able to concentrate in the contest like before.↵
↵
As for the Problem D(spoilers ahead), i completely did not see the Binary Search on answer approach. But i came up with a greedy strategy which i thought should be optimal (it was). Although, i was not able to implement it in 1 hour. I still think that my approach was much more intuitive, and will share it in some other blog maybe.↵
↵
**Question 2.**↵
↵
(i) How to be sure if my greedy solution is optimal or not?↵
(ii) Do i need to emphasize on standard techniques for proving greedy solutions mentioned in books, or i just have to take a gist of their ideas?↵
↵
I have tried to learn proving techniques like exchange arguments and greedy stays ahead from a lot of youtube videos and books (i also found [this](https://mirror.codeforces.com/blog/entry/111849) blog insightful). But till this point i haven't understood anything except the very idea of the techniques. Although, i think my problem solving skills of greedy and constructive problems have improved a lot, only by knowing these ideas. ↵
↵
(iii) For the people who are Candidate Masters and above, how often do you think about these proofs of correctness when solving greedy problems ? Does it now get just intuitive ?↵
↵
(iv) Is there a way to know that this problem is not a greedy one ? (or am i just not good enough in DP lol) ↵
How do you know if "you" are not able to come up with a greedy strategy or this problem is not a greedy one?↵
Or do you first think about DP, then greedy ?↵
↵
There are a lot of instances when i waste 1.5 hours on a problem in a contest trying to find a greedy strategy just to know it was a DP problem. Few examples are [this](https://www.codechef.com/START232D/problems/SORTSUB9?tab=statement) and [this](https://mirror.codeforces.com/contest/2222/problem/C).↵
↵
Some types of dp like knapsack, dp with bitmasks, even matrix chain multiplication can be seen directly, atleast in easier problems. But things like interval dp and partition dp is pretty hard to find. Can you tell me the patterns which signals you to think about these ?↵
↵
Please share if you have any good resources related to proving a greedy solution or finding out DP v/s greedy.
