Hello Codeforces!
On today's contest, Codeforces Global Round 26, I lost a ton of rating because of many Wrong Answers and I was very slow today. Does anyone have any tips for avoiding wrong answers? Does anyone have any tips for getting faster at solving the easier problems?
Also, for today's C1, it took me forever to come up with the idea for how to solve it. When I solved it, I was so frustrated because of how simple it was. Do any of you have a way of looking at problems that helps you solve it? I've noticed that easier problems tend to have a greedy/brute force solution to it. Do you notice any tendencies of greedy methods?
Thanks!
UPD: Even if you think that I am stupid and downvote, please answer my questions to the best of your ability. Thanks again!
be like rainboy :)
that does work for rainboy
what do you mean?
rainboy is so good that he doesn't even need to solve the easy problems. Best way to avoid WA.
Your title is quite misleading. I clicked on ur blog to see the tips, but found out u r the one just like me who is searching for the tips. It would be nice if u just add a "need" before ur blog title so that others doesn't face the same issue.
Thanks for the suggestion!
Thanks for listening!
Hope you get back to pupil soon!
Thanks for the good wish. I am finally back to pupil. Would u please give me some guidelines on how to reach the next rank like u?
Good job on pupil! 1999 place is crazy! In general, to reach specialist, you would probably try getting at least 4 problems in Div 3/4. Div 3/4 can really carry you to specialist, but since there is a lot of Div 2s coming up, you should try using the Div 2s. For Div 2, try solving the first 3 problems. For example, you could try practicing on Div 2 problem C from previous contests. Speed is another thing, especially when contests have a big line between two problems (problem difficulty difference is big), then speed is the next deciding factor that can determine how much you go up/down by. Please ask if you have any questions, and good luck on reaching specialist!
4 problems on a Div 4 isn't enough. You have to aim for 5(but you have to be very speedy) or 6(time probably doesn't matter for this) to achieve specialist.
On a Div 3, you have to aim for at least 5 problems. There was one time where I solved 5 problems very slowly, yet I still went up by 10 rating when my rating was 1430.
On a Div 2, solving the first 3 problems is great, but for specialists, you need to solve the 3 within the first 1.5 hours assuming the problems are "regular" difficulty.
Of course, this all varies depending on the contest.
You realize they are a pupil right?
I realize that, but I'm saying that this is the necessary results to reach specialist.
I put these numbers as a lower bound, yours is for going up at specialist. For whoever is reading this, hope this message helps you understand.
You have to aim higher to achieve success :)
Auto comment: topic has been updated by rangerscowboys (previous revision, new revision, compare).
i think that u should not focus on speed too much as you develop it with time, try to solve more problems,for example yesterday i was so slow (usually my goal is to solve 3 problems but quickly)i could not do that but i solved 4 problems which was better
hmm yeah i wonder what i should practice to improve my cf rating
Auto comment: topic has been updated by rangerscowboys (previous revision, new revision, compare).
guessforces!
yeah guessing is good option, dont solve anything, just guess the solution
Well, do more virtual contests, and try to thing about edge cases while implementing, also you shouldn't care about your rating at all, you shouldn't get demotivated about a single -58 when you know that you can do better
Forget about greedy, think DP. If DP doesn't work, guess the greedy.
Seems to work fine for the current meta.
My approaches for the global round were:
A — think about max and min values, try something with them
B — think about backtrack (dp) then realize that the choices don't change anything, turns into greedy
C — DP
D — Just do what the statement asks for fast enough
E — solve the samples by drawing them and guess the DP
F — guess that the local conditions are sufficient and code the DP
as you can see, lots of DP and guessing.
In general, is there up to a certain problem where it is good to think about greedy? (Like the easier ones such as A and B)
It depends on the problem. If someone says "How many times do we need to pick option 2 ? We only need to pick it once. How can we calculate the final value for every position we can pick?" I see it more as a "I'm too lazy to give you a practical approach for this problem so here's a brain-teasing specific approach for it". Why think about the specific problem if you can simply solve it with a general approach that works for many other problems?
Ah ok. For C1 I did greedy, but DP was definitely possible. DP is probably the thing I am worst at, do you have any places that I can practice DP? Even though I learned DP, I don't really practice it and now I've kind of lost my DP skills lol. Also, should I know all types of DP?
So since you seem to be asking seriously here's my actual opinion:
The most important skill in CP (and even more so in learning DP) is being able to solve problems through some sort of bruteforcing. I include backtracing as bruteforce, and that's kind of the basis of DP if you learn top-down dp. The reason for it being important in general is that I believe that many problems can be solved by simply first understanding the problem and then trying to get some correct solution ignoring the complexity. That usually leads to a fast enough solution either through some observation that you don't have to try every choice in the bruteforce or just leads to it directly. It especially works for the first few problems in div2, because the way to make the solution faster isn't locked behind knowledge of some data structure/algorithm.
We have an example of how I put that into practice here: problem B from the global round. If I don't know how to solve the problem, a good first step is imagining what a backtrack solution would look like for the problem. Then the problem solves itself. A similar approach is "try testing everything and then notice what's useless to test" that appears in problems where you could solve it by nesting fors but that's too slow, then you do the same thing but faster.
As for how to practice dp: master how to write backtrack solutions, then dp solutions should come naturally once you understand what you need to do (make the function depend only on the parameters that are given and possibly some fixed variables). Then solve lots of dp problems. You might encounter problems that bottom-up dp makes it easier to reason about the solution, when you've seen enough problems just spend some days coding only bottom-up dp and force yourself to learn it. There's no skipping solving problems by yourself.
Ah ok. Thank you!!!
what would you suggest if one has to start by iterative dp? I personally like it way more and also find it more intuitive but I can't solve it.
Learning both ways doesn't hurt. It gives you more options when coding, there are times that recursive dp is easier to implement.
backtrack = complete search it's iterative and recursive version ?
Can you please list common types of DP?
Thank you so much. I want to know if you have any approach for constructive problems, and long implementation that is usually required by Div2D?
And also, many times after the contest in Div2C, I see some corners case that give the wrong answer. And many times, in contest where I could not solve Div2C, after when I see the case that give the wrong, I could easily what was the problem. Do you have any techniques to guess theses testcases, or how to ensure that your code cover all cases?
Usually if your implementation is long for such problems it means that it's not good. Look at stronger participant's code and compare yours to theirs in order to see what you're doing wrong.
As for corner cases, it fits exactly what I did for B. Prefer an approach that's clearly correct and doesn't need corner case treatment. Sometimes that means thinking DP instead of greedy, sometimes it requires rethinking how you understand the problem a bit. It's impossible to list all cases where that applies, looking at stronger contestants' code can also be extremely helpful here. If you can't simplify your solution, then you can try to stress test to find cases that break your solution. 2 hours is a lot of time for 3-4 problems, you can spare some time to stress test if you're stuck.
Thank you!
can i see edi after only 15 mins stucking ?
orz
to reduce WA and panic over solving fast, I always repeat this to myself "always solve it in the mind then start coding it"
Hmm, that is a good idea, but sometimes I want to go immediately into coding so I can get speed. I might do virtual contests to see when I can go without my mind and see when I have to use paper to think about it.
During a contest, you can make sure your code is correct before submitting it. For example, you can generate several testcases, and check them by yourself or a simple bruteforce solution. This is very helpful.
And more, you can think more deeply before you start coding. You can try to solve the problems in mind first.
More important, when you practise the past problems, you can try to reduce the number of unaccepted submissions.
hmm ye maybe after questions A and B, I can start generating test cases
Do not force solutions and do not underestimate the problem.
cows?
Bessie and Farmer John
Following kinitic013's advice but more in-depth, I also keep my speed and precision through solving mentally beforehand.
Still, I tend to approach it bit by bit. Can only code I/O? Do it. Have a solution structure but not yet knowing the inner algorithm? Then just implement the structure first, and leave a function declaration for the core. You don't need to start coding something only when you have known everything from start to finish — do what you can, and leave the rest after your thought process.
The catch here is to reduce the number of things you need to worry at the start of each problem. Might reduce dead time spent for questioning your mind even.
Also, stress testing, as some has stated, also helps in reducing WAs. I myself rarely do it (mostly because of overconfidence :D), and sometimes it actually costed me some penalty, so yeah, if feeling unsure about something, test it thoroughly.
This is a good idea. I think that I can open up places to store my code for a problem if I can't solve it fully so I won't need to recode it.
Yeah, and the idea also applies in-contest as well. Code the barebone, leave it as it is, then come back thinking. Imagine coming back with an idea and having your desk already clean and tidy (coz' you did your housekeeping beforehands) — probably much more comfy crafting the remaining code that way, I bet.
Especially for USACO, eventually you will need to solve the problems (at least 2/3 + partial)
Unlike Codeforces, USACO is pass or no pass, so just coding what you can is a good idea, especially for USACO.