mac_n_cheese_pog's blog

By mac_n_cheese_pog, history, 3 years ago, In English

imagine ur trying to solve problem C.the first time u see the problem statement ur like damn this is interesting.and 30 mins later u ahve no clue how to solve even though u have thought hardly about the problem as if youre solving world hunger and peace. then u see the editorial and it says.

just split it into 2 numbers and ur basically done.

happens to noone except me i guess

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

| Write comment?
»
3 years ago, # |
  Vote: I like it +68 Vote: I do not like it

happens to noone except me i guess

happens to literally everyone. When you practice problems of the right difficulty you should feel like you're constantly struggling, because that's a sign you're actually improving.

You can even struggle on problems far below your skill level. As a red I'm still not immune from struggling on the occasional div2A (for example edu round 100)

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    do you think strunggling==improving? for me improving==struggling and struggling!=improving u may struggle alot,but that doesnt mean u improve (which explains my rating constantly getting ups and downs at the range 600-800).even reaching 1000 is a distant dream for me.

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

      My point is that struggling is necessary for improvement, so you just have to keep pushing through and learning new ideas as you go. The more you genuinely love the process, the less it will feel like "struggling" when you're stuck on a problem.

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it +6 Vote: I do not like it

    As a red I'm still not immune from struggling on the occasional div2A (for example edu round 100)

    Don't you remember I hate 1111 (which was ironically div2A in testing) :holyfuck:

»
3 years ago, # |
  Vote: I like it +48 Vote: I do not like it

As the author of the problem in question I wanted to make some comments.

The editorial for the problem is devilishly simple, misleading people into thinking the problem was easy. I don't think the problem was that easy in practice, as evidenced by the submission count. While I didn't expect the problem to be so hard (and indeed most testers solved it), the problem was indeed hard for a div 2C.

During testing I made the comparison to 1450C1 - Крестики Нолики Errichto (простая версия). As you can see by the blog comments, it was certainly not an easy problem by any means, but after one simple observation (spoiler!) it becomes a lot easier (in fact, the observation is similar in some ways). (This is also why 1. the constraints for my problem are so small, to allow other solutions, and 2. problem D was only 1750 on the scoring distribution, to encourage people to try it as well [I think it's a lot easier to make progress on that problem FWIW.].)

It is easy to miss these observations, but just because the solution is short doesn't mean the process of getting there should be, too. There are so many things you can try in both problems, how do you know which will work out and which don't? That is problem-solving: building intuition for these types of problems so you see the same ideas later.

Contrary to what you mention, everyone goes through the phase when they just can't solve a problem, read the editorial and go "how didn't I see that?!?". This is part of the natural process of problem solving.

So TL;DR don't beat yourself up about it, short solution $$$\neq$$$ easy to come up with.

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

    To tell the truth, the idea is really hard to think but if you get the point, it's quite easy. I think that's why people think C is an easy problem.

    I used dfs when I solve this problem but didn't find the approach of the editorial... Maybe the real fun of CP is in it.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hey I just wanted to say, this problem was amazing because even though I couldn't solve it, I was finally motivated to practice bitmask. While practicing bitmasks it started helping me visualise DP states so much better as well. The fact that there are 3 ways (maybe more) to solve it is what makes it so valuable. So thank you and your co-author for the question and the contest.

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

easy to implement != easy to think

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

and 30 mins later u ahve no clue how to solve even though u have thought hardly about the problem

Solving Div2C problems in less than 30 minutes would make you at least a specialist on codeforces. I think that you are giving up too early and maybe don't have enough patience. Spending more than an hour on a problem isn't very uncommon. A better question is: what did you use these 30 minutes for? Were you just staring at the text of the problem statement and thinking?

I didn't have enough time to solve that problem C during the contest, but I upsolved it later without checking the editorial. How did this work?

Spoiler

Please note that I wasn't just staring at the screen for X minutes and then having a sudden divination: "Oh, yeah, that's the necessary observation". The time was spent writing and testing different pieces of code, each of them providing extra information and moving me closer to a working solution.

I actually enjoy Google Kick Start contests, because they motivate participants to at least try implementing solutions for small constraints, rather than giving up completely if the problem seems to be too difficult. A naive bad time complexity solution can be sometimes used as a foothold for implementing a better solution. There's an old blog https://www.joelonsoftware.com/2002/01/06/fire-and-motion/ and it talks about interesting things: "Maybe this is the key to productivity: just getting started. Maybe when pair programming works it works because when you schedule a pair programming session with your buddy, you force each other to get started."

That said, just being able to solve problems in principle is not good enough. We need to solve them very fast before a contest ends if a good rating is desired. And speed improves with experience, because many competitive programming problems are solved by similar tricks.