I request you all to answer the following questions based on only your experience and nothing else.
During a contest, when you get a solution to a problem, do you actually prove the solution to be true or just use some test cases and check if the solution works correctly? I feel the latter answer is obvious but I would still like to take a poll. The reason for asking this question is because sometimes, I am just not confident enough on my intuition and feel like I am missing some test case which can prove it wrong. Also, I am not that good when things come to prove something though I understand the proofs done in the editorials. Lastly, when I submit it (my intuitive solution) and I receive a WA, it demoralizes me to such an extent that I feel I should quit the contest immediately.
In a greedy vs dp scenario, how do you judge if the problem can be solved greedily or not? I am new to dynamic programming (though I am practicing it for the past few months) and often get confused when encountering such scenarios. The reason for this confusion is mainly because of not being able to find a test case that fails the greedy solution. I also understand that constraints are important in analyzing the type of problem and the first thing I do is analyze the time complexity of the dp solution. Then I think of a greedy solution. But most of the time, I fail to optimize my dp solution or believe it to be a greedy problem and receive a TLE or WA respectively. Hence, I need your help here.
How do you all stay motivated, especially in a scenario where your past 5-10 contests have gone bad? I am currently going through it. I have no aim whatsoever regarding my rating but my only aim is to be able to solve 4-5 problems (Div2A — D) in a contest as fast as I can and increase this count with time. But for the past few contests, I was either able to solve 4 problems but I was comparatively late (compared to my peers) or I solved fewer problems that too after a series of WAs and TLEs. What do you do in such conditions?
Do you keep an eye on standings? I understand looking at the dashboard at regular intervals, as there can be a problem with increasing submissions ahead of what I am trying to solve (like contest #643 where D was easier than C). But do you look at the standings? My general protocol is to look at the standings after I solve 3 problems. This usually tells me how fast I should be to solve the fourth problem (again, compared to my peers).
Do you read all problem statements before attempting one? If yes, how are you able to think of a solution/idea immediately to rate a problem easy or difficult? I have seen many people practicing this and I do not understand how they do it. For example, consider contest #643 again. There must be a few people who read D and attempted D before C. This led others to think that maybe D is easier than C and hence the chain. But how do I identify such things? If tomorrow the submissions are invisible, how should I check if the problem ahead of the current problem was easier than it should be at that hierarchy?
I request you all to answer as honestly as possible, even if it means throwing hard truth directly on my face. A very big thank you to all and to MikeMirzayanov for this platform.
Auto comment: topic has been updated by IngaleAnkur10 (previous revision, new revision, compare).
1) Use testcases to check.
2) If the time limit and memory limit allows DP and DP seems obvious then it is DP. Practicing helps recognise problems which require DP.
3) Passion for CP.
4) I look at the standings after every 5/10 minutes. Helps me to be aware of the solutions people are submitting, what is the number of people failing the pretests and also my rank.
5) I see the number of submissions on problems and check those problems in order and then decide which one to solve.
Understood. But what is your reason behind looking at your rank during the contest? I mean how does it affect your contest?
it COULD (big on COULD) be an indication that you're spending too much time on one problem. although i usually do them in order unless for 10+ minutes i've made absolutely ZERO forward progress
Recently I am seeing myself submitting A/B based on intuition without proofs. I think recent Div2 A/B problems have become harder.
I start with greedy mostly and try to break it for few minutes. If broken I switch to dp.
Recently I have been upsolving a lot. Now my motivation does not come from rating but from the number of (hard) problems I upsolve.
Yes, I need to know how I have been doing so far.
I solve A, B and then read C,D. Mostly I don't read E (only when it has more than 800 accepted)
it demoralizes me to such an extent that I feel I should quit (I think this happens to everyone from time to time. )
Div2 A/B, for me, has to be solved intuitively as I do not have enough time to think of a proof. And yes, Div2 starters are becoming harder, especially now that we have Div4 rounds taking place, it will become even harder.
How do you determine hard problems? Based on rating, tags, submissions?
If I read a problem and don't submit the solution, will my rating be affected? I am new on this platform. please reply
No.
1) Just testcases. It helps to just practice intuition, such as coming up with countercases to bad solutions. Maybe take some obviously-DP problems and come up with a greedy for it, then try to disprove it. Or try your hand at hacking, e.g. during Div. 3's. And it may also just be your code that has a mistake. In any case, don't lose confidence. You can, for example, first assume your logic is sound and try to scour your code for bugs, then later try to disprove your logic if you find nothing (or if you're totally lost, try a new solution). Especially in Div. 2 where there are many problems that decide the rankings, a single penalty or two probably won't have much of an effect.
2)
You should almost never submit a solution you think will obviously TLE, unless it's a tight constant factor. As for greedy, this has a lot to do with (1). Ultimately it'll come down to your intuition, which you can improve with practice.
3)
This mindset seems bad, because it seems like it'll give you thoughts like "oh no, an hour has passed and I only have two problems, guess I'm screwed." Your goal should just be to do the best you can. It'll help you focus. You can almost always save a bad contest, but not if you're freaking out about it. And as for your current losses, that only means your next gains will be bigger!
4) I prefer the contest dashboard and generally avoid the standings because seeing those usually throws rating or such into the equation. The exception to this was Round 641 after solving A-C because I figured that I had been decently fast and that the rest of the problems would be near-impossible.
5)
This is impossible. If you could instantly rate a problem by solving it, you'd... have the solution. If you feel stuck on a problem, it often doesn't hurt to glance ahead and see if you have any leads on the next one, but the generally optimal strategy is to follow what either the score distribution or dashboard says (I have learned this from experience).
`I can relate point 3. There are times where I feel I won’t be able to reach the fourth problem, and in a hurry, makes a mess in the third problem itself. And your reply on point 5 gave me a new question: How does score distribution affect your strategy? Do you plan on something different depending on it?
Usually not. What I mostly meant was the initial ordering of the problems. In an ideal contest, I would just mow down the problems one by one with disregard to the ordering.
Yes, that’s what I follow as well. The score distribution tells me one thing for sure: the expected difficulty of the problem. As seen in contest #643 A problem, having a score of 750 rather than usual 500 gave me a hint on the difficulty of it.
Than what about C and D , according to the score distribution shouldn't there difficulty be reversed. That's why i don't particularly pay attention to score distribution and rather check the dashboard for number of submissions of a problem to decide it's difficulty level.
I almost always prove the solutions. But it's not like after I'm finished thinking I start to prove. Usually the proof just develops as part of the problem solving process. Sometimes I write up some solution based on only gut feeling, but in general I dislike doing this, because I have no idea of exactly how wrong I am after getting WA.
I don't solve problems this way — I don't try to force a greedy solution on it (or a DP one). Instead, I look at the situation presented in the statement; make observations, notice its properties, simplify it, try to understand it better. Then I can piece together a solution. The result may be a DP solution, or a greedy one, or something else. But I don't start solving the problem by "hmm today I'm going to write a greedy".
I don't know. I think solving beautiful problems gives enough satisfaction even if contests go meh.
Yes, to have the most information. But looking at "how fast I should be able to solve" seems pointless.
Not all of them. But if it seems that skipping a problem might be a smart move, I read multiple statements at a time.
I agree on all the points you mentioned but would like to discuss on point 2. My usual strategy is to find a greedy solution based on the sample test cases and then I check if it works for other test cases. But I feel your view is better than mine as without noting some facts and properties given in the problem, I am just making a huge mistake, which I might not even find till the end of the contest.
And how do you get time to prove solutions? I guess that as well comes with practice.
I don't think I understand. Making observations and all that is all part of the proof (by "making observations" I don't only mean noticing that stuff happens, but also understanding why stuff happens). I don't take some extra time to prove, it's just all part of the problem solving process for me.
Of course I don't write them out in detail to present to someone or something. But usually if I solve a problem I can rigorously prove the solution.
Actually it was me who didn’t understand. Thank you.
I don't take some extra time to prove, it's just all part of the problem solving process for me.Did you try solving yesterday's D? I don't see how you can arrive at the proof "as a part of thinking process". This may be true for certain problems where the proof lies in the observation, but there are certainly a non-trivial amount of problems where you first come up with a lemma which solves the problem, and proving the lemma is orthogonal to getting AC.
About point 2, don't you think rational process of making observations, analyzing properties and making decisions based on them doesn't work in many constructive problems, e.g. Problem E of global round 8? The only way I can think of solving this type of problems is: guess randomly as many ways as I can and check if any of them works.
Do you know a better way to tackle such constructive problems?
My solution to 1368E - Ski Accidents developed more like this.
I observed that instead of just deleting vertices we can think about it like splitting vertices into "sources", "sinks" and "deleteds".
After that it became kinda obvious that if we assigned the vertices greedily in topological order (into the "best possible state") the condition would be satisfied because each source generates up to 2 sinks and each sink generates up to 2 deleteds.
Obviously some guesswork is involved. I guessed that I should look at the problem as in point 1: I did not know before thinking that this approach would work. Guesswork is always involved in making observations and analyzing the object. You have to guess things like "what if I looked at it this way?". I don't think it contradicts my point 2.
And in such constructive problems in general: simplify the thing you're building, try to understand what it actually is. And yeah, I totally agree that sometimes in constructive problems you just have to try lots of constructions to see if they work.
What I meant in point 2 was more like: often newcomers try to force some kind of very rigid "template" approach on a problem. But in even slightly harder problems that's not going to do much.
Speaking about the constraints, well they also help. For example, if there are limits like
n < 100000, k < 7, then it's probably something about bitmasks, etc. So I would generally never look for a greedy solution when the constraints are sufficiently low. Sometimes that strategy even works, LOL.1) Probably more often than not I submit without proof, because during contest time is a relevant factor, and proofs take extra time and are sometimes tough to make in a rigorous manner. I check the given testcases and, perhaps, some more own test cases, if I am not confident enough about my intuition. Sometimes writing a brute force helps, as that way you can check more test cases, and maybe find some pattern, observation or a counter example. That said, I would avoid submitting something that looks random or counter-intuitive.
2) Greedy is only applicable when local optimum at each step implies global optimum. But I do not think there is an universal recipe to recognize when this is the case. Also, if thinking of the problem in terms of DP states, and a given state depends on more then one previous state, then I guess it is less likely for a greedy solution to exist, unless it calculates something unrelated to the DP states. Sometimes, a top down DP (recursion with memoization) can be easier to implement than bottom up DP. Making the choice based on constraints, rather then the problem itself, seems strange to me though. I think the constraints should be a hint and not a decisive factor.
3) Rating is not the only and not the main motivation for me. I find learning stuff to be motivating. That is why I do not only solve problems in contests, but also do practice problems when I have time and also upsolve some contest problems. Also I do not think it is a good idea to set hard expectation restrictions like "I must solve x problems or I am not good enough". (Nobody knows in advance what round it is going to be, and rounds vary in difficulty.) That makes you more susceptible to tilt. Do not exert artificial psychological pressure onto yourself. Go into the contest open-mindedly and solve as much as you can as fast as you can. Do not bother too much where you stand relative to your peers.
4) As long as I have a (relatively) easy problem to solve and no doubts on how to solve it, then why waste time? Go for the solution. Usually I do not look at the standings until I am stuck on some problem. Then I check the number of accepted solutions per problem, to see if there is some imbalance in the score distribution, and which other problems I want to at least read.
5)I read the problem statements in the order of increasing score, one at a time, and try to solve it before going to read the next one. Only if I am stuck, I will go and check other problems, to see if I can use my time better somewhere else (especially if there is an imbalance in the score distribution indicated by number of submissions; if there is an imbalance, then likely the trend will be already visible by that time, I am not fast enough to be able to discover the imbalance and initiate that trend myself). To assess, if the other problem is actually easier for me or not, I do have to invest a fair amount of time into thinking and trying to solve it, it cannot be done just by reading, unless it is a very badly misplaced problem like A/B level in the position of D, then it might happen that you read it and the solution just clicks shortly after.
I agree with all your points. In point 5 you mentioned a "fair amount of time". What, according to you, is the fair amount of time for A,B,C,D. Is it just intuition or standings or a hard fixed time constraint like 15 mins?
I do not have a rule of thumb on how much time to spend per problem. I take the time to fully understand the problem, work out examples, think of how I could approach the problem, trying to find some patterns and observations, until I run out of ideas and do not make any progress. Then I might read another problem.
Depends on a problem. If it is Div2 A-C, I just check if sample test cases give correct answer and submit. If it is something where submitting 5 min later is less crucial and solution is likely to be more complex than what I came up with, I try to draft a proof or try test cases where my solution's weak spot feels to be. Regarding the motivation: some time ago I watched a stream by some LGM, where he was solving Div1, same as me. Needless to say, he got first 3 problems in smth like 15 min, and I was working on them for almost the entire contest. But! He submitted a wrong solution to A or B, did not even wait for pretests to pass, and continued to the next problem. The next time he saw the submissions page and that his solution was wrong, he just returned to that problem and corrected the mistakes. 1 WA is not a big deal, in the end.
Tough question — as if I could tell myself in 100% cases. Usually I think "when is my dp transition wrong?" — and answer is usually "maybe, if there is a situation, where ..." and then I try to investigate this hypotetical situtation until I come to a contradiction or a valid counter-example. But it is not easy, that's for sure.
When my rating did not grow for a long time, I just started practicing more. Unlike real-life CS problems, CP problems have solutions. And if these are not some crazy math transformations or novel data structures that appear in late Div1, the editorials are understandable, right? Thinking that there is a sequence of thoughts that I could in principle arrive to, always motivates me. Of course, the cases when I can barely understand the editorial, extremely demotivates me, but I just think that after I master easier matters, I will have time and knowledge to dig into these crazy tricks.
I usually look at standings if I am stuck at some problem longer than I usually do. Then I check the problems page to see how many people have solved it — sometimes it is just a hard problem, sometimes score distribution is not right, and there is some later problem that people are solving.
I always read problems in the order. However, if I feel that this problem hits my weak spot (like, I am really bad at this type of problems), I check the next problem. In today's #643, I was solving C, and when I felt that it's too much coding, I checked the problems page and saw that more people are solving D. I still went for C first, but if I was not sure about it, I would switch to D immediately.
im a cyan noob but here's what i do:
a) if a solution doesn't come up for me, then i will generate some tests and try out solutions as they come along. usually i'm missing a few pieces each time but at the end either i missed the whole point of the problem or i constructed a solution. or sometimes i get super lucky and find out the whole answer in the last like 2 minutes
b) time complexity analysis generally will tell you whether you can DP or greedy it. if worst comes to worst, first greedy then convert to dp if it fails
c) dude, idk. some contests i get A-C relatively easily, some i get hardstuck on B. i guess keep on trying, don't focus on the result too much (if ur ego gets tied to stuff like rating it'll mess with your head, regardless of how good or bad your rating is)
d) sometimes if i get really tilted, i'll look at standings. if there's someone that TLEd on test 17 along with me, i know that i had the wrong approach for sure and i'm not just being crazy and that i have the right answer but it's implemented poorly. other than that not really.
e) no ,but i probably should. this D was so much easier compared to C, I spent 30 minutes checking C and I still couldn't get it, I didn't understand the editorial even though I had the general intuition that they had :/
I will answer all these referring to contest 643
I couldn't think of proofs so I went with intuition B and D. I figured if the intuition was wrong I would fail the pretests. The intuition was correct (Although I did fail the first submission for D because I output "N0" instead of "NO", I don't know why I did this).
My thoughts during the contest B is probably greedy, no one is going to put a DP problem on a Div 2B worth 750 points.
I came off a few bad performances entering the contest but I felt confident because practice was going well.
I looked at the standings after solving problems to get an idea of what to solve next.
I jumped around a bit. My final solve order was B,D,C,A. I started at B because after staring at A for a while I couldn't see a solution. Then I looked at C but it looked tedious so I moved to D because it looked more fun. After solving D I moved back to C. I suspected I could solve C because I was familiar with the key insight to solve the related question where if you randomly cut a rod into three parts what is the probability the parts will form a non-degenerate triangle. I figured out a solution using this insight and one other trick. Then I went back to staring at A and saw the insight required for the solution. After I solved A I had about 30 minutes left. I read E and F. F looked more interesting. I had some ideas for F but there was not enough time to find and code a solution.
Solve counts will generally tell you which problems are easier and which aren't. But, are there any instances where you were one of the first solvers of a later problem which lead to a chain (others seeing solve count and so on)?
Not me first solving, but rather me following the chain of solvers :)
You will see this a lot in ICPC contests, where problems are not sorted in difficulty order. Often easy problems are missed because people follow most solved problems instead of reading everything.